Dynamic programming

Greed fails on 0/1 knapsack because the value of taking an item depends on what best fills the capacity it leaves, which is not known when the choice has to be made.

The obvious response is to stop choosing and try both branches, take the item or leave it, and keep whichever turns out better. Done directly that is $2^{n}$ subsets and hopeless. This lesson shows that it is not hopeless at all, because the recursion asks the same questions over and over, and that answering each question once turns an exponential algorithm into a polynomial one, at the cost of a table.

The same subproblem, again and again

The clearest demonstration needs no optimisation at all. Define $F (n) = F (n - 1) + F (n - 2)$ with $F (0) = 0$ and $F (1) = 1$ , and compute it by writing exactly that as a recursive function.

Count the calls. The call tree for $F (5)$ contains $F (3)$ twice, $F (2)$ three times, $F (1)$ five times. In general the number of calls satisfies the Fibonacci recurrence itself, so it grows like $φ^{n}$ . Computing $F (40)$ makes 331,160,281 calls, about a third of a second on a modern machine. $F (50)$ makes 40,730,022,147, forty seconds. $F (100)$ would outlast the machine.

Yet there are only 101 distinct values in play. The algorithm is exponential purely because it recomputes the same answers, and this is the condition that dynamic programming exploits, called overlapping subproblems: the recursion visits a small set of distinct subproblems an enormous number of times.

Overlapping subproblems is not the same as the divide-and-conquer situation. Mergesort's two halves are disjoint and share nothing, so there is nothing to reuse and no table would help. Dynamic programming applies when the subproblems overlap and the problem has optimal substructure, the same property that licensed greedy recursion. Both are needed: overlap without optimal substructure gives nothing to combine, and optimal substructure without overlap is just divide and conquer.

There are two ways to exploit it. Memoisation keeps the recursion and adds a cache: before computing, look the subproblem up; after computing, store it. Bottom-up tabulation discards the recursion, works out the order in which subproblems depend on each other, and fills a table in that order with loops.

Memoisation is easier to write from a working recursion and computes only the subproblems actually reached. Tabulation avoids the call overhead, has predictable memory access, and often allows the table to be shrunk, since a row may depend only on the row above. Both turn $φ^{n}$ into $n$ for Fibonacci: 39 additions rather than 331 million calls, a factor of eight million at $n = 40$ .

Rod cutting

Now a real optimisation. A rod of length $n$ can be cut into whole-number pieces, and a piece of length $i$ sells for $p_{i}$ . Maximise the revenue.

There are $2^{n - 1}$ ways to cut, one for each subset of the $n - 1$ internal positions, so enumeration is out. The recursive structure is: the leftmost piece has some length $i$ between 1 and $n$ , and whatever it is, the rest of the rod should be cut optimally. So

r (n) = \max_{1 \leq i \leq n} (p_{i} + r (n - i))

with $r (0) = 0$ . That is optimal substructure stated directly, and the subproblems overlap heavily: $r (n - 1)$ is needed by $r (n)$ , by $r (n + 1)$ , and so on. Filling $r (0)$ upwards to $r (n)$ costs $Θ (n^{2})$ , since computing $r (k)$ examines $k$ options.

Example. Pieces of length 1 to 8 sell for 2, 5, 7, 8, 10, 17, 17 and 20. Fill the table and find the best revenue for a rod of length 8.

$r (1) = 2$ . $r (2) = \max (2 + r (1), 5) = \max (4, 5) = 5$ . $r (3) = \max (2 + 5, 5 + 2, 7) = 7$ . $r (4) = \max (2 + 7, 5 + 5, 7 + 2, 8) = 10$ . $r (5) = \max (2 + 10, 5 + 7, 7 + 5, 8 + 2, 10) = 12$ . $r (6) = \max (2 + 12, 5 + 10, 7 + 7, 8 + 5, 10 + 2, 17) = 17$ . $r (7) = \max (2 + 17, 5 + 12, 7 + 10, 8 + 7, 10 + 5, 17 + 2, 17) = 19$ . $r (8) = \max (2 + 19, 5 + 17, 7 + 12, 8 + 10, 10 + 7, 17 + 5, 17 + 2, 20) = 22$ .

