Tools Suite

Dynamic programming

O(n · W)·O(n · W) space
Whole table

Drag to pan; pinch or Ctrl+scroll to zoom, which stops at the whole table; arrow keys pan once the picture has focus. The headers stay put while you pan.

no items, capacity 0, not yet filledno items, capacity 1, not yet filledno items, capacity 2, not yet filledno items, capacity 3, not yet filledno items, capacity 4, not yet filledno items, capacity 5, not yet filledno items, capacity 6, not yet filledno items, capacity 7, not yet filleditem 1, 1 kg worth £1, capacity 0, not yet filleditem 1, 1 kg worth £1, capacity 1, not yet filleditem 1, 1 kg worth £1, capacity 2, not yet filleditem 1, 1 kg worth £1, capacity 3, not yet filleditem 1, 1 kg worth £1, capacity 4, not yet filleditem 1, 1 kg worth £1, capacity 5, not yet filleditem 1, 1 kg worth £1, capacity 6, not yet filleditem 1, 1 kg worth £1, capacity 7, not yet filleditem 2, 3 kg worth £4, capacity 0, not yet filleditem 2, 3 kg worth £4, capacity 1, not yet filleditem 2, 3 kg worth £4, capacity 2, not yet filleditem 2, 3 kg worth £4, capacity 3, not yet filleditem 2, 3 kg worth £4, capacity 4, not yet filleditem 2, 3 kg worth £4, capacity 5, not yet filleditem 2, 3 kg worth £4, capacity 6, not yet filleditem 2, 3 kg worth £4, capacity 7, not yet filleditem 3, 4 kg worth £5, capacity 0, not yet filleditem 3, 4 kg worth £5, capacity 1, not yet filleditem 3, 4 kg worth £5, capacity 2, not yet filleditem 3, 4 kg worth £5, capacity 3, not yet filleditem 3, 4 kg worth £5, capacity 4, not yet filleditem 3, 4 kg worth £5, capacity 5, not yet filleditem 3, 4 kg worth £5, capacity 6, not yet filleditem 3, 4 kg worth £5, capacity 7, not yet filleditem 4, 5 kg worth £7, capacity 0, not yet filleditem 4, 5 kg worth £7, capacity 1, not yet filleditem 4, 5 kg worth £7, capacity 2, not yet filleditem 4, 5 kg worth £7, capacity 3, not yet filleditem 4, 5 kg worth £7, capacity 4, not yet filleditem 4, 5 kg worth £7, capacity 5, not yet filleditem 4, 5 kg worth £7, capacity 6, not yet filleditem 4, 5 kg worth £7, capacity 7, not yet filledcapacity 00capacity 11capacity 22capacity 33capacity 44capacity 55capacity 66capacity 77no items—noneitem 1, 1 kg worth £11 kg£1item 2, 3 kg worth £43 kg£4item 3, 4 kg worth £54 kg£5item 4, 5 kg worth £75 kg£7→ capacity↓ item

The table has 5 rows and 8 columns, and nothing has been worked out yet. Each item is taken whole or left behind, so every cell has exactly two possibilities to compare.

The table has 5 rows and 8 columns, and nothing has been worked out yet. Each item is taken whole or left behind, so every cell has exactly two possibilities to compare.
Answer so far—

K(i, w) = max( K(i−1, w), value(i) + K(i−1, w − weight(i)) )

  1. 1fill the first row and the first column with zeroes: no items, or no room, is worth nothing
  2. 2read the cell directly above, which is leaving this item out
  3. 3this item is heavier than the capacity, so leaving it is the only option
  4. 4also read the cell one row up and its weight to the left, then add its value: that is taking it
  5. 5write the better of the two, and remember which it was
  6. 6walk back: wherever the value differs from the cell above, that item was taken
  7. 7stop: the bottom-right cell is the best the knapsack can hold
Cells filled
0
Cells read
0
Values written
0
Items too heavy
0

Complexity

BestO(n · W)
AverageO(n · W)
WorstO(n · W)
Extra spaceO(n · W)
2 · items × capacity at n=40 predicts 80; this run took 0.

0/1 knapsack

Each item is taken whole or not at all, which is what the 0/1 means. Consider the items one at a time and every capacity from nothing up to the limit. For each pair there are exactly two possibilities: leave this item, which is the answer for the same capacity one row up; or take it, which is its value plus the answer one row up for the capacity that is left over. The better of the two goes in the cell.

Its recurrence

K(i, w) = max( K(i−1, w), value(i) + K(i−1, w − weight(i)) )

When it is the right choice

Any allocation with a hard limit and indivisible choices: which features fit in a release, which jobs fit in a budget, which files fit on a disc. The fact that it is O(n · W) rather than polynomial in the size of the input is worth knowing — the capacity is a number, and a number written down takes only log W digits, which is what makes this problem NP-hard in the strict sense and this algorithm merely useful.

How it works

Worth noticing

Cost

Best
O(n · W)
Average
O(n · W)
Worst
O(n · W)
Extra space
O(n · W)
Table
two dimensions
Accepts
1 to 8 items, each from 1 to 12; capacity from 1 to 24

The limits are pedagogical rather than technical: this tool keeps the whole table in every recorded step, so the shape of the table sets the size of the trace directly, and a run has to stay short enough to sit and watch. An input that would take more than three thousand steps on this algorithm is refused before a single step is generated, from a formula in the input sizes rather than by running it and finding out.

An unfilled cell is drawn differently from a cell holding a zero — no fill, a dashed outline, and no number at all — because early in a run that difference is most of the picture.

Worth comparing

All dynamic programming algorithms