Knapsack & Subset Problems

A thief breaks into a warehouse carrying a knapsack that holds at most $W$ units of weight. Item $i$ weighs $w_i$ and is worth $v_i$. Each item is taken whole or left behind, with no fractions and no duplicates. Which subset maximizes the value carried out without exceeding the capacity? This is the 0/1 knapsack problem, and despite its toy framing it is one of the most important problems in computing: it is the kernel of resource allocation, budgeting, and cutting-stock problems, and a canonical $\text{NP-hard}$ optimization problem whose dynamic program teaches a subtle lesson about what polynomial really means.¹

We will arrive at knapsack through its simpler decision cousin, $\text{Subset-sum}$, which strips away the values and asks a plain yes/no question. The include/exclude recurrence is identical, the running-time subtlety is identical, and subset-sum is the cleanest place to see both.

Subset-sum: the decision core

The brute-force space is the $2^n$ sublists. To get a recurrence we shrink the instance one element at a time, and the trick that supplies the second dimension is to make the target itself a parameter of the subproblem.

The answer we want is $A(n,t)$. Now look at $a_i$, the last element we are allowed to use, and make the include/exclude decision that defines every 0/1 dynamic program:

• Exclude $a_i$. Then some sublist of the first $i-1$ elements must already hit $u$ on its own: $A(i-1,u)$.
• Include $a_i$. Then it contributes $a_i$ toward the target, and the first $i-1$ elements must cover the shortfall: $A(i-1,u-a_i)$.

The element can be used in either way, so the subproblem is true if either branch succeeds, a logical $\vee$. The base cases pin down the boundary: a budget of $0$ is always reachable by the empty set; a positive budget is unreachable with no elements; a negative budget is impossible:

Every entry depends only on two entries of the previous row ($i-1$): the one directly above (exclude) and the one above and $a_i$ columns to the left (include). So we fill the table row by row in increasing $i$, sweeping the budget $u=0,\dots ,t$ within each row.

The subset-sum table, filled

Take $L=⟨1,3,4,2⟩$ and target $t=6$. The table holds the boolean $A(i,u)$: row $0$ is $\text{true}$ only in column $0$ (the empty set sums to $0$), and each later row ORs the exclude cell directly above with the include cell $a_i$ columns to its left. The shaded cell $A(4,6)$ is the answer; the two arrows show its include/exclude dependency.

The answer is $A(4,6)=\text{true}$, witnessed by $\left\{4,2\right\}$ or $\left\{1,3,2\right\}$. Reading its two dashed predecessors: exclude $a_4$ asks $A(3,6)=\text{false}$ (no subset of $⟨1,3,4⟩$ hits $6$), while include $a_4=2$ asks $A(3,6-2)=A(3,4)=\text{true}$; the $\vee$ makes the cell true through the include branch.

Subset-sum in pseudocode

This fills $(n+1)(t+1)$ boolean cells in $\Theta (1)$ apiece, for $\Theta (nt)$ time and $\Theta (nt)$ space, and the space drops to $\Theta (t)$ because each row reads only the one above it. We will return to that innocent-looking $\Theta (nt)$ below, since it hides a trap. First, let us see that 0/1 knapsack is the same machine with values bolted on.

The problem and why greed fails

Knapsack is subset-sum with two upgrades: each item carries a separate value$v_i$ as well as a weight $w_i$, and the capacity $W$ is an upper bound rather than an exact target, so we maximize value instead of answering yes/no. The include/exclude decision is unchanged: the $\vee$ of subset-sum becomes a $\max$, and the boolean cell becomes a value. (Set $v_i=w_i=a_i$ and the answer $K(n,t)=t$ recovers subset-sum exactly, a reduction we make precise below.)