So 22, from a piece of length 2 and a piece of length 6, worth $5 + 17$ . Note that selling the whole 8 fetches only 20, and that the greedy rule of taking the best price per unit length would pick length 6 at 2.83 per unit first, then length 2 at 2.50, reaching 22 here by luck; change $p_{6}$ to 16 and greed picks 6 then 2 for 21 while the optimum is $r (8) = 21$ as well. Greed is not reliably wrong, it is merely unproved.

Now you. With the same prices, what is $r (9)$ if a length-9 piece sells for 24?

Answer

$r (9) = \max (p_{1} + r (8), p_{2} + r (7), p_{3} + r (6), p_{4} + r (5), p_{5} + r (4), p_{6} + r (3), p_{7} + r (2), p_{8} + r (1), 24)$ , which is $\max (2 + 22, 5 + 19, 7 + 17, 8 + 12, 10 + 10, 17 + 7, 17 + 5, 20 + 2, 24) = 24$ . Five different decompositions tie at 24, including the uncut rod. Ties are common and harmless: the algorithm returns a maximum, and any decomposition attaining it is a correct answer.

0/1 knapsack

Now the problem greed could not solve. Items $1$ to $n$ with weights $w_{i}$ and values $v_{i}$ , a bag of capacity $W$ , each item taken whole or not at all.

The subproblem needs two parameters, and identifying them is the real work. Let $K (i, w)$ be the best value obtainable from the first $i$ items with capacity $w$ . Item $i$ is either left out, giving $K (i - 1, w)$ , or taken, which is only possible if $w_{i} \leq w$ and gives $v_{i} + K (i - 1, w - w_{i})$ . So

K (i, w) = \max (K (i - 1, w), v_{i} + K (i - 1, w - w_{i}))

with $K (0, w) = 0$ and the second branch dropped when the item does not fit. The table has $(n + 1) (W + 1)$ cells and each costs constant work, so the whole thing is $Θ (n W)$ .

Example. A bag holds 8 kg. The items are (3 kg, 4), (4 kg, 5), (2 kg, 3) and (5 kg, 6). Fill the table and find the best value.

Row 0 is all zeros. Row 1, with only the 3 kg item, is 0 for capacities 0 to 2 and 4 from capacity 3 onwards. Row 2 adds the 4 kg item: capacities 0 to 2 stay 0, capacity 3 stays 4, capacities 4 to 6 give 5, and capacity 7 gives $4 + 5 = 9$ , as does capacity 8. Row 3 adds the 2 kg item: capacity 2 becomes 3, capacity 3 stays 4, capacity 4 stays 5, capacity 5 becomes $3 + 4 = 7$ , capacity 6 becomes $3 + 5 = 8$ , and capacities 7 and 8 stay 9. Row 4 adds the 5 kg item and changes only capacity 8, to $6 + K (3, 3) = 6 + 4 = 10$ . The answer is 10.

Now you. A bag holds 9 kg, with items (2 kg, 3), (3 kg, 4), (4 kg, 5) and (5 kg, 6).

Answer

The final answer is 12. Working the last row: $K (4, 9) = \max (K (3, 9), 6 + K (3, 4))$ , which is $\max (12, 6 + 5) = 12$ , so the 5 kg item is left out. The first three items weigh $2 + 3 + 4 = 9$ exactly and are worth $3 + 4 + 5 = 12$ . Note that the ratio rule would have taken the 2 kg item first at 1.5 per kg, then the 3 kg at 1.33, then the 4 kg at 1.25, arriving at the same answer here; it is the previous lesson's instances, not all of them, where it goes wrong.

Reading the answer back

The table holds the value of the optimum, not the optimum itself, and the choices have to be recovered. Two ways.

