0/1 knapsack
Each item has a weight and a value, and the bag has a weight limit. For every item and every amount of room, decide: leave the item out and keep the best answer without it, or put it in and add its value to the best answer for the room left over. The table remembers every one of those answers.
empty table
Pack items into a bag that holds weight 7, for the most total value. Each item goes in whole or not at all.
1function knapsack(items, capacity) {2 const dp = Array.from({ length: items.length + 1 }, () => new Array(capacity + 1).fill(0));3 for (let i = 1; i <= items.length; i++) {4 const [w, v] = items[i - 1];5 for (let c = 0; c <= capacity; c++) {6 dp[i][c] = dp[i - 1][c];7 if (w <= c) dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - w] + v);8 }9 }10 return dp[items.length][capacity];11}Keys: Space play or pause, ← → step. The URL always points at the frame you are on.
What it costs
| Case | Time | When |
|---|---|---|
| best | n · W | every cell: n items by W + 1 capacities |
| average | n · W | any items |
| worst | n · W | big capacities make the table huge |
| space | n · W | the table; one row is enough for the value alone |
Where it breaks
- Greedy by value per weight fails. Pick Greedy trap: the 5-weight item is worth the most per unit of weight, but after taking it nothing else fits, for 11. The table finds 13 from the other two.
- "Polynomial" with a catch. n · W looks fast, but W is a number, not a count. A capacity of a billion makes a billion columns. The problem is still hard in general; this table only helps when W is small.
- Each item at most once. Reading the previous row,
dp[i − 1], is what stops an item being packed twice. Read the current row instead and you get the unbounded version, where items repeat.