The tempting greedy idea, taking items in decreasing order of value-per-weight ratio $v_i/w_i$, is wrong for the 0/1 problem. Suppose $W=10$ and the items are $A=(w=6,v=10)$, $B=(w=5,v=9)$, $C=(w=5,v=9)$. Item $A$ has the best ratio ($1.67$ per unit) so greed grabs it first, then nothing else fits, for a total value of $10$. But taking $B$ and $C$ together fills the knapsack exactly for value $18$. Greed is fooled because a locally efficient item can block a globally better combination; the 0/1 problem lacks the structure that lets greedy choices succeed on matroids. We need to consider subsets, and that calls for dynamic programming.

The high-ratio item $A$ is a trap: it is locally efficient yet blocks the $B+C$ pair that packs the knapsack with no waste.

The subproblem and recurrence

The brute-force space is the $2^n$ subsets. To get a recurrence we need a subproblem definition that shrinks the instance one decision at a time. The key insight, the source of the second dimension, is that we must track not only which items remain available but how much capacity is left.

The answer is $K(n,W)$. Now consider item $i$, the last one we are allowed to use, and make the same include/exclude decision as in subset-sum; this is the 0/1 in the name.

Exclude item $i$. Then the best we can do is whatever the first $i-1$ items achieve within the same budget: $K(i-1,w)$.

Include item $i$. This is only possible if it fits, $w_i\le w$. We collect its value $v_i$ and spend $w_i$ of the budget, leaving $w-w_i$ for the first $i-1$ items: $v_i+K(i-1,w-w_i)$.

We take the better of the two, and if item $i$ does not fit, only the first option is available:²

The base case says: with no items, or no capacity, the value is $0$. Each entry depends only on entries in the previous row ($i-1$), so we fill the table row by row in increasing $i$, and within each row over all budgets $w=0,\dots ,W$.

The DP table, filled

Take capacity $W=5$ and four items: $1:(w=1,v=1)$, $2:(w=2,v=6)$, $3:(w=3,v=10)$, $4:(w=5,v=16)$. The table holds $K(i,w)$; row $0$ is all zeros (no items), and each later row applies the recurrence across budgets $0$ through $5$.

The shaded answer is $K(4,5)=16$. The arrows trace the highlighted entry $K(3,5)$: item $3$ weighs $3\le 5$, so we compare excluding it ($K(2,5)=7$, the cell directly above) against including it ($v_3+K(2,5-3)=10+K(2,2)=10+6=16$, reaching $w_3=3$ columns to the left); the include branch wins at $16$. One row down, $K(4,5)$ compares excluding item $4$ ($K(3,5)=16$) against including it ($16+K(3,0)=16$), a tie at $16$.

The algorithm

Recovering the chosen items. As with every DP, the table holds the value; the subset is recovered by walking backward from $K[n][W]$. At row $i$, if $K[i][b]\ne K[i-1][b]$ then item $i$ was taken: record it and drop the budget to $b-w_i$; otherwise it was skipped. Continue down to row $0$.

On the filled table above ($W=5$), the walk starts at $K[4][5]$ and reads off one decision per row, dropping the budget by $w_i$ whenever an item is taken:

Running time and the pseudo-polynomial trap

The table has $(n+1)(W+1)$ entries, each filled in $\Theta (1)$, so $\text{Knapsack-01}$ runs in

time and space. (Space drops to $\Theta (W)$ if only the value is needed, since each row reads only the previous one, so scan $b$ from high to low to reuse a single array.)

The descending sweep is not a detail but the whole correctness argument for the 1-D version: when we apply an item, $K[b-w_i]$ must still hold the value from before this item was available, so we must reach $b$ before we overwrite $b-w_i$ — that is, go high to low.

Sweeping the other way, low to high, would let $K[b-w_i]$ already include item $2$, silently packing it twice — exactly the reuse that the unbounded knapsackwants, and that the ascending sweep there deliberately permits.

That $\Theta (nW)$ looks polynomial, and here lies one of the most important subtleties in all of algorithms.

