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

更新于: 2020年10月5日

512 次浏览

开启你的 职业生涯

通过完成课程获得认证

立即开始
广告