पायथन में क्षमता के भीतर अलग-अलग आइटम लेकर प्राप्त की जा सकने वाली अधिकतम राशि खोजने का प्रोग्राम

मान लीजिए हमारे पास weights और values नामक दो सूचियां हैं जो समान लंबाई की हैं और एक अन्य संख्या capacity जिसे k कहते हैं। यहां weights[i] और values[i] iवें आइटम का वजन और मूल्य दिखाते हैं। अब, हम अधिकतम k क्षमता का वजन ले सकते हैं, और हम प्रत्येक आइटम की अधिकतम एक प्रति ले सकते हैं। हमें प्राप्त होने वाले मूल्य की अधिकतम राशि ढूंढनी है।

उदाहरण के लिए, यदि इनपुट है weights = [2, 3, 4], values = [2, 6, 4], capacity = 6, तो आउटपुट होगा 8।

हल करने के चरण

n := weights का आकार।
dp := आकार capacity x n का मैट्रिक्स, 0 से भरा हुआ।
i को 0 से n तक:
- j को 0 से capacity तक:
  - यदि i == 0 या j == 0, तो dp[i][j] := 0।
  - अन्यथा जब weights[i-1] <= j, तो dp[i][j] = max(dp[i-1][j-weights[i-1]] + values[i-1], dp[i-1][j])।
  - अन्यथा, dp[i][j] := dp[i-1][j]।
dp[n][capacity] लौटाएं।

उदाहरण

class Solution:
    def solve(self, weights, values, capacity):
        n = len(weights)
        dp = [[0 for i in range(capacity+1)] for _ in range(n+1)]
        for i in range(n+1):
            for j in range(capacity+1):
                if i == 0 or j == 0:
                    dp[i][j] = 0
                elif weights[i-1] <= j:
                    dp[i][j] = max(dp[i-1][j-weights[i-1]] + values[i-1], dp[i-1][j])
                else:
                    dp[i][j] = dp[i-1][j]
        return dp[n][capacity]

ob = Solution()
weights = [2, 3, 4]
values = [2, 6, 4]
capacity = 6
print(ob.solve(weights, values, capacity))

इनपुट

[2, 3, 4], [2, 6, 4], 6