Fractional Knapsack
你有 n 件物品。第 i 件物品的价值为 values[i]，重量为 weights[i]。你的背包最多能装 capacity 的总重量，而且你可以只取一件物品的一部分：第 i 件物品中重量为 w 的部分，价值为 values[i] × w / weights[i]。
编写一个名为 fractionalKnapsack 的函数，返回背包能装下的最大总价值，并向下取整为整数。
函数
- valuesinteger-array
- 每个项目的值
- weightsinteger-array
- 每件物品的重量
- capacityinteger
- 袋子最多能装的重量
- 返回值integer
- 能装入背包的最大总价值，向下取整
约束条件
1 ≤ n ≤ 5000，其中n = values.length = weights.length1 ≤ values[i], weights[i] ≤ 1041 ≤ capacity ≤ 108
示例
- 输入
- values = [40, 90, 30, 50]weights = [8, 30, 5, 20]capacity = 40
- 输出
- 151
- 解释
- 物品的单位重量价值分别为 5、3、6 和 2.5。完整装入物品 2 和 0，价值为 70，还剩 27 的容量。再装入物品 1 的 30 个单位中的 27 个，增加 81 的价值，总计 151。
- 输入
- values = [10, 7]weights = [4, 3]capacity = 5
- 输出
- 12
- 解释
- 物品 0 的单位价值为 2.5，物品 1 的单位价值约为 2.33，因此物品 0 可以整体放入，价值为 10。物品 1 的 3 个单位中，取 1 个可增加
7 / 3，12 又三分之一向下取整为 12。
- 输入
- values = [5, 8]weights = [2, 3]capacity = 100
- 输出
- 13
- 解释
- 这两件物品都能轻松装下，所以你把它们全都拿走：5 + 8 = 13。
进阶
你能在 O(n) 时间内找到答案，而不对所有物品进行排序吗？
提示
逐个打开提示，每个都会多透露一点。
如果背包还能再装 1 个单位的重量，你会从哪个物品中取出这部分重量？
单位重量的价值越高，物品就越值得优先选择。从密度最高的物品开始装满背包，只有最后放入的物品需要切分。
按密度从高到低排序，通过比较
values[a] × weights[b]和values[b] × weights[a]，这样就不必做除法。能装下时就拿取整个物品，然后对装满背包的那个物品，使用整数除法计算values[i] × room / weights[i]。
题解
由于你可以拆分物品，这个问题属于贪心问题，与 0/1 背包问题不同：每单位重量都应来自剩余单位价值最高的物品。按单位价值排序，然后依次装满背包。通过交叉相乘比较单位价值，并且只对拆分的物品向下取整，这样就不需要存储任何小数。
每轮选择密度最大的物品
结果正确，但无法在最大的测试中运行完毕
思路
从密度最大的物品开始装袋：如果能装下，就整件装入；否则，装入刚好填满袋子的那部分，然后停止。扫描所有物品，找出尚未使用的物品中密度最大的一个。比较 values[i] × weights[j] 和 values[j] × weights[i]，而不是进行除法。只要重量为正，这种比较方法就等价，而且两个乘积都不会超过 10^8。
优先装入密度最大的物品是最优的：如果装载的某部分重量来自密度较低的物品，而密度更高的物品还没有完全装入，那么用密度更高的物品替换这部分重量，价值不会降低。持续替换，就能得到按密度从高到低装载的结果。
最多进行 n 轮，每轮都要扫描尚未使用的物品；当 n = 5000 时，大约需要进行 n²/2 = 1250 万次比较。
算法
- 将每件物品标记为未使用，并设置
room = capacity和total = 0。 - 只要还有剩余容量，就扫描未使用的物品，通过交叉相乘比较密度，找出密度最高的物品。
- 如果没有剩余物品，就停止。否则，将该物品标记为已使用。
- 如果该物品能装下，就将它的价值加到
total中，并从room中减去它的重量。如果装不下，就用整数除法将values[i] × room / weights[i]加到total中，然后停止。 - 返回
total。
def fractionalKnapsack(values, weights, capacity):
n = len(values)
used = [False] * n
total = 0
room = capacity
while room > 0:
best = -1
for i in range(n):
# i is denser than best: values[i] / weights[i] > values[best] / weights[best], cross-multiplied
if not used[i] and (best == -1 or values[i] * weights[best] > values[best] * weights[i]):
best = i
if best == -1:
break # every item is already in the bag
used[best] = True
if weights[best] <= room:
total += values[best]
room -= weights[best]
else:
total += values[best] * room // weights[best] # the part that fits, rounded down
room = 0
return total按单位重量的价值排序
思路
扫描会一次又一次地找到密度最高的物品，但每一轮的顺序都不会改变。用相同的交叉相乘比较方法，只排序一次物品，按密度从高到低排列。密度相同的物品可以按任意顺序排列，因为它们每单位的价值相同。
只要装得下，就整件取走物品。第一个装不下的物品是唯一需要拆分的物品：它会增加 values[i] × room / weights[i]，而整数除法会向下取整。它之前的物品都是整件取走的，因此只对这一项取整，就能得到准确答案。排序的时间复杂度是 O(n log n)，遍历的时间复杂度是 O(n)。
算法
- 创建一个物品索引列表，并使用交叉相乘比较法按密度从高到低排序。
- 设置
room = capacity，并设置total = 0。 - 按该顺序遍历每件物品，如果
weights[i] ≤ room，则累加其价值，并从room中减去其重量。 - 否则，使用整数除法累加
values[i] × room / weights[i]，然后停止。 - 返回
total。
from functools import cmp_to_key
def fractionalKnapsack(values, weights, capacity):
# a goes before b when values[a] / weights[a] > values[b] / weights[b],
# tested as values[a] * weights[b] > values[b] * weights[a] to stay in whole numbers.
def denser_first(a, b):
return values[b] * weights[a] - values[a] * weights[b]
order = sorted(range(len(values)), key=cmp_to_key(denser_first))
total = 0
room = capacity
for i in order:
if weights[i] <= room:
total += values[i] # the whole item fits
room -= weights[i]
else:
total += values[i] * room // weights[i] # the part that fits, rounded down
break
return total
易错点和边界情况
- 只按价值或重量排序。在第一个示例中，价值为 90 的物品密度排名第三；先拿它，会剩下足够的空间容纳价值为 50 的物品的一半，总价值为 115，而不是 151。
- 先除再乘。价值为 13、重量为 7、剩余容量为 3 时，使用整数运算计算
13 / 7 * 3会得到 3，而13 * 3 / 7才能得到正确结果 5。 - 以为每次都要切分物品。在第三个示例中，所有物品都能装下，答案就是所有价值的总和 13。
常见问题3
分数背包问题的时间复杂度是多少？
按单位重量的价值对物品排序需要 O(n log n)，填充过程只需遍历一遍，因此总时间复杂度为 O(n log n)，排序结果占用 O(n) 空间。每轮扫描以找到价值密度最高的物品，需要 O(n²) 时间。
为什么贪心算法适用于分数背包问题，却不适用于 0/1 背包问题？
切分可以让你用密度更高的物品替换密度较低的物品。如果不能切分，较高密度的物品可能会留下无法填满的空间。价值为 8、11、15，重量为 2、3、4，容量为 7 时，按密度从高到低选择会得到重量为 2 和 4 的物品，总价值为 23；而选择重量为 3 和 4 的物品，总价值为 26。0/1 版本需要使用动态规划。
如何在不使用浮点数的情况下求解分数背包问题？
对于正权重，a / b > c / d 与 a × d > c × b 是等价的判断方法，因此可以通过交叉相乘来比较密度。最优值是一个整数加上一个分数，对于被切分的物品，这个分数是 values[i] × room / weights[i]，因此只需进行一次整数除法，就能得到精确的向下取整结果。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def fractionalKnapsack(values, weights, capacity):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
values = [40, 90, 30, 50] weights = [8, 30, 5, 20] capacity = 40
预期输出
151