मान लीजिए हमारे पास समान लंबाई की दो सूचियाँ हैं जिन्हें weights और values कहा जाता है, और हमारे पास एक और मान capacity है। यहां weights[i] और values[i] iवीं वस्तु का वजन और मूल्य दर्शाते हैं। यदि हम अधिकतम capacity वजन ले सकते हैं, और हम प्रत्येक वस्तु की कितनी भी प्रतिलिपियाँ ले सकते हैं, तो हमें प्राप्त होने वाले मूल्य की अधिकतम मात्रा ढूंढनी है।
इसलिए, यदि इनपुट weights = [1, 2, 3], values = [1, 5, 3], capacity = 5 जैसा है, तो आउटपुट 11 होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −
- एक फ़ंक्शन dp() परिभाषित करें। यह i, k लेगा
- यदि i, weights के आकार के समान है, तो
- 0 वापस करें
- ans := dp(i + 1, k)
- यदि k >= weights[i], तो
- ans := ans और dp(i, k - weights[i]) + values[i] का अधिकतम
- ans वापस करें
- मुख्य विधि से निम्नलिखित करें −
- dp(0, capacity) वापस करें
बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −
उदाहरण
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
