Python程式：在容量限制內選擇不同物品以獲取最大價值

假設我們有兩個列表，分別稱為 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] = (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

輸出

8

Arnab Chakraborty

更新於: 2020年10月5日

512 次瀏覽

開啟你的 職業生涯

透過完成課程獲得認證

立即開始