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. Despite the toy framing, it underlies resource allocation, budgeting, and cutting-stock problems, and it is a canonical $\text{NP-hard}$ optimization problem whose dynamic program illustrates 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; the second dimension comes from making 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 specify 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$ reads $A(3,6)=\text{false}$ (no subset of $⟨1,3,4⟩$ hits $6$), while include $a_4=2$ reads $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 return to the $\Theta (nt)$ bound below; it is less benign than it looks. First, 0/1 knapsack is the same recurrence with values added.

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 greedy strategy fails 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 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 second dimension comes from tracking 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$.

To see the whole table appear rather than just its answer, walk the rows in order. Row $0$ is the boundary: with no items every budget yields value $0$. Each later row copies the row above (the exclude branch) and then, wherever item $i$ fits, overwrites the cell with the larger of that copy and $v_i+K(i-1,w-w_i)$.

• Row $1$, item $(w=1,v=1)$. It fits from $w=1$ onward, and once it fits it is always worth taking, so $K(1,0)=0$ and $K(1,w)=1$ for $w\ge 1$.
• Row $2$, item $(w=2,v=6)$. At $w=2$ we compare exclude $K(1,2)=1$ against include $6+K(1,0)=6$; include wins, $K(2,2)=6$. At $w=3$, include gives $6+K(1,1)=7$, beating the copied $1$. From $w=3$ up the row reads $7$, since one unit of budget past the pair adds nothing new.
• Row $3$, item $(w=3,v=10)$. At $w=3$, include gives $10+K(2,0)=10>K(2,3)=7$. At $w=4$, include gives $10+K(2,1)=11$. At $w=5$, include gives $10+K(2,2)=10+6=16$, the entry the arrows highlighted.
• Row $4$, item $(w=5,v=16)$. It fits only at $w=5$, where include gives $16+K(3,0)=16$, tying the copied $K(3,5)=16$. The recurrence keeps the earlier winner on a tie, so the answer $K(4,5)=16$ is achieved without item $4$.

A cell is never touched again once written: every dependency points one row up, so the sweep in increasing $i$ always finds its inputs already final.

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:

The same walk drawn on the grid is a staircase: a vertical step means the item was skipped (budget held), and a diagonal drop down and to the left means it was taken (budget falls by $w_i$). The path starts at the answer $K(4,5)$ and lands at the origin $K(0,0)$; the diagonal drops mark exactly the chosen items.

from typing import NamedTuple, Sequence

class Item(NamedTuple):
  """
    One knapsack item: the value gained and the weight it costs.\n
  """
  value: int
  weight: int

def knapsack(items: Sequence[Item], capacity: int) -> int:
  """
    Best total value of a subset of `items` whose weights fit within\n
    `capacity`. Weights are non-negative integers.\n
  """
  # best_value[c] is the most value reachable with a weight budget of c.
  best_value: list[int] = [0 for _ in range(capacity + 1)]

  for item in items:
    # sweep capacities high-to-low so the item is taken at most once.
    for remaining in range(capacity, item.weight - 1, -1):
      candidate: int = best_value[remaining - item.weight] + item.value
      best_value[remaining] = max(best_value[remaining], candidate)

  return best_value[capacity]

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 the 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 — the reuse that the unbounded knapsack requires, and that the ascending sweep there deliberately permits.

The failure is easy to trace on the same array. Sweeping upward, $K[2]$ becomes $6$ first. Then at $b=4$ the update reads $K[4-2]=K[2]$, which already holds item $2$; adding $v_2$ again yields $12$, as if two copies of a weight-$2$ item were packed into a budget of $4$. The descending sweep reads $K[2]$ while it still holds its pre-item value, so no cell is ever charged item $2$ twice.

That $\Theta (nW)$ looks polynomial, but the accounting deserves scrutiny.

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. 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.

The $\Theta (nt)$ DP is 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 equivalent. 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 have 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)$; the sort dominates.

The contrast between the two variants is the point.

Approximation and the two ways to be pseudo-polynomial

Knapsack's $\Theta (nW)$ table is pseudo-polynomial — polynomial in the numeric capacity $W$, exponential in its bit length. The same limitation makes possible a strong approximation result: knapsack admits a fully polynomial-time approximation scheme (FPTAS). Given any $\epsilon >0$, one can find a packing within a $(1-\epsilon )$ factor of optimal in time $O(n^3/\epsilon )$ — polynomial in both $n$ and $1/\epsilon$ — by dynamic-programming on value instead of weight and then rounding the values: divide every $v_i$ by a scaling factor $K=\epsilon v_{\max }/n$ and round, which shrinks the value-indexed table to polynomial size while losing at most an $\epsilon$ fraction of the objective (Ibarra and Kim, 1975; the treatment in Vazirani's Approximation Algorithms is the standard reference). Few NP-hard problems can be approximated this well; knapsack can precisely because it is only weakly NP-hard, i.e. hard only when the numbers are large.

The complementary DP, keyed on value rather than weight ($D[v]=$ minimum weight achieving value exactly $v$), runs in $\Theta (n\cdot V)$ where $V$ is the total value, and is the one the FPTAS rounds; whichever of $W$ and $V$ is smaller gives the better bound. Two related results extend this. The meet-in-the-middle technique (Horowitz and Sahni, 1974) solves subset-sum in $O(2^{n/2})$ time by splitting the items in half, enumerating each half's subset sums, and merging — far better than $2^n$ when $W$ is astronomically large and the $\Theta (nW)$ table is useless. And strong NP-hardness marks the boundary of the FPTAS approach: problems like bin packing and 3-partition remain hard even with small numbers, so no pseudo-polynomial algorithm exists for them unless P $=$ NP. The FPTAS exploits precisely that large-number weakness of Knapsack.⁴

Takeaways

• $\text{Subset-sum}$ and 0/1 knapsack share one structure: 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.