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

मान लीजिए हमारे पास संख्याओं की दो सूचियाँ हैं: weights और values। ये समान लंबाई की हैं। हमारे पास capacity और count भी हैं। weights[i] और values[i] i-वें आइटम का वजन और मूल्य दर्शाते हैं। हम अधिकतम capacity वजन और अधिकतम count आइटम कुल रख सकते हैं, और प्रत्येक आइटम की केवल एक प्रति ले सकते हैं। हमें प्राप्त होने वाले अधिकतम मूल्य को ज्ञात करना है।

उदाहरण के लिए, weights = [2, 2, 4, 6], values = [15, 15, 20, 35], capacity = 8, count = 3 के लिए आउटपुट 50 होगा (पहले 3 आइटम चुनें, कुल वजन 8)।

एल्गोरिदम (रिकर्सिव DP)

items := weights और values से बने जोड़ों की सूची
dp(i, cp, ct) फ़ंक्शन परिभाषित करें:
- यदि i == len(items) या ct == 0, तो 0.0 वापस करें
- (w, v) := items[i]
- ans := dp(i+1, cp, ct) (आइटम न लें)
- यदि cp >= w, तो ans = max(ans, dp(i+1, cp-w, ct-1) + v) (आइटम लें)
- ans वापस करें
मुख्य विधि से dp(0, capacity, count) वापस करें

उदाहरण

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