पायथन में कई प्रतियाँ लेकर हम अधिकतम मूल्य खोजने के लिए नैपसेक समस्या प्राप्त कर सकते हैं

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

इसलिए, यदि इनपुट वज़न =[1, 2, 3], मान =[1, 5, 3], क्षमता =5 जैसा है, तो आउटपुट 11

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

• एक फ़ंक्शन को परिभाषित करें dp() । यह ले जाएगा मैं, कश्मीर
• अगर मैं वजन के आकार के समान हूं, तो
  • वापसी 0
• उत्तर:=dp(i + 1, k)
• यदि k>=भार[i], तो
  • Ans :=अधिकतम ans और dp(i, k - weights[i]) + value[i]
• वापसी उत्तर
• मुख्य विधि से निम्न कार्य करें -
• रिटर्न डीपी(0, क्षमता)

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

उदाहरण

class Solution:
   def solve(self, weights, values, capacity):
      def dp(i, k):
         if i == len(weights):
            return 0
         ans = dp(i + 1, k)
         if k >= weights[i]:
            ans = max(ans, dp(i, k - weights[i]) + values[i])
         return ans
      return dp(0, capacity)
ob = Solution()
weights = [1, 2, 3]
values = [1, 5, 3]
capacity = 5
print(ob.solve(weights, values, capacity))

इनपुट

[1, 2, 3], [1,5,3], 5

आउटपुट

11