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

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

因此，如果输入像权重= [6，7，3]值= [110，120，2]容量= 10，那么输出将是178。

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

• res：= 0

• cif容量为0，则

• 如果pair [0]>容量，则

• 否则，当pair [0] <=容量时，则

• 从循环中出来

• res：= res +（pair [1] /（pair [0] /容量）的商

• 容量：= 0

• res：= res +对[1]

• 容量：=容量-对[0]

• 列出具有权重和值的对P的列表，并根据每个权重的值对它们进行排序

• 对于P中的每对

• 返回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 = Soluthtml" target="_blank">ion()weights = [6, 7, 3]
values = [110, 120, 2]
capacity = 10
print(ob.solve(weights, values, capacity))

输入值

[6, 7, 3],[110, 120, 2],10

输出结果

230