Python实现背包问题：求解可多次选取物品的最大价值

假设我们有两个长度相同的列表，分别称为weights（重量）和values（价值），还有一个capacity（容量）值。其中weights[i]和values[i]分别表示第i个物品的重量和价值。如果我们最多可以承受capacity重量，并且可以对每个物品选取任意数量的副本，我们需要找到可以获得的最大价值。

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

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

• 定义一个函数dp()。它将接收i和k作为参数。
• 如果i等于weights的长度，则
  • 返回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))

输入

[1, 2, 3], [1,5,3], 5

输出

11

Arnab Chakraborty

更新于：2020年10月20日

507 次浏览

开启您的职业生涯

完成课程获得认证

开始学习