用 Python 编写程序，通过复制多个副本找到背包问题中可以得到的最大值

pythonserver side programmingprogramming更新于 2026/2/2 12:28:17

假设我们有两个长度相同的列表，它们分别称为权重和值，我们还有另一个值容量。这里 weights[i] 和 values[i] 表示第 i 个项目的权重和值。如果我们最多可以复制容量权重，并且可以为每个项目复制任意数量的副本，那么我们必须找到可以得到的最大价值。

因此，如果输入为 weights = [1, 2, 3], values = [1, 5, 3], capacity = 5，则输出将为 11

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

定义一个函数 dp() 。这将需要 i, k
如果 i 与权重的大小相同，则
- 返回 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))