Python程序：求解背包中物品所能获得的最大价格

假设我们有两个数字列表。一个称为weights（重量），另一个称为values（价值）。它们的长度相同。我们还有两个值，capacity（容量）和count（数量）。其中weights[i]和values[i]分别表示第i个物品的重量和价值。我们最多可以容纳capacity重量的物品，并且最多可以携带count件物品。每个物品只能取一件，我们需要找到可以获得的最大价值。

例如，如果输入为weights = [2, 2, 4, 6]，values = [15, 15, 20, 35]，capacity = 8，count = 3，则输出为50，因为我们可以选择前3个物品，总重量为8。

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

  • items := 通过组合weights和values创建一个包含重量和价值对的列表

  • 定义一个函数dp()。它将接收i, cp, ct作为参数

  • 如果i等于items的长度或ct等于0，则

    • 返回0.0

  • (w, v) := items[i]

  • ans := dp(i + 1, cp, ct)

  • 如果cp >= w，则

    • ans := ans和dp(i + 1, cp - w, ct - 1) + v中的最大值

  • 返回ans

  • 在主方法中返回dp(0, capacity, count)

示例

让我们来看下面的实现，以便更好地理解：

 在线演示

class Solution:
   def solve(self, weights, values, capacity, count):
      items = list(zip(weights, values))
      def dp(i, cp, ct):
         if i == len(items) or ct == 0:
            return 0.0
         w, v = items[i]
         ans = dp(i + 1, cp, ct)
         if cp >= w:
            ans = max(ans, dp(i + 1, cp - w, ct - 1) + v)
         return ans
      return int(dp(0, capacity, count))
ob = Solution()
weights = [2, 2, 4, 6]
values = [15, 15, 20, 35]
capacity = 8
count = 3
print(ob.solve(weights, values, capacity, count))

输入

[2, 2, 4, 6], [15, 15, 20, 35], 8, 3

输出

50

更新于：2020-12-22

310 次浏览

开启你的职业生涯

完成课程获得认证

开始学习
广告