Fractional Knapsack

#How does it work?

Fractional knapsack is the version of 0/1 knapsack where items can be split: we may take any amount of an item, not just all or nothing (think gold dust, spices or fabric).

Here the greedy approach is optimal: sort items by value per unit of weight (v / w), take whole items starting with the most valuable, then cut the first item that doesn't fit to fill the remaining space, and stop.

With the same items, 0/1 knapsack's best value for capacity 7 is 9; the fractional version reaches 9.67. In the 0/1 version the same greedy rule can fail, because items can't be split to use the leftover space. That is why 0/1 knapsack needs DP.

#Try it yourself

#Step by step

1. 01Compute v / w for each item.
2. 02Sort the items by that ratio, largest first.
3. 03Take every item that fits whole.
4. 04From the first item that doesn't fit, take the fraction that fills the remaining capacity and stop.

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

# (weight, value) of each item; any fraction of an item may be taken.
ITEMS = [(1, 1), (3, 4), (4, 5), (5, 7)]


def fractional_knapsack(items: list, capacity: float) -> float:
    total = 0.0
    for w, v in sorted(items, key=lambda it: it[1] / it[0], reverse=True):  # best value per weight first
        if capacity <= 0:
            break
        take = min(w, capacity)  # the whole item, or the part that still fits
        total += v * take / w
        capacity -= take
    return total


print(f"{fractional_knapsack(ITEMS, 7):.2f}")  # 0/1 knapsack only reaches 9

#Complexity

Sorting dominates. With a selection algorithm, finding the item to cut can even be done in O(n). The result is always optimal: a unit from a lower-ratio item can never beat a unit from a higher-ratio one.

#When to use it?

Sharing out divisible resources: budget allocation, cargo and fuel planning, fractional investment amounts. It is also used to compute upper bounds in branch-and-bound solvers for 0/1 knapsack.

#Practice

Log in to answer questions and save your progress.