0/1 Knapsack Problem, in depth: the table as a picture, rows as staircases, Pareto lists, choosing between tied optima and an event trace for animation and debugging

The recurrence in one paragraph

Number the items 1 to n. Let dp[i][w] be the best value achievable using only the first i items with total weight at most w. Item i is either left out, giving dp[i-1][w], or taken, which is only legal when its weight wt fits and gives dp[i-1][w - wt] + v. The cell holds the larger of the two. Row 0 is all zeros, the answer is dp[n][W], and filling the table costs O(nW) time.

The 0/1 part lives in the index i - 1 on the take branch: taking item i looks up a row that has never seen item i, so it cannot be taken twice. Read at most w carefully too. Because row 0 is all zeros rather than minus infinity for w greater than 0, unused capacity is allowed, and each row is non-decreasing in w. That one property is what the rest of this article exploits.

def knapsack_table(items, W):
    """items: list of (name, weight, value). Returns the full (n+1) x (W+1) table."""
    dp = [[0] * (W + 1)]
    for _, wt, v in items:
        prev = dp[-1]
        dp.append([max(prev[w], prev[w - wt] + v) if wt <= w else prev[w]
                   for w in range(W + 1)])
    return dp

Worked example: the whole table

Use five items and capacity 9: A (weight 2, value 3), B (3, 4), C (4, 5), D (5, 8) and E (3, 5). Row i adds one item to what was available on row i-1. The table below was computed by the function above, and the figure shows it with the cells where taking the new item helped shaded green.

Read row C at w = 9: leaving C out gives 7 (row B), taking it gives row B at w = 5, which is 7, plus 5, so 12. Read row D at w = 9: leaving D out gives 12, taking it gives row C at w = 4 plus 8, which is 13. Row E at w = 9 stays at 13, because taking E gives row D at w = 6 plus 5, also 13, not more. The answer is 13.

To recover the items, walk up from dp[5][9]. If a cell equals the cell above it, the item was not needed; otherwise it was taken, so subtract its weight and move up. Row E: 13 equals 13, skip E. Row D: 13 differs from 12, take D, move to w = 4. Row C: 5 differs from 4, take C, move to w = 0. The packing is C and D, weight 9, value 13.

Every row is a staircase

Look along any row of the table. The values never decrease and they change only at a few positions: row B is 0, 0, 3, 4, 4, 7, 7, 7, 7, 7. Plotted against w it is a staircase. Row i is the function f_i(w) = max value with capacity w, and the recurrence is an operation on whole functions: shift f_{i-1} right by wt, lift it by v, and take the pointwise maximum with the unshifted f_{i-1}.

This view explains three things at once. It explains why the one-row version of the algorithm must loop w downward: an upward loop would read cells already lifted by the current item, which is the shift-and-max applied repeatedly, which is the unbounded knapsack. It explains why the capacity axis can be enormous while the interesting information is small: only the corners of the staircase matter. And it explains the animation everyone draws, a row being built by sliding a copy of the row above to the right and keeping the higher of the two curves.

Storing only the corners: Pareto lists

A corner of the staircase is a pair (weight, value) that is not dominated: no other reachable packing is at most as heavy and at least as valuable. Keep only those pairs, sorted by weight, and you have the whole row. The update for a new item is the staircase operation on lists: shift every pair by (wt, v), merge with the old list, drop anything over capacity, and remove dominated pairs with one sweep that keeps a pair only if its value beats every lighter pair.

def pareto_knapsack(items, W):
    """Keep only non-dominated (weight, value) pairs. Returns the final list."""
    frontier = [(0, 0)]
    for _, wt, v in items:
        shifted = [(a + wt, b + v) for a, b in frontier if a + wt <= W]
        merged = sorted(frontier + shifted, key=lambda t: (t[0], -t[1]))
        frontier, best = [], -1
        for a, b in merged:              # weights ascending, ties: highest value first
            if b > best:                 # strictly better than every lighter pair
                frontier.append((a, b))
                best = b
    return frontier                      # last pair holds the optimum

After all five items the frontier has 7 pairs, against 50 table cells. That ratio is the point. With integer weights in the millions, the table is out of the question but the frontier often stays small, because only distinct best values can appear on it. Its size is bounded by min(2^i, W + 1, number of distinct values), so it is never worse than the table in the worst case, and on random instances it is typically far smaller; Nemhauser and Ullmann's 1969 list method is this algorithm, and later probabilistic analyses explain why random instances behave so well. Weights can even be real numbers, which the table cannot handle at all.

Note one subtlety in the sweep: ties on weight must be sorted by value descending, otherwise a dominated pair such as (5, 7) survives next to (5, 8).