Store a decision alongside each cell as it is filled, which costs memory but makes recovery a direct walk. Or reconstruct from the values alone, which costs nothing extra: start at $K (n, W)$ and compare it with $K (n - 1, W)$ . If they differ, item $n$ must have been taken, so record it and move to $K (n - 1, W - w_{n})$ ; if they agree, item $n$ was not needed, so move to $K (n - 1, W)$ . Repeat down to row 0.

On the first knapsack example: $K (4, 8) = 10$ and $K (3, 8) = 9$ , so item 4 was taken, leaving $K (3, 3)$ . $K (3, 3) = 4$ and $K (2, 3) = 4$ , so item 3 was not taken; nor was item 2, since $K (2, 3) = K (1, 3) = 4$ . $K (1, 3) = 4$ against $K (0, 3) = 0$ , so item 1 was taken. The packing is items 1 and 4, weighing $3 + 5 = 8$ and worth $4 + 6 = 10$ .

Edit distance

The best-known table in this family compares two strings. The edit distance between them, from Vladimir Levenshtein in 1965, is the fewest single-character insertions, deletions and substitutions turning one into the other.

Let $D (i, j)$ be the distance between the first $i$ characters of $a$ and the first $j$ of $b$ . Consider the last operation performed. It either deleted $a_{i}$ , costing $1 + D (i - 1, j)$ ; or inserted $b_{j}$ , costing $1 + D (i, j - 1)$ ; or aligned $a_{i}$ with $b_{j}$ , costing $D (i - 1, j - 1)$ plus 1 if the characters differ and 0 if they match. Take the minimum of the three. The base cases are $D (i, 0) = i$ and $D (0, j) = j$ , since an empty string needs one operation per character.

The table is $(m + 1) (n + 1)$ cells filled in $Θ (m n)$ time, and only the previous row is ever needed, so the space can be cut to $Θ (\min (m, n))$ if the alignment itself is not wanted.

Example. What is the edit distance between "kitten" and "sitting"?

Filling the table row by row gives 3, and the path shows what the operations are: substitute k with s, substitute e with i, and insert g at the end. Spot-checking one interior cell, $D (3, 3)$ compares "kit" with "sit" and is 1, which is right: one substitution.

Now you. Compute the edit distance between "sunday" and "saturday".

Answer

The route is "sunday" to "saunday" by inserting a, to "satunday" by inserting t, to "saturday" by substituting r for n. The table gives the count without finding that alignment first, which is the point of filling a table rather than searching for a sequence of edits: the search space of edit sequences is enormous and the table has $7 \times 9 = 63$ cells.

Longest common subsequence is the same table with a different recurrence, and it is what diff computes: the unchanged lines are the longest common subsequence of the two files, and the added and removed lines are everything else. Sequence alignment in bioinformatics is the same table again, with a scoring matrix in place of the unit costs.

The cost, and the crack in it

The pattern is now visible. Identify the subproblem and its parameters, write the recurrence, decide the fill order, and the running time is the number of table cells times the work per cell. Rod cutting has $n$ cells at $Θ (n)$ work each, so $Θ (n^{2})$ . Knapsack has $n W$ cells at constant work, so $Θ (n W)$ . Edit distance has $m n$ cells at constant work, so $Θ (m n)$ .

Two of those are honestly polynomial. The knapsack one is not, and the reason is the subject of the last lesson.

The size of an input is the number of bits needed to write it down. A capacity of $W$ is written in $\log_{2} W$ bits, so a table of $n W$ cells is exponential in the length of that number. With 100 items and a capacity of one kilogram measured in grams, the table has $10^{5}$ cells and fills instantly. Measure the same capacity in micrograms and nothing about the problem has changed, but the table has $10^{11}$ cells. An algorithm polynomial in the numeric value of its input but exponential in its length is called pseudo-polynomial, and 0/1 knapsack has no algorithm known to be genuinely polynomial.

That is not a gap in this lesson. It is the edge of what anybody knows how to do, and the final lesson says what is on the other side of it.