A knapsack holds a limited weight. Each item has a weight and a value, and you either pack it or you don't: no fractions, no duplicates (that's the "0/1"). Which items give the most value without going over the limit? The same shape appears in budgeting, cargo loading and picking which jobs to run on a machine with limited time.
Trying every subset takes 2n steps. The obvious greedy rule, "best value per kg first", is fast but can be wrong, as the example below shows.
As with edit distance, solve smaller versions of the problem first and store them in a table. Row i allows only the first i items; column c is the capacity. For each cell, the new item is either skipped or taken:
Looking in the row above when taking is what makes each item usable once. Using the item's own row would allow packing it again.
Start at the bottom-right cell and walk up a row at a time. If a cell equals the one above, its item wasn't needed: go straight up. Otherwise the item was packed: move left by its weight. When both explain the value, these pages leave the item out, so each step has one right answer.
| 0/1 knapsack by dynamic programming | |
|---|---|
| Time and space | O(n · W) for n items and capacity W |
| Fine print | That's fast for small W, but W can be huge: the problem is NP-hard in general, and this is called a pseudo-polynomial algorithm. |
| Fractions allowed? | Then greedy by value per kg is optimal: take the best items whole, and a fraction of the next. |