Fractional Knapsack

Problem We are given a set of items, their weights and values.
We have a knapsack (bag) of given capacity.
Our target is to collect max value in the knapsack. We can pick items partially (that is why it's called fractional)

	i1	i2	i3
weights	50	20	30
values	600	500	400

knapsack capacity = 70

output = 1410
$i1 + i2 + 20/50 * i1$
$500 + 400 + (20/50*600) = 1410$

Time: $O(nlogn)$ Pseudo Code:

- calculate ratio (value/weight) for every item
- sort items in decreasing ratio
- initialize res = 0, current_capacity = given_capacity
- do the following for every item, I in sorted order:
    if I.weight <= current_capacity:
        current_capacity -= I.weight
        res += I.value
    else:
        res += (I.value) * (current_capacity / I.weight)
        return res
- return res

Python

def fKnapsack(items, capacity):
    N = len(items)
    valueWeight = sorted(items, key=lambda x: x[0]*1.0/x[1], reverse=True)
    res = 0.0
    for v, w in valueWeight:
        if w <= capacity:
            capacity -= w
            res += v
        else:
            res += v * (capacity / w)
            break
    return res