Fractional Knapsack, in depth: the greedy proof, a linear-time algorithm and the LP bound

Filling by density

The idea: value per unit of capacity

Give every item a weight w and a value v, and define its density as v divided by w: value per unit of capacity. Capacity is the only scarce thing, so each unit of it should go where it earns the most. The densest item earns the most per kilogram, so take as much of it as you can. When it is gone, the next densest item is the best remaining use of capacity, and so on, until capacity runs out. The last item you touch is usually taken in part, because it is cut off by the remaining room.

This is the shape of every greedy algorithm: an ordering, and a rule that commits to the best-looking choice and never revisits it. This one is right because splitting removes what makes density misleading in the 0/1 version: a dense item that does not fit, or leaves an awkward gap. The general pattern and its proof techniques are covered in greedy algorithms.

Worked example

Take a capacity of 48 kg and five items.

Sorted by density the order is C, A, B, E, D. C, A and B together weigh 45 kg and are worth 146. Three kilograms remain, so the algorithm takes three fifths of E for 7.2 and stops. The optimum is 153.2. Notice that D, the most valuable item in absolute terms, is not taken at all: what matters is value per unit of capacity, not value.

For contrast, the best 0/1 packing of the same instance is C, A and B for 146, which leaves 3 kg empty because nothing else fits. The fractional optimum, 153.2, is an upper bound on every 0/1 packing; the gap of 7.2 is exactly the value of the split item. That relationship is what makes the fractional solution useful even when you are not allowed to split.

Why greedy is optimal: the exchange argument

Why is the greedy answer optimal? Use an exchange argument. Sort items so that density never increases: d1 ≥ d2 ≥ ... ≥ dn. Let G be the greedy solution and X any optimal solution, each described by the fraction of every item taken. Assume X fills the capacity whenever the items' total weight allows it, since leaving room empty can only lose value.

If X differs from G, look at the first item i, in density order, where X takes less than G. Greedy takes as much of each item as it can, in order, so X must make up that weight somewhere later, on some item j with dj ≤ di, where X takes more than G. Move a small weight δ from j to i in X. Capacity used is unchanged. Value changes by δ(di - dj), which is never negative. Repeat until X agrees with G on item i, then move to the next difference. Every step keeps X feasible and never lowers its value, and the process ends at G. So G is worth at least as much as an optimal solution, which means it is optimal.

It also shows that ties do not matter, since moving weight between equal densities changes nothing, and exactly where 0/1 knapsack escapes: moving a small weight δ is illegal when items are indivisible.

The LP view and the critical ratio

Written as a linear program, fractional knapsack is: maximise the sum of vi xi subject to the sum of wi xi ≤ W and 0 ≤ xi ≤ 1. It has one resource constraint, and that is why it is easy. LP theory says an optimal solution sits at a vertex of the feasible region, and with one constraint plus bounds a vertex has at most one variable strictly between 0 and 1. That is the split item.

The dual gives the density threshold an economic meaning. Let λ be the density of the split item, the critical ratio. It is the shadow price of capacity: one more kilogram of capacity would be worth λ more value. Every item with density above λ is taken whole, every item below is left, and only items exactly at λ may be partial. In the example λ is 2.4. This view explains why you do not need a full sort. You only need to find λ and the items on each side of it, which is a selection problem, not a sorting problem.

Code: sort-based and linear-time

The direct implementation sorts by density and fills. It uses Fraction so densities are compared exactly; floating-point keys can order two nearly equal densities wrongly and, worse, can leave room at a tiny positive value instead of zero.

from fractions import Fraction

def fractional_knapsack(items, capacity):
    # items: (name, weight, value) with weight >= 0 and value >= 0.
    # Returns the exact optimum and a plan of (name, fraction taken).
    if capacity < 0:
        raise ValueError("capacity must be non-negative")
    plan, total = [], Fraction(0)
    for name, w, v in items:
        if w == 0 and v > 0:             # free value: take it, it uses no room
            plan.append((name, Fraction(1)))
            total += v
    rest = [it for it in items if it[1] > 0 and it[2] > 0]
    rest.sort(key=lambda it: Fraction(it[2], it[1]), reverse=True)
    room = Fraction(capacity)
    for name, w, v in rest:
        if room == 0:
            break
        take = min(Fraction(1), room / w)
        plan.append((name, take))
        total += take * v
        room -= take * w
    return total, plan

Sorting costs O(n log n) and dominates. The linear-time version follows the LP view: it searches for the critical ratio the way quickselect searches for a median. Pick a random pivot density, split items into denser, equal and less dense, and compare the weight of the denser group with the room left. If the denser items alone overflow the room, the threshold is among them and everything else can be discarded. Otherwise take them all, try the equal group, and if that still leaves room, recurse into the less dense group. Comparisons cross-multiply, v * pw > pv * w, which is exact for integers and avoids division entirely.

