分数背包问题
d
P
A
R
from bisect import bisect
from itertools import accumulate
def frac_knapsack(vl, wt, w, n):
"""
>>> frac_knapsack([60, 100, 120], [10, 20, 30], 50, 3)
240.0
>>> frac_knapsack([10, 40, 30, 50], [5, 4, 6, 3], 10, 4)
105.0
>>> frac_knapsack([10, 40, 30, 50], [5, 4, 6, 3], 8, 4)
95.0
>>> frac_knapsack([10, 40, 30, 50], [5, 4, 6], 8, 4)
60.0
>>> frac_knapsack([10, 40, 30], [5, 4, 6, 3], 8, 4)
60.0
>>> frac_knapsack([10, 40, 30, 50], [5, 4, 6, 3], 0, 4)
0
>>> frac_knapsack([10, 40, 30, 50], [5, 4, 6, 3], 8, 0)
95.0
>>> frac_knapsack([10, 40, 30, 50], [5, 4, 6, 3], -8, 4)
0
>>> frac_knapsack([10, 40, 30, 50], [5, 4, 6, 3], 8, -4)
95.0
>>> frac_knapsack([10, 40, 30, 50], [5, 4, 6, 3], 800, 4)
130
>>> frac_knapsack([10, 40, 30, 50], [5, 4, 6, 3], 8, 400)
95.0
>>> frac_knapsack("ABCD", [5, 4, 6, 3], 8, 400)
Traceback (most recent call last):
...
TypeError: unsupported operand type(s) for /: 'str' and 'int'
"""
r = sorted(zip(vl, wt), key=lambda x: x[0] / x[1], reverse=True)
vl, wt = [i[0] for i in r], [i[1] for i in r]
acc = list(accumulate(wt))
k = bisect(acc, w)
return (
0
if k == 0
else sum(vl[:k]) + (w - acc[k - 1]) * (vl[k]) / (wt[k])
if k != n
else sum(vl[:k])
)
if __name__ == "__main__":
import doctest
doctest.testmod()
关于此算法
问题陈述
给定一组物品，每个物品都有重量和价值，确定每个物品包含在集合中的数量，以便总重量小于或等于给定的限制，并且总价值尽可能大。
贪心算法总是可以为分数背包问题提供最优解。
时间复杂度
O(nlog n) 最坏情况
示例
Lets assume the capacity of knapsack, W = 60
value = [280, 100, 120, 120]
weight = [40, 10, 20, 24]
Ratio(V/W) = 7,10,6,5
Say those items as A,B,C,D
next, the items should be sorted in descending order based on the ratio of value by weight to get maximum profit
First and foremost, B was picked since its weight is smaller than the knapsack's capacity. The next item, A, is chosen since the knapsack's available capacity is more than A's weight. C is now the next item on the list. However, the entire item cannot be chosen because the knapsack's remaining capacity is less than C's weight.
As a result, the C proportion (60–50)/20)
The knapsack's capacity is now equal to the specified items.
As a result, no more items can be chosen.
10 + 40 + 20*(10/20) = 60 is the total weight of the chosen goods.
100+280+120*(10/20)=380+60=440 is the total profit.
This is the most suitable option.
We won't be able to make more money by combining diverse things.