Ties: which optimum do you want?

The table has more than one optimum here, and backtracking from dp[5][9] silently picks one of them. Row E reaches 13 at w = 8 already: backtracking from dp[5][8] gives D and E, weight 8. Both packings are worth 13; the second leaves one unit of capacity free. Which one is right depends on the application, and the code should say so explicitly instead of inheriting whatever the loop order happens to produce.

• Lightest optimum: backtrack from the smallest w with dp[n][w] equal to dp[n][W]. Useful when leftover capacity has value, such as headroom in a memory budget.
• Fewest items: carry a second key, the item count, and compare (value, -count) tuples in the max.
• All optima: backtrack recursively, following both branches when they tie. The count can be exponential, so cap it.

Turning the algorithm into an animation trace

An animation, a step-through debugger and a test oracle all want the same thing: a sequence of events describing what the algorithm read and wrote. Writing the algorithm as a generator that yields those events keeps a single implementation and lets any front end consume it.

def knapsack_trace(items, W):
    """Yield one event per cell, then the backtrack. The caller decides how to draw it."""
    dp = [[0] * (W + 1) for _ in range(len(items) + 1)]
    for i, (name, wt, v) in enumerate(items, start=1):
        for w in range(W + 1):
            skip = dp[i - 1][w]
            take = dp[i - 1][w - wt] + v if wt <= w else None
            dp[i][w] = skip if take is None or take <= skip else take
            yield {"type": "cell", "i": i, "w": w, "item": name,
                   "reads": [(i - 1, w)] + ([(i - 1, w - wt)] if take is not None else []),
                   "skip": skip, "take": take, "value": dp[i][w],
                   "took": take is not None and take > skip}
    w = W
    for i in range(len(items), 0, -1):
        took = dp[i][w] != dp[i - 1][w]
        yield {"type": "back", "i": i, "w": w, "took": took, "item": items[i - 1][0], "value": dp[i][w]}
        if took:
            w -= items[i - 1][1]

import json
events = list(knapsack_trace([("A",2,3), ("B",3,4), ("C",4,5), ("D",5,8), ("E",3,5)], 9))
print(len(events))                       # 50 cell events + 5 backtrack events = 55
json.dump(events, open("trace.json", "w"))

A renderer needs very little: highlight the cells in reads, write value into the current cell, colour it if took is true, and pause. The reads field is the important one for teaching, because it makes the dependency visible: every cell looks straight up and diagonally up-left by exactly the item's weight.

Debugging with the trace

The trace is also a precise debugging tool, because the classic knapsack bugs each leave a distinctive signature in it.

• Forward loop in the one-row version. Record which item lifted each cell; if any backtrack path takes the same item twice, the loop ran upward. On this instance the upward loop returns 15, from E taken three times, which is impossible for 0/1.
• Exactly-W initialisation by accident. If row 0 is filled with minus infinity except at w = 0, rows are no longer monotone. Assert that every row of the traced table is non-decreasing when you want the at-most semantics.
• Backtrack from the wrong cell. Starting the walk at dp[n][W] with a table built for exact capacity can land on minus infinity. Check that the first back event has a finite value.

Pair these assertions with a brute-force oracle over all 2^n subsets for n up to about 20, and run both on a few thousand random instances. That combination finds essentially every implementation bug in minutes.

Choosing a method

The capacity axis that the table depends on is the pseudo-polynomial trap: O(nW) looks polynomial, but W is a number, not a size: each extra bit in W doubles the work while the input grows by one bit. When the subject is a subset that hits a sum exactly, the partition and subset-sum pages show the boolean version of the same table, and when there are several capacity constraints at once, see multi-dimensional knapsack.

Failure modes

• Memory blow-up. A full table for n = 10,000 and W = 10^6 is 10^10 cells. Keep only the row unless you need reconstruction, and reconstruct with a divide-and-conquer method or the Pareto list's back pointers.
• Scaling weights to make W small. Dividing weights by 1,000 and rounding can make an infeasible packing look feasible. Round weights up, never down, and re-check the final packing with the true weights.

What to do next

1. Type in knapsack_table and reproduce the table above by hand for rows A and B, then let the code finish it.
2. Change the backtrack to start from the lightest optimal capacity and confirm you get D and E.
3. Implement pareto_knapsack, print the frontier after each item, and check its last pair against the table.
4. Write the trace generator and replay it in a terminal: print the row after each item with the updated cells marked.
5. Introduce the upward loop bug in a one-row version and use the trace to catch the item taken twice.
6. Add a brute-force oracle and compare all three methods on 1,000 random instances with n at most 15.
7. Pick the method for your real problem from the table above, based on n, W and whether weights are integers.