पायथन में फ्रैक्शनल नैपसैक समस्या को लागू करने का प्रोग्राम

मान लीजिए हमारे पास दो सूचियां हैं, weights और values समान लंबाई की, और एक मान capacity। weights[i] और values[i] iवें आइटम का वजन और मूल्य दर्शाते हैं। यदि हम अधिकतम capacity वजन ले सकते हैं, और हम किसी आइटम के वजन का अंश समानुपातिक मूल्य के साथ ले सकते हैं, तो हमें प्राप्त होने वाले मूल्य की अधिकतम मात्रा ढूंढनी है (निकटतम पूर्णांक तक राउंड डाउन)।

उदाहरण के लिए, यदि इनपुट weights = [6, 7, 3], values = [110, 120, 2], capacity = 10 है, तो आउटपुट 178 होगा। (नोट: दिए गए कोड में आउटपुट 230 दिखाया गया है, लेकिन सही उत्तर 178 है जब प्रति यूनिट मूल्य के अनुसार सॉर्ट किया जाता है।)

इसे हल करने के लिए हम निम्न चरणों का पालन करेंगे (लालची एल्गोरिदम):

res := 0।
P को (वजन, मूल्य) जोड़े की सूची बनाएं और उन्हें value/weight अनुपात के अवरोही क्रम में सॉर्ट करें।
प्रत्येक pair के लिए P में:
- यदि capacity == 0, तो ब्रेक।
- यदि pair[0] > capacity:
  - res += int(pair[1] / (pair[0] / capacity))।
  - capacity = 0।
- अन्यथा (pair[0] <= capacity):
  - res += pair[1]।
  - capacity -= pair[0]।
int(res) लौटाएं।

उदाहरण

class Solution:    def solve(self, weights, values, capacity):       res = 0       for pair in sorted(zip(weights, values), key=lambda x: - x[1]/x[0]):          if not bool(capacity):             break          if pair[0] > capacity:             res += int(pair[1] / (pair[0] / capacity))             capacity = 0          elif pair[0] <= capacity:             res += pair[1]             capacity -= pair[0]       return int(res) ob = Solution() weights = [6, 7, 3] values = [110, 120, 2] capacity = 10 print(ob.solve(weights, values, capacity))

इनपुट

[6, 7, 3],[110, 120, 2],10