The 0/1 knapsack problem

You have a knapsack that holds at most W kilograms and n items, where item i weighs wi and is worth vi. Which items should you pack to carry the most value? It's called 0/1 because each item is either taken whole (1) or left behind (0); you can't take half of one.

Greedy ideas fail here. Taking the most valuable items first, or the best value per kilogram first, can leave awkward gaps. With capacity 10 and items (weight 6, value 30), (5, 20) and (5, 20), the best value per kilogram is the first item, but the two others together are worth 40. Trying every subset works, but there are 2n of them.

Knapsack of capacity 10 kg: greedy by value per kilogram packs the 6 kg item worth 30 and wastes 4 kg because neither 5 kg item fits; the best load is the two 5 kg items worth 40
Packing the best value-per-kilogram item first leaves a 4 kg gap; the two 5 kg items together are worth more.

The recurrence

Let best[i][w] be the largest value you can get using only the first i items with capacity w. Look at the last item, item i. Either you leave it out, and the best you can do is best[i-1][w], or it fits (wi ≤ w) and you take it. Then its value comes on top of the best use of the remaining capacity with the earlier items:

best[0][w] = 0                                  (no items)
best[i][w] = best[i-1][w]                       if w_i > w  (item i does not fit)
best[i][w] = max( best[i-1][w],                 skip item i
                  v_i + best[i-1][w - w_i] )    take item i

Each cell depends only on two cells in the row above, so the table can be filled row by row, left to right. In the animation, the cell being filled is outlined, the "skip" source is blue and the "take" source is green. The answer is the bottom-right cell, best[n][W].

Finding the items

The table gives the best value but not which items achieve it. To recover them, start at best[n][W] and walk up. If a cell has the same value as the cell above it, the item for that row wasn't needed, so move straight up. If it differs, the item was taken: record it and move up and left by its weight. The animation colors the cells on that walk yellow and the chosen items green.

Running time

The table has (n + 1)(W + 1) cells and each takes constant time, so the algorithm runs in Θ(nW) time and space. Only the previous row is needed to fill the next one, so the space can drop to Θ(W) if you only want the value.

Θ(nW) looks polynomial, but it isn't polynomial in the size of the input: writing W down takes only about lg W digits, so doubling the number of digits squares the running time. That is called pseudo-polynomial time, and it is consistent with 0/1 knapsack being NP-hard: no known algorithm is polynomial in n and lg W.

Worked example

Capacity W = 5 and three items: A (weight 1, value 1), B (weight 3, value 4), C (weight 4, value 5). Each row adds one more item; each cell is max(skip, take):

                 w = 0   1   2   3   4   5
none               0   0   0   0   0   0
≤ A  (1, 1)        0   1   1   1   1   1     take A as soon as it fits: 1 + best[0][w-1] = 1
≤ B  (3, 4)        0   1   1   4   5   5     w=3: max(1, 4 + best[1][0]) = 4
                                             w=4: max(1, 4 + best[1][1]) = 5   (B and A)
≤ C  (4, 5)        0   1   1   4   5   6     w=5: max(5, 5 + best[2][1]) = 6   (C and A)

The answer is best[3][5] = 6. Walking back: best[3][5] = 6 ≠ best[2][5] = 5, so C was taken and the remaining capacity is 5 − 4 = 1; best[2][1] = best[1][1] = 1, so B was not; best[1][1] = 1 ≠ best[0][1] = 0, so A was taken. The best load is A + C: weight 5, value 6.

Knapsack table for capacity 5 and items A (1 kg, 1), B (3 kg, 4), C (4 kg, 5). Cell best[3][5] = max(skip C = 5 from the cell above, take C = 5 + best[2][1] = 6) = 6. The walk back goes from best[3][5] to best[2][1] (C taken), up to best[1][1] (B not taken), then to best[0][0] (A taken)
Each cell is the better of skipping the item (cell above) or taking it (value plus the cell above, its weight to the left); walking back reads off A + C.

Compare the greedy rule "best value per kilogram first": B (1.33 per kg), then C (1.25) no longer fits, then A (1.0) does, for a value of only 5. That is why 0/1 knapsack needs dynamic programming, while the fractional knapsack, where you may take part of an item, is solved exactly by that greedy rule.

Common mistakes and variants

  • Table size: capacities run from 0 to W, so each row has W + 1 cells, and row 0 (no items) is all zeros.
  • One-row version: with a single array, loop w from W down to wi. Looping upwards reads cells that already include item i, so the item can be taken several times. That is exactly the unbounded knapsack, where each item has unlimited copies.
  • Recovering the items needs the full table (or a separate "taken" flag per cell); the one-row version only gives the value.
  • If only whether some subset reaches weight exactly W matters, the same table with booleans solves subset sum.