DP: 0/1 Knapsack
Medium+95 XPPack a weight-limited bag for maximum value by filling a 2D best-value table.
No visualization loaded.
Watch
—
Press Run to begin.
You have a bag that can hold only so much weight, and a pile of items each with a weight and a value. You want the most valuable load that still fits. The trick: for every item you face exactly two choices — leave it OR take it (you can't take half). So you build a table where each cell asks 'with these items and this much room left, what's the best value?' and answers it using two cells you already filled in: the 'skip it' answer and the 'take it' answer. Keep whichever is bigger.
▸Why is it called '0/1' knapsack?
Because each item is all-or-nothing: you take it once (1) or not at all (0). You can't take a fraction of an item or two copies. That's what makes a table the right tool — at each item there are exactly two branches to compare.
▸What do the two highlighted cells mean when a new cell lights up?
They're the two pasts you're choosing between. The cell directly ABOVE = the best value if you SKIP this item (same budget, one fewer item). The cell up-and-to-the-LEFT (left by this item's weight) = the best value BEFORE you spent room on this item, to which you add its value if you TAKE it. The new cell is just the larger of those two.
▸Why not just try every possible combination of items?
With n items there are 2ⁿ combinations — that doubles every time you add an item, so it explodes. The table reuses overlapping answers (lots of combinations share the same 'first 3 items, 5kg left' subproblem), so each (item, budget) pair is solved exactly once. That's O(n × capacity) instead of O(2ⁿ).
▸Why does the base (top) row hold all zeros?
That row means 'zero items chosen so far.' With nothing to pack, the best value is 0 for every budget — there's nothing to take. Every later cell is built on top of this honest starting point.
▸Where's the final answer in the table?
The bottom-right cell: all items considered, full budget available. Reading it tells you the best value; you could walk back up through the choices to recover WHICH items were taken, but the value itself is just that one corner cell.
How the work grows
O(n × W) is slow — explodes on big inputs. You fill one cell for every (item, budget) pair: n items times W budget = n×W cells, each computed in O(1) from two earlier cells. That's the pseudo-polynomial table cost. Brute-forcing every subset is O(2ⁿ) — the runaway curve the table replaces. Memory is the table itself, n×W cells.
Faint dotted lines = O(1) (flat) and O(n) (straight) for comparison.