用 Python 编写程序，找出在容量范围内取不同物品可以获得的最大数量

pythonserver side programmingprogramming更新于 2026/1/8 23:08:17

假设我们有两个列表，分别称为 weights 和 values，它们的长度相同，还有一个数字，称为容量 k。这里的 weights[i] 和 values[i] 表示第 i 个物品的重量和价值。现在，我们最多可以取 k 个容量权重，并且每个项目最多只能取一份，我们必须找到可以得到的最大价值。

因此，如果输入为 weights = [2, 3, 4], values = [2, 6, 4], capacity = 6，则输出为 8

要解决这个问题，我们将遵循以下步骤 −

n:= 权重的大小
dp:= 一个大小为 capacity x n 的矩阵，并用 0 填充
对于范围从 0 到 n 的 i，执行
- 对于范围从 0 到 capacity 的 j，执行
  - 如果 i 与 0 相同或 j 与 0 相同，则
    - dp[i, j]:= 0
  - 否则当 weights[i-1] <= j 时，则
    - dp[i,j] = maximum of (dp[i-1, j-weights[i - 1]] + values[i-1]) and (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))