import random
from fractions import Fraction

def fractional_knapsack_linear(items, capacity):
    # Expected O(n): find the critical ratio by randomized selection.
    total = Fraction(sum(v for _, w, v in items if w == 0 and v > 0))
    cand = [(w, v) for _, w, v in items if w > 0 and v > 0]
    room = Fraction(capacity)
    while cand and room > 0:
        pw, pv = random.choice(cand)                         # pivot density pv/pw
        hi = [(w, v) for w, v in cand if v * pw > pv * w]   # denser than pivot
        eq = [(w, v) for w, v in cand if v * pw == pv * w]
        lo = [(w, v) for w, v in cand if v * pw < pv * w]
        w_hi = sum(w for w, _ in hi)
        if w_hi >= room:            # threshold is above the pivot: discard eq and lo
            cand = hi
            continue
        total += sum(v for _, v in hi)
        room -= w_hi
        w_eq = sum(w for w, _ in eq)
        if w_eq >= room:            # threshold is the pivot density
            return total + Fraction(pv, pw) * room
        total += sum(v for _, v in eq)
        room -= w_eq
        cand = lo                   # threshold is below the pivot
    return total

Each round discards a constant fraction of the candidates in expectation, so the expected total work is linear, the same argument as for quickselect. A deterministic median-of-medians pivot gives a worst-case linear bound at the cost of larger constants; in practice the randomised version or a plain sort is what people ship. Both listings above were checked against a brute-force solver that enumerates every LP vertex, on 3,000 random instances including zero weights, zero values and zero capacity, and agree on every one. The linear version returns only the value; recording the plan is a matter of keeping item names in the tuples.

Edge cases and numeric traps

• Zero capacity. The answer is the value of zero-weight items, and nothing else. Code that divides by remaining room breaks here.
• Zero weight. Density is infinite. Take every zero-weight item with positive value before anything else, and never divide by its weight.
• Zero or negative value. Zero-value items change nothing; skip them. Negative values do not belong in the standard problem; if your domain has costs, model them explicitly rather than letting them sort to the bottom.
• Total weight below capacity. Everything is taken and room is left over. That is a correct answer, not an error.
• Ties. Any order among equal densities is optimal for value, but not for the plan. If callers compare plans, for example in tests, break ties deterministically by name or index.
• Overflow. In Python integers are unbounded. In Java, C++ or Go, cross-multiplying two 64-bit values can overflow; use 128-bit arithmetic, a big-integer type, or bound the inputs.

Where it is used, and where it is not

The most important use is as a bound. Branch and bound for 0/1 knapsack explores decisions item by item and prunes any subtree whose best possible value cannot beat the best complete packing found so far. The fractional optimum of the remaining items in the remaining capacity is that best possible value; it is cheap to compute if items are pre-sorted by density, and it is tight enough that branch and bound with this bound solves many practical 0/1 instances quickly. The worked example shows why: the bound 153.2 is close to the true 0/1 optimum 146. The dynamic-programming and branch-and-bound treatments of 0/1 knapsack are in the knapsack family and dynamic programming.

As a model in its own right it fits divisible resources with linear returns, such as a budget split across channels with known value per pound up to a cap each. The cap is the item's weight; the density is its marginal return.

Know where the model stops. If returns diminish within an item, value is concave rather than linear, and the right algorithm equalises marginal returns across items, a water-filling procedure, rather than taking items whole in order. If there are two constraints, weight and volume for instance, the problem is a general LP and greedy by any single density can be wrong. And if items cannot be split, greedy by density is only a heuristic; compare it with the related exact greedy schedules in job sequencing with deadlines and Huffman coding to see what makes a greedy rule provably correct.

Failure modes

Trade-offs

Sort-and-scan is O(n log n), easy to verify, and the right default; it also leaves items sorted for branch and bound to reuse. Expected linear selection wins only when n is very large and the answer is needed once, so measure before adopting it. A heap built in O(n) and popped k times costs O(n + k log n), which beats sorting when capacity runs out after a few of many items. Exact arithmetic costs time but removes a class of bugs.

What to do next

1. Implement the sort-based version from memory with exact arithmetic and reproduce 153.2 on the example.
2. Write a brute-force checker that enumerates whole subsets plus one split item, and compare on random inputs including zero weights and zero capacity.
3. Implement the selection version and confirm it agrees with the sort on the same random inputs.
4. Use the fractional bound inside a branch-and-bound 0/1 solver and count how many nodes it prunes versus no bound.
5. For a real allocation problem, check that returns are linear and there is only one constraint before reaching for this algorithm.
6. Read the exchange proof again and adapt it to a greedy rule of your own; if the swap step fails, the greedy is probably wrong.