Is this really polynomial time? It is tempting to call $\Theta (nt)$ (or $\Theta (nW)$) polynomial: the input is a list of $n+1$ numbers, so surely its size is $\approx \Theta (n)$, and $nt$ is polynomial in $n$. That accounting is wrong, and seeing why is what matters here. We have to count the input's size in bits, not in numbers. This is the same bit-length accounting that underlies asymptotic analysis.

Now rewrite the running time against $b$. Since $t$ can be as large as $2^b-1$,

which is exponential in $b$, the number of bits of a single input integer. Doubling the bits used to write the target squares $t$ and thus squares the running time. An algorithm whose time is polynomial in the numeric value of an input but exponential in its encoded length is called pseudo-polynomial: it counts as polynomial only if we dishonestly pretend an integer $s$ has size $|s|$ rather than its true size $\Theta (\log |s|)$.³ Such running times are central to coping with hardness.

So the $\Theta (nt)$ DP is not a flaw in our analysis but the best we currently know how to do. It is fast and practical precisely when the numbers are small (a target in the thousands, say), and uselessly slow when $t$ is a $200$-bit integer, even though both instances have the same handful of elements. The lesson generalizes: any DP whose table is indexed by a numeric quantity (a target sum, a capacity) inherits this pseudo-polynomial character. The same pattern recurs in coin change and the unbounded knapsack.

Subset-sum as a special case

We opened with subset-sum and built knapsack on top of it; the reduction also runs the other way, and making it precise shows the two problems are the same machine. Take any subset-sum instance $⟨a_1,\dots ,a_n⟩$ with target $t$, and feed it to 0/1 knapsack with each item's value equal to its weight, $v_i=w_i=a_i$, and capacity $W=t$. The most value you can pack into a capacity-$t$ knapsack is at most $t$, and it equals $t$ exactly when some subset of weights sums to $t$ without waste. So

and one call to $\text{Knapsack-01}$ answers subset-sum. The two recurrences are the same shape with the $\vee$ of the boolean table promoted to a $\max$ over values, which is why everything transfers: $\Theta (nt)$ time, pseudo-polynomial, and $\text{NP-complete}$ / NP-hard in general.

Where greed does work: fractional knapsack

Change one rule, letting items be split so that we may take any fraction $0\le x_i\le 1$ of item $i$, and the problem fractional knapsack becomes easy, solvable by the very greedy strategy that failed the 0/1 version. Sort items by value-per-weight ratio $v_i/w_i$ and take them greedily, highest ratio first, slicing the last item to fill the knapsack exactly.

This runs in $\Theta (n\log n)$, since the sort dominates, and is provably optimal by an exchange argument: any optimal solution can be rearranged, without losing value, to match the greedy choice. The contrast is the moral of the lesson.

Takeaways

• $\text{Subset-sum}$ and 0/1 knapsack share one engine: a two-dimensional subproblem ($A(i,u)$ / $K(i,w)$) indexed by items available and budget remaining, because how much budget is left is part of the state.
• The recurrence is the include/exclude choice on the last element: a $\vee$ of two previous-row cells for subset-sum, a $\max$ for knapsack. Each cell depends on the one directly above (exclude) and the one $a_i$/$w_i$ columns to the left (include); the optimal subset is recovered by walking backward.
• $\Theta (nt)$ / $\Theta (nW)$ is pseudo-polynomial: polynomial in the numeric value of the target, but with an honest size of $(n+1)b$ bits it is $\Theta (n\cdot 2^b)$, exponential in the bit length $b$ of one integer.
• A truly polynomial $\mathrm{poly}(n,b)$ algorithm is unlikely: $\text{Subset-sum}$ is $\text{NP-complete}$, so one exists only if $\mathrm{P}=\mathrm{NP}$.
• Fractional knapsack flips to a $\Theta (n\log n)$ greedy algorithm: allowing fractions restores the greedy-choice property that indivisibility destroys, so one rule change crosses the line from NP-hard to easy.