Knapsack

The archetypal DP family. Given items with weights and values and a capacity, maximise value.

0/1 Knapsack — each item at most once

$dp[i][w]=\max (dp[i-1][w],dp[i-1][w-w{t}_i]+va{l}_i).$

long long knapsack01(int n, int W, vector<int>& wt, vector<long long>& val) {
    vector<long long> dp(W + 1, 0);
    for (int i = 0; i < n; i++)
        for (int w = W; w >= wt[i]; w--)              // DOWN: previous row
            dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
    return dp[W];
}

$O(nW)$ time, $O(W)$ space. Pseudo-polynomial — it is exponential in the number of bits of $W$, which is why knapsack is NP-hard despite this simple algorithm.

Unbounded Knapsack — unlimited copies

$dp[w]={\max }_i(dp[w-w{t}_i]+va{l}_i).$

for (int i = 0; i < n; i++)
    for (int w = wt[i]; w <= W; w++)                  // UP: current row
        dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);

The loop direction is the entire difference between the two problems. Downward reads the previous row (item used at most once); upward reads the current row (item reusable).

Bounded Knapsack — at most $c_i$ copies

Naive is $O(W\sum c_i)$. Two better ways:

Binary splitting. Replace $c$ copies of an item by items of multiplicity $1,2,4,\dots$ — $O(\log c)$ items that can form any count up to $c$. Then run 0/1 knapsack.

for (int k = 1; c > 0; k <<= 1) {
    int take = min(k, c);
    items.push_back({wt * take, val * take});
    c -= take;
}

$O(nW\log c)$.

Monotone deque. Group weights by residue mod $w{t}_i$ and use a sliding-window maximum. $O(nW)$ — optimal, but longer to write.

Fractional Knapsack — items divisible

Greedy, not DP: sort by value density $va{l}_i/w{t}_i$ and take greedily, splitting the last item. $O(n\log n)$. This is the one knapsack variant that is not NP-hard, and the exchange argument proving it is a good example of greedy correctness.

The variant table

Variant	Recurrence change	Complexity
0/1	weight loop down	$O(nW)$
Unbounded	weight loop up	$O(nW)$
Bounded ($c_i$ copies)	binary splitting	$O(nW\log c)$
Fractional	greedy by density	$O(n\log n)$
Count the ways instead of maximising	dp[w] += dp[w - wt]	$O(nW)$
Subset sum (feasibility only)	boolean, use a bitset	$O(nW/64)$
Exactly fill capacity	initialise dp[0]=0, rest $-\infty$	$O(nW)$
Minimum items to reach $W$	dp[w] = min(dp[w-wt]+1)	$O(nW)$
Small $W$, huge values	swap the roles: dp[value] = min weight	$O(n\sum val)$
Huge $W$, few items ($n\le 40$)	meet in the middle	$O(2^{n/2})$
Multi-dimensional (weight and volume)	dp[w][v]	$O(nWV)$
$k$ knapsacks	dp[w1][w2]... — exponential in $k$

The “swap the roles” row is the one people forget: when $W$ is $10^9$ but $\sum val\le 10^4$, index the DP by value and store the minimum weight needed. Always check which quantity is small.

Reconstructing the chosen items

Keep the full 2D table (or a take[i][w] bitset) and walk backwards:

int w = W;
for (int i = n - 1; i >= 0; i--)
    if (dp[i + 1][w] != dp[i][w]) { chosen.push_back(i); w -= wt[i]; }

With only the 1D array, this is impossible — the trade-off for the memory saving.

Related classics

• Subset sum and partition — knapsack with $val=wt$
• Coin change — unbounded knapsack, counting or minimising
• Rod cutting — unbounded knapsack in disguise
• Karmarkar-Karp — a heuristic for balanced partitioning

See also: Coin Change · Partition Problems · Bitset Optimization