DP: 0/1 Knapsack, Subset Sum and Matrix-Chain Multiplication

Three classical DP problems share a tabular fill and a reconstruction step: the 0/1 knapsack problem (and its decision twin subset sum), and matrix-chain multiplication. Density order solves the fractional knapsack but fails for 0/1; matrix-chain parenthesization has no useful greedy rule either (CLRS Exercise 15.3-4). Both need DP.

This note states the recurrences, works a full knapsack table and a small matrix-chain table, and records the standard complexities $\Theta(nW)$ and $\Theta(n^3)$.

Input. $n$ items with weights $w_i > 0$ and values $v_i \ge 0$, capacity $W$. Each item is taken wholly or not at all.

State. Let $V[i,w]$ be the maximum value using a subset of the first $i$ items with total weight at most $w$.

Answer $V[n,W]$. Time and space $\Theta(nW)$ (pseudo-polynomial in the numeric magnitude of $W$).

Decision version. Given positive integers $a_1,\ldots,a_n$ and target $T$, does a subset sum to $T$? Same table with values replaced by booleans (or by 0/1): item $i$ with weight $a_i$ and value $a_i$, capacity $T$; accept if $V[n,T] = T$. The optimisation version (subset of sum closest to $T$ without exceeding) is the knapsack table with $v_i = w_i = a_i$.

Input. Dimensions $p_0,p_1,\ldots,p_n$ for matrices $A_1,\ldots,A_n$ with $A_i$ of size $p_{i-1} \times p_i$.

Goal. Fully parenthesize the product $A_1 A_2 \cdots A_n$ to minimise the number of scalar multiplications. Multiplying an $a\times b$ matrix by a $b\times c$ matrix costs $abc$.

State. Let $m[i,j]$ be the minimum cost of computing $A_i \cdots A_j$, and let $s[i,j]$ be an optimal split index.

Number of states $\Theta(n^2)$; each state tries $O(n)$ splits: $\Theta(n^3)$ time. The number of full parenthesizations is the Catalan number $C_{n-1} = \frac{1}{n}\binom{2n-2}{n-1}$, which is exponential, so enumeration is hopeless.

Pseudocode uses 1-based arrays, <- for assignment and A[i..j] for the subarray from position $i$ to position $j$.

Preconditions: $W\ge0$ and all $w[i]>0$ are integers; $w$ denotes the weight array, never a loop counter.

Reconstruction. From $(n,W)$: if $V[i,w] = V[i-1,w]$ then item $i$ is unused, step to $(i-1,w)$; otherwise item $i$ is used, emit $i$ and step to $(i-1, w-w_i)$.

Space. Only the previous row is needed for the value: $O(W)$ extra space. Reconstruction then needs either the full table or a separate choice bit per cell.

One-array version: the direction of the inner loop matters. With a single array d[0..W] updated as d[wt] <- max(d[wt], v[i] + d[wt - w[i]]), scan wt downward from $W$ to $w_i$ for 0/1 knapsack. Then d[wt - w[i]] still holds the value from row $i-1$, so item $i$ is used at most once. Scanning upward reads values already updated in row $i$ and silently solves the unbounded knapsack instead. On the four-item example below, the upward scan gives 20 at capacity 6 (item 3 taken twice) where the 0/1 answer is 17.

Edge cases. $W = 0$ or $n = 0$ returns 0. Items with $w_i > W$ are never taken. Ties do not affect the optimal value. They do affect which subset is reported: the reconstruction rule above treats item $i$ as unused whenever $V[i,w] = V[i-1,w]$, so on a tie it prefers to exclude. State the tie-break if a question asks which subset.

Time / space. $\Theta(n^3)$ time, $\Theta(n^2)$ space. Fill by increasing chain length ell so that every shorter chain is already known.

Printing the parenthesization. Recursively: if $i = j$ print $A_i$; else print ( + chain $i..s[i,j]$ + chain $s[i,j]+1..j$ + ).

Exact counts. The table has $n(n-1)/2$ non-trivial cells $m[i,j]$ with $i < j$. Line 10 runs once per pair $(i,j)$ and split $k$, that is $\sum_{\ell=2}^{n} (n-\ell+1)(\ell-1) = (n^3 - n)/6$ times. For $n = 4$: 6 cells and 10 evaluations of $q$.

Cost model. Multiplying a $p \times q$ matrix by a $q \times r$ matrix with the standard method takes $pqr$ scalar multiplications (and $pr(q-1)$ additions) and yields a $p \times r$ matrix. Matrix-chain questions count multiplications only.

In any optimal packing of capacity $w$ using items $1..i$, item $i$ is either absent (then the packing is optimal for $i-1,w$) or present (then the rest is optimal for $i-1, w-w_i$). Those are the only two options, so the recurrence is exhaustive.

Items $(v,w) = (60,10), (100,20), (120,30)$, $W = 50$. Densities 6, 5, 4. Greedy-by-density for 0/1 takes the first two (value 160) and cannot fit the third; the optimum is items 2 and 3 (value 220). The fractional optimum on the same instance is 240 (Greedy Algorithms).

An optimal parenthesization of $A_i \cdots A_j$ splits at some $k$ into $A_i \cdots A_k$ and $A_{k+1} \cdots A_j$. Each side must itself be optimally parenthesized, otherwise a cheaper side could replace it. Minimising over $k$ yields $m[i,j]$ (CLRS 3e, Section 15.2).

The number of ways to parenthesize $n$ matrices is $C_{n-1}$. For $n = 4$, $C_3 = 5$; for $n = 10$, $C_9 = 4862$. DP evaluates each of the $\Theta(n^2)$ subchains once instead of enumerating trees.

Items $(v,w)$: $(1,1), (6,2), (10,3), (16,5)$; $W = 7$. Index items 1..4 in that order.

Final row $V[4,0..7]$ equals $0,1,6,10,11,16,17,22$. Optimum 22: items 2 and 4 (weights $2+5=7$, values $6+16=22$), or check by reconstruction from $(4,7)$: $V[4,7] = 16 + V[3,2]$ and $V[3,2] = 6$, so items 4 and 2.

Selected cells used in the figure:

Dimensions $p = \langle 5, 4, 6, 2, 7 \rangle$ (matrices $5\times 4$, $4\times 6$, $6\times 2$, $2\times 7$).

Chain length 2:

Chain length 3:

Chain length 4:

Optimal cost 158 with split $s[1,4] = 3$: $(A_1 A_2 A_3)\,(A_4)$. Expanding $A_1..A_3$ with $s[1,3] = 1$ gives $((A_1(A_2 A_3))A_4)$.

All $C_3 = 5$ parenthesizations, for comparison:

The worst order costs more than 2.6 times the best. Plain left-to-right evaluation (250) is not optimal here.

Common misconceptions.