在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 = Solution()weights = [6, 7, 3]
values = [110, 120, 2]
capacity = 10
print(ob.solve(weights, values, capacity))输入值
[6, 7, 3],[110, 120, 2],10
输出结果
230