Knapsack and Variants

Given items each with a weight and value, and a knapsack with a weight capacity, maximize value. The variants (0/1, unbounded, bounded multiplicity) teach the full DP toolkit.

0/1 knapsack

Each item is either taken (once) or not. State: $f(i, w)$ = best value using items $0..i)$ with capacity $w$. Recurrence:

Take or skip. $O(n W)$ time and space, where $W$ is the capacity. (This is pseudo-polynomial — polynomial in $W$ but exponential in the bit-length of $W$. NP-hard in general.)

Space optimization

The recurrence only references $f(i - 1, *)$, so collapse to a 1D array. Important: iterate the inner loop $w$ from $W$ down to $w_i$, not up. Going up would let the same item be picked multiple times — that's a different problem.

Unbounded knapsack

Unlimited copies of each item. Same DP, but iterate the inner $w$ loop UP from $w_i$ to $W$. This way, $f(w)$ updated with item $i$ at weight $w$ can be reused for $w' > w$, allowing multiple copies.

Coin change (count of ways)

Count the number of ways to make change for $n$ using unlimited copies of each coin. Identical to unbounded knapsack with "value" replaced by "count of ways."

Why these matter

The shape of the recurrence — "for each item, either take or don't" — appears constantly. Subset sum, partition equal subset sum, target sum, last stone weight — all variants of the same template. Master 0/1 knapsack and a third of DP problems become routine.

NP-hardness

General knapsack with arbitrary-precision weights is NP-hard. The pseudo-polynomial algorithm works because real-world capacities are bounded. Beware: if weights can be enormous (say, $10^{18}$), the DP table doesn't fit in memory — you'd need approximation algorithms.