पायथन में भिन्नात्मक नैपसेक समस्या को लागू करने का कार्यक्रम

मान लीजिए कि हमारे पास दो सूचियाँ, वज़न और समान लंबाई के मान और एक अन्य मान क्षमता है। वजन [i] और मान [i] ith तत्व के वजन और मूल्य का प्रतिनिधित्व करते हैं। इसलिए यदि हम अधिक से अधिक क्षमता भार ले सकते हैं, और यह कि हम किसी वस्तु के भार का एक अंश आनुपातिक मूल्य के साथ ले सकते हैं, तो हमें वह अधिकतम मूल्य ज्ञात करना होगा जो हम प्राप्त कर सकते हैं (निकटतम पूर्णांक तक पूर्णांकित)

इसलिए, अगर इनपुट वज़न की तरह है =[6, 7, 3] मान =[110, 120, 2] क्षमता =10, तो आउटपुट 178 होगा।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

रेस :=0
- वजन और मूल्यों के साथ जोड़े पी की एक सूची बनाएं, और प्रति वजन के मूल्यों के आधार पर उन्हें क्रमबद्ध करें
- P में प्रत्येक जोड़ी के लिए, करें
  - सीआईएफ क्षमता 0 है, तो
    - लूप से बाहर आएं
  - अगर जोड़ी [0]> क्षमता, तो
    - रेस :=रेस + भागफल (जोड़ी[1] /(जोड़ी[0] / क्षमता)
    - क्षमता :=0
  - अन्यथा जब युग्म[0] <=क्षमता, तब
    - रेस:=रेस + पेयर[1]
    - क्षमता :=क्षमता - जोड़ी[0]
- रेज का रिटर्न फ्लोर वैल्यू

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

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