पायथन में एक बैग में आइटम रखकर हम अधिकतम मूल्य प्राप्त करने का कार्यक्रम प्राप्त कर सकते हैं

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

इसलिए, यदि इनपुट वज़न की तरह है =[2, 2, 4, 6] मान =[15, 15, 20, 35] क्षमता =8 गिनती =3, तो आउटपुट 50 होगा, क्योंकि हम पहले 3 आइटम चुन सकते हैं , चूंकि कुल वजन 8 है।

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

आइटम :=वजन और मान लेकर जोड़ियों की सूची
एक फ़ंक्शन को परिभाषित करें dp() । यह ले जाएगा मैं, सीपी, सीटी
अगर मैं आइटम के आकार के समान हूं या सीटी 0 के समान है, तो
- वापसी 0.0
(डब्ल्यू, वी) :=आइटम [i]
उत्तर:=डीपी (i + 1, सीपी, सीटी)
अगर सीपी>=डब्ल्यू, तो
- उत्तर:=अधिकतम उत्तर, dp(i + 1, cp - w, ct-1) + v
वापसी उत्तर
मुख्य विधि से वापसी dp(0, क्षमता, गिनती)

उदाहरण

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

class Solution:
   def solve(self, weights, values, capacity, count):
      items = list(zip(weights, values))
      def dp(i, cp, ct):
         if i == len(items) or ct == 0:
            return 0.0
         w, v = items[i]
         ans = dp(i + 1, cp, ct)
         if cp >= w:
            ans = max(ans, dp(i + 1, cp - w, ct - 1) + v)
         return ans
      return int(dp(0, capacity, count))
ob = Solution()
weights = [2, 2, 4, 6]
values = [15, 15, 20, 35]
capacity = 8
count = 3
print(ob.solve(weights, values, capacity, count))

इनपुट

[2, 2, 4, 6], [15, 15, 20, 35], 8, 3