Fractional Knapsack
i
d
p
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()
关于这个算法
Problem Statement
Given a set of items, each with weight and a value, determine the number of each item included in a collection so that the total weight is less than or equal to the given limit and the total value is as large as possible.
Greedy method will always provide an optimal solution with fractional knapsack problem.
Time Complexity
O(nlog n) Worst Case
Example
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.
