Fractional Knapsack

Fractional Knapsack is the cleanest example of a greedy algorithm. Unlike the classic 0/1 knapsack (which needs dynamic programming), here you may take a fraction of an item — and that one freedom makes a simple greedy choice provably optimal.

The slow way first

You might think: try every combination of items, or every cut point. With fractions allowed, the number of possibilities is unbounded — and even restricting to whole-item subsets is O(2ⁿ). That is far too slow and, worse, it ignores the structure that makes this problem easy.

The question to ask: if I could add just one more kilogram to the bag, which item gives me the most value for it? The answer never changes: the item with the highest value-per-kilogram.

The idea: take the densest value first

Each item has a ratio = value / weight — its value per kilogram. Sort items by that ratio, highest first. Then walk down the list: take each item whole while it still fits, and when you reach the first item that does not fit, take just the fraction that fills the remaining space. Once the bag is full, stop.

The key insight: every kilogram of space should hold the densest value available. Because we can split items, there is never a reason to skip a denser item for a lighter one — greedy is exactly optimal.

Walk through it

Step through the animation. The three items are already sorted by ratio (6.0, 5.0, 4.0). The pick pointer scans left to right. The first two fit whole, draining the capacity meter from 50 to 40 to 20. The third weighs 30 kg but only 20 kg remains, so we take 20/30 of it for 4.0 × 20 = $80, filling the bag and reaching a total of $240.

Pseudocode

sort items by (value / weight) descending
total = 0
for each item:
    if item.weight <= capacity:        # fits whole
        total += item.value
        capacity -= item.weight
    else:                              # does not fit
        fraction = capacity / item.weight
        total += item.value * fraction # take just enough to fill up
        stop
return total

The Python solution

def fractional_knapsack(items, capacity):
    items.sort(key=lambda it: it.value / it.weight,
               reverse=True)
    total = 0.0
    for it in items:
        if it.weight <= capacity:
            total += it.value
            capacity -= it.weight
        else:
            fraction = capacity / it.weight
            total += it.value * fraction
            capacity = 0
            break
    return total

• We sort items by value / weight descending, so the densest value comes first.
• total accumulates the value we have packed; capacity is the room left.
• If an item fits whole (weight <= capacity), we take all of it and shrink the capacity.
• Otherwise it is the last item we touch: fraction = capacity / weight is the portion that fits, and we add that share of its value.
• The break ends the loop — once the bag is full no later (lower-ratio) item can improve the answer.

Complexity

The sort dominates at O(n log n); the fill loop is a single linear pass. We use only O(1) extra space beyond the input (or O(n) if the sort is not in place).

When this pattern shows up

Practice