用 Python 实现分数背包问题的程序

pythonserver side programmingprogramming更新于 2026/1/15 0:12:17

假设我们有两个列表，长度相同的权重和值以及另一个值容量。weights[i] 和 values[i] 代表第 i 个元素的权重和值。因此，如果我们最多可以取容量权重，并且可以取一个项目重量的一小部分，并按比例取值，那么我们必须找到我们可以得到的最大价值(四舍五入到最接近的整数)

因此，如果输入为 weights = [6, 7, 3] values = [110, 120, 2] capacity = 10，则输出为 178。

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

res := 0
- 制作一个带有权重和值的对 P 列表，并根据每个权重的值对它们进行排序
- 对于 P 中的每一对，执行
  - 如果 capacity 为 0，则
    - 从中出来循环
  - 如果 pair[0] > capacity，则
    - res := res + (pair[1] /(pair[0] / capacity) 的商
    - capacity := 0
  - 否则，当 pair[0] <= capacity 时，则
    - res := res + pair[1]
    - capacity := capacity - pair[0]
- 返回 res 的底值

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

示例

class Solution:
   def solve(self, weights, values, capacity):
      res = 0
      for pair in sorted(zip(weights, values), key=lambda x: - x[1]/x[0]):
         if not bool(capacity):
            break
         if pair[0] > capacity:
            res += int(pair[1] / (pair[0] / capacity))
            capacity = 0
         elif pair[0] <= capacity:
            res += pair[1]
            capacity -= pair[0]
      return int(res)

ob = Solution()
weights = [6, 7, 3]
values = [110, 120, 2]
capacity = 10
print(ob.solve(weights, values, capacity))