Take It or Leave It: the Knapsack
One last problem, and it is the one that gets asked about most often. A bag that holds a fixed weight, a pile of items each with a weight and a value, and a rule that every item is either in the bag or out of it. No taking half of something.
The 0/1 knapsack earns a tutorial of its own because of what the second axis turns into here. In the last tutorial that axis was a second sequence. Here it is a resource you are spending, and once you have seen that version, a whole family of problems that look unrelated turn out to be the same table with the arrows moved.
Why the obvious approaches fail
The tempting move is to sort the items by value and take greedily, or to sort them by value per unit of weight and take greedily. Both are wrong, and both are wrong for the same reason. An item that looks excellent on its own can crowd out a pair that would have been better together, and no amount of sorting sees that coming. Sorting cannot see a pair.
The opposite extreme is to try every subset, which is correct and hopeless. With n items there are 2 to the power of n subsets, so forty items gives roughly a trillion, and the shape of that number is the same one the second tutorial in this section spent its time on.
The state
A call in the brute-force version is deciding exactly one thing: does item i go in the bag? To settle that you have to know two things, which items are still on the table and how much room is left, and there is nothing else that could possibly matter.
That hands you the state directly. Cell (i, c) holds the best value obtainable from the first i items with a bag of capacity c. Nothing else needs tracking, because those two numbers already pin down every choice made so far.
The rule is the two-way decision from the house problem with a weight check bolted on. Leave item i out and the value is whatever the first i minus 1 items managed at the same capacity, which is the cell directly above. Take it and you collect its value, then land one row up and several columns to the left, at capacity c minus the item's weight. Keep the larger of the two. If the item weighs more than c there is nothing to compare, and the cell copies the one above it.
The widget below packs a bag of capacity 7 from four items. Each row adds one more item to what you are allowed to consider.
best(0,c) = 0 · if the item is too heavy: best(r,c) = best(r - 1, c) · otherwise: best(r,c) = max(best(r - 1, c), value(r) + best(r - 1, c - weight(r)))
across: bag capacity|down: items available
Each row adds one more item to the shelf. A cell either matches the row above it, meaning the item was left behind, or beats it, meaning the item went in.
With no items to choose from, every bag size is worth nothing.
Read a row as a bigger shelf rather than a bigger bag. The columns are capacities and the rows are how many items are on offer, so moving down a row means one more item became available while the bag stayed the same size. A cell either matches the cell above it, meaning that item was left behind, or beats it, meaning the item went in.
That is also how the traceback works, and it is simpler here than on the grid. Walk up the rows starting from the corner. Every time a cell differs from the one directly above it, the item belonging to that row is in the bag, so subtract its weight from the capacity and carry on upward. Every time the two match, that item was skipped.
Pseudo-polynomial, and why the word matters
The table has n rows and W plus 1 columns, where W is the capacity, so the whole thing costs n times W. That looks polynomial, and it very nearly is, and the gap between very nearly and actually is the sort of distinction that sounds pedantic right up until the moment it bites.
The size of an input is measured by how many symbols it takes to write down. Writing a capacity of one billion takes ten digits, and the table for it is a billion columns wide. Add one more digit and the table gets ten times wider while the input grew by a single character. Growing tenfold per character of input is exponential growth, measured the way complexity theory measures it, and an algorithm that does this is called pseudo-polynomial.
In practice the rule of thumb is short. The table is fine when capacities are small and useless when they are large. A bag measured in grams is comfortable, and the same bag measured in micrograms has a table a million times wider holding exactly the same problem. Units matter here.
The family it belongs to
| Problem | What changes about the table |
|---|---|
| Subset sum | values equal weights, and you only ask whether a total is reachable |
| Partition into two equal halves | subset sum aimed at half the total |
| Unbounded knapsack | taking an item reads the same row, since it is still available after |
| Fewest coins | unbounded knapsack, minimizing a count instead of maximizing a value |
Those are not four algorithms. They are one table with its arrows moved, and seeing that is most of what being comfortable with this topic amounts to. Learn the table, not the four names.
The unbounded row repays a second reading. Taking an item there reads the current row rather than the row above, because the item is still on the shelf afterwards, and that single change is the entire difference between taking something once and taking it as often as you like. It is one subscript.
Where to go from here
This section has been one idea told four ways. A recursion is correct because of induction. It is slow when it keeps asking the same question. Storing answers repairs that from the top down, filling a table repairs it from the bottom up, and the only genuinely difficult part is deciding what a single cell should mean.
What comes next is practice, and there is one piece of advice about practice worth taking seriously. Every problem in this section has a brute-force version that is short, obviously correct, and far too slow, so write both and run them against each other on small inputs. Agreement there is not a proof. But it catches nearly every bug a subtly wrong recurrence produces, since those bugs tend to show up long before the input gets large.
The backtracking section is the natural companion to this one, since a backtracking search with a store bolted onto it is a dynamic programming solution, and several of the problems over there become tractable the moment you notice that. The sorting section is worth a second visit too, because merge sort and quick sort are the divide and conquer half of the picture this section has been drawing.