ii. Knapsack and Subset Sum

Items with cost $w_i$ and value $v_i$, capacity $W$. The basic DPs are $O(nW)$; the real skill is noticing which quantity is small (capacity, total value, number of items, maximum weight, number of distinct weights) and which structure the items have (equal weights give concave groups, bounded total gives $O(\sqrt{S})$ distinct sizes).

The family

Variant	Recurrence / method	Cost
0/1	for w = W..c: dp[w] = max(dp[w], dp[w-c] + v)	$O(nW)$
unbounded	same, capacity increasing	$O(nW)$
bounded ($k_i$ copies)	binary splitting, or monotone deque per residue	$O(nW\log k)$ / $O(nW)$
exactly $W$	init $d{p}_0=0$, others $-\infty$	same
small total value $V=\sum v_i$	dp[value] = min weight	$O(nV)$
boolean (subset sum)	`bitset	= bitset << c`
subset sum, total $S$ bounded	merge duplicates: $O(\sqrt{S})$ items	$O(S\sqrt{S}/64)$
counting subsets	dp[w] += dp[w-c]; reversible (deletions)	$O(nW)$
many items with equal weight	concave max-plus convolution per residue	$O(W\log W)$ per weight class
small weights $\le D$, huge $W$	greedy prefix + DP on $O(D^2)$ exchanges	$O(n{D}^2)$
huge everything, $n\le 40$	meet in the middle (MITM)	$O(2^{n/2})$
representability of huge $W$ with unlimited coins	shortest paths modulo the smallest coin	$O(m\cdot n\log m)$
items on a tree (take parent to take child)	tree knapsack (Tree DP)	$O(nW)$ or $O(n^2)$
fractional	greedy by density	$O(n\log n)$
$(1-\epsilon )$-approximation	round values to multiples of $\epsilon v_{\max }/n$, value-indexed DP	$O(n^2/\epsilon )$
minimum items to reach exactly $W$	dp[w] = min(dp[w-c]+1)	$O(nW)$
two constraints (weight and volume)	dp[w][vol]	$O(nWV)$
$k$ independent knapsacks	dp[w_1][w_2]...[w_k] — exponential in $k$	$O(n{W}^k)$

Loop directions and why they work: DP Foundations. The basic 0/1 DP is only pseudo-polynomial: it’s polynomial in the value of $W$, not in the number of bits needed to write $W$ — which is exactly why knapsack is NP-hard despite this simple $O(nW)$ algorithm, and exactly why an FPTAS (below) exists for it but not for strongly NP-hard problems.

Proof: fractional knapsack greedy and the FPTAS bound

Greedy: if an optimal fractional solution takes some amount of a lower-density item while a higher-density item is not fully taken, moving $\delta$ weight from the former to the latter changes the value by $\delta ({\rho }_{\text{high}}-{\rho }_{\text{low}})\ge 0$. Repeating gives the density-ordered solution without loss.
FPTAS: with $K=\epsilon v_{\max }/n$ and $v_i^{\prime }=\lfloor v_i/K\rfloor$, the optimum $S^{\ast }$ for the original values satisfies ${\sum }_{S^{\ast }}K{v}_i^{\prime }\ge {\sum }_{S^{\ast }}{v}_i-nK=\text{OPT}-\epsilon v_{\max }\ge (1-\epsilon )\text{OPT}$ (since $\text{OPT}\ge v_{\max }$, assuming every item fits alone). The solution found is optimal for $v^{\prime }$, so its original value is at least $K\sum v^{\prime }$ of itself $\ge K{\sum }_{S^{\ast }}{v}_i^{\prime }$. Total scaled value is at most $n\cdot n/\epsilon$, giving $O(n^2/\epsilon )$ states.

Bounded knapsack in $O(nW)$

For an item $(c,v,k)$ and a residue $r$, write $j=r+tc$. Then $d{p}_{r+tc}^{\prime }=tv+{\max }_{t-k\le s\le t}(d{p}_{r+sc}-sv)$, a sliding-window maximum.

void addBounded(vector<ll>& dp, int c, ll v, ll k) {        // dp over capacities 0..W, in place
    int W = sz(dp) - 1; vector<ll> old = dp;
    for (int r = 0; r < c && r <= W; r++) {
        deque<pair<ll, ll>> dq;                            // (s, old[r + s c] - s v), values decreasing
        for (ll t = 0, j = r; j <= W; t++, j += c) {
            ll val = old[j] - t * v;
            while (sz(dq) && dq.back().second <= val) dq.pop_back();
            dq.push_back({t, val});
            if (dq.front().first < t - k) dq.pop_front();
            dp[j] = dq.front().second + t * v;
        }
    }
}

Binary splitting is shorter: replace $k$ copies with bundles $1,2,4,\dots ,2^{p-1},k-(2^p-1)$ and run 0/1 knapsack on the bundles.

Proof: binary splitting represents exactly the counts $\mathrm{0..}k$

Let $p$ be maximal with $2^p-1\le k$ and $\rho =k-(2^p-1)<2^p$. Subsets of $\{1,\dots ,2^{p-1}\}$ give every count in $[0,2^p-1]$ (binary representations). Adding the bundle $\rho$ gives every count in $[\rho ,k]$, and since $\rho \le 2^p$ these two ranges together cover $[0,k]$. No subset exceeds $k$ because the total of all bundles is $k$.

Subset sum

bitset<N> dp; dp[0] = 1;
for (int x : a) dp |= dp << x;

Bounded total $S$: while some value $x$ occurs $\ge 3$ times, replace two copies by one copy of $2x$. Afterwards every value occurs at most twice, so there are $O(\sqrt{S})$ items, and the bitset DP costs $O(S\sqrt{S}/64)$. When $S$ is only known at runtime, dispatch to a templated bitset size (template<int L> void solve() { if (S >= L) return solve<min(2 * L, MAXL)>(); ... }).

Proof: merging duplicates keeps the reachable sums and leaves $O(\sqrt{S})$ items

Before the merge there are $c\ge 3$ copies of $x$; after it, $c-2$ copies of $x$ and one $2x$. A subset using $j$ copies of $x$ ($0\le j\le c$) is simulated by $j$ copies if $j\le c-2$, or by $2x$ plus $j-2\le c-2$ copies otherwise; conversely $2x$ is two copies of $x$. So the set of reachable sums is unchanged; the total sum is unchanged and the number of items drops, so the process terminates. At the end the distinct values $d_1<d_2<\cdots <d_m$ satisfy $d_i\ge i$ and $\sum d_i\le S$, so $m(m+1)/2\le S$, $m\le \sqrt{2S}$, and there are at most $2\sqrt{2S}$ items.

Other subset-sum facts:

• Values bounded by $D$: Pisinger’s balancing algorithm runs in $O(nD)$.
• “Sum divisible by $k$” is a residue DP in $O(nk)$; by Erdős–Ginzburg–Ziv, any $2k-1$ integers contain $k$ whose sum is divisible by $k$.
• “XOR equals $x$” is linear algebra over ${\mathbb{F}}_2$ (XOR Basis).
• Minimum difference partition: the largest reachable sum $\le \lfloor S/2\rfloor$.

Counting knapsack and deletions

The counting DP is polynomial multiplication: adding item $c$ multiplies the generating function by $(1+x^c)$ (0/1) or $\frac{1}{1-x^c}$ (unbounded). Both are invertible, so items can be removed in $O(W)$:

void add(vector<mint>& f, int c)    { for (int j = sz(f) - 1; j >= c; j--) f[j] += f[j - c]; }   // * (1 + x^c)
void remove(vector<mint>& f, int c) { for (int j = c; j < sz(f); j++) f[j] -= f[j - c]; }          // / (1 + x^c)
void addUnb(vector<mint>& f, int c) { for (int j = c; j < sz(f); j++) f[j] += f[j - c]; }          // / (1 - x^c)
void remUnb(vector<mint>& f, int c) { for (int j = sz(f) - 1; j >= c; j--) f[j] -= f[j - c]; }     // * (1 - x^c)
// at most k copies: * (1 - x^{(k+1)c}) / (1 - x^c), two O(W) passes

That answers “for each item, the number of subsets of the others with sum $s$” in $O(nW)$ total. Over ${\mathbb{F}}_p$ (or with doubles for probabilities) this is exact; for max/min DPs there is no inverse, so use the tricks below.

Proof: the removal loop divides by $1+x^c$

Let $g=f\cdot (1+x^c)$, i.e. $g_j=f_j+f_{j-c}$. Then $f_j=g_j-f_{j-c}$, where $f_{j-c}=g_{j-c}$ for $j<2c$ and is already recovered for larger $j$ if we go in increasing $j$. The in-place loop computes exactly this. The unbounded versions are the same identities with $g_j=f_j-f_{j-c}$ (multiplication by $1-x^c$) and its inverse.

Max/min knapsack without deletion

• Range of items, many queries (best value using items $l..r$ with capacity $W_q$): divide and conquer on the item array. For a split point $m$, compute knapsack DPs of $l..m$ going left from $m$ and of $m+\mathrm{1..}r$ going right, and answer every query crossing $m$ by ${\max }_x(L_x+R_{W_q-x})$ in $O(W)$. Total $O(nW\log n+qW)$.
• Queue of items (add newest, remove oldest): two stacks of DP layers (push = one knapsack step from the stack top); a query merges the two tops in $O(W)$ for a single capacity.
• Undo (stack order): keep the previous layer per push, or a rollback log.
• Offline add/remove in arbitrary order: segment tree over time; each item is added to $O(\log q)$ nodes; DFS with a stack of layers, $O(qW\log q)$.

Many items with the same weight

Items of weight $c$ sorted by value descending have concave prefix sums $g_0=0,g_1,g_2,\dots$. Within each residue class mod $c$, the update is a max-plus convolution of an arbitrary sequence $a$ with the concave $g$, whose argmax is monotone. Divide and conquer gives $O(\frac{W}{c}\log \frac{W}{c})$ per residue, $O(W\log W)$ per distinct weight. So for weights in $[1,D]$ the whole problem is $O(DW\log W)$ independent of $n$.

// b[j] = max_{0 <= j - t < sz(g)} a[t] + g[j - t], g concave
void conv(int jl, int jr, int tl, int tr, const vector<ll>& a, const vector<ll>& g, vector<ll>& b) {
    if (jl > jr) return;
    int jm = (jl + jr) / 2, best = max(tl, jm - sz(g) + 1); ll bv = LLONG_MIN;
    for (int t = best; t <= min(tr, jm); t++) if (a[t] + g[jm - t] > bv) bv = a[t] + g[jm - t], best = t;
    b[jm] = bv;
    conv(jl, jm - 1, tl, best, a, g, b); conv(jm + 1, jr, best, tr, a, g, b);
}
void addGroup(vector<ll>& dp, int c, vector<ll> vals) {     // all items of weight c; unreachable dp = -1e18
    sort(all(vals), greater<>()); vector<ll> g{0};
    for (ll x : vals) g.push_back(g.back() + x);
    int W = sz(dp) - 1;
    for (int r = 0; r < c && r <= W; r++) {
        vector<ll> a; for (int j = r; j <= W; j += c) a.push_back(dp[j]);
        vector<ll> b(sz(a)); conv(0, sz(a) - 1, 0, sz(a) - 1, a, g, b);
        for (int t = 0; t < sz(a); t++) dp[r + t * c] = b[t];
    }
}

Proof: the argmax is monotone

Let $M_{j,t}=a_t+g_{j-t}$ (only for $0\le j-t<|g|$). Take $j<j^{\prime }$ and $t<t^{\prime }$. The indices satisfy $j-t^{\prime }<j-t,j^{\prime }-t^{\prime }<j^{\prime }-t$ and $(j-t^{\prime })+(j^{\prime }-t)=(j-t)+(j^{\prime }-t^{\prime })$; for a concave $g$ the outer pair has the smaller sum, $g_{j-t^{\prime }}+g_{j^{\prime }-t}\le g_{j-t}+g_{j^{\prime }-t^{\prime }}$. Adding $a_t+a_{t^{\prime }}$ to both sides gives $M_{j,t^{\prime }}+M_{j^{\prime },t}\le M_{j,t}+M_{j^{\prime },t^{\prime }}$. So if $t^{\prime }$ beats $t$ at row $j$ ($M_{j,t^{\prime }}\ge M_{j,t}$), then $M_{j^{\prime },t^{\prime }}\ge M_{j^{\prime },t}+(M_{j,t^{\prime }}-M_{j,t})\ge M_{j^{\prime },t}$: it also beats $t$ at row $j^{\prime }$. Hence the leftmost argmax is nondecreasing in $j$, and divide and conquer over rows with shrinking column ranges is valid. The band restriction $0\le j-t<|g|$ is compatible, because its boundaries $t\ge j-|g|+1$ and $t\le j$ are both nondecreasing in $j$.

Small weights, huge capacity

All $w_i\le D$, $W$ and $n$ large. Sort by density $v_i/w_i$ descending and let $G$ be the longest prefix that fits. Some optimal solution differs from $G$ only by a removed set $A\subseteq G$ and an added set $B$ from the rest, each of weight $O(D^2)$. So compute “min value lost removing weight exactly $x$ from $G$” and “max value gained adding weight exactly $y$ from the rest” for $x,y\le 2D^2+D$, and combine: $O(n{D}^2)$.

Proof: the exchange sets are small

Lemma: two sequences of integers in $[1,D]$, each of length $\ge 2D$, have nonempty subsequences with equal sums. Walk with a counter $d$ = (sum taken from the first) $-$ (sum taken from the second): take from the first if $d\le 0$, from the second otherwise. Then $d$ always stays in $[-(D-1),D]$, a set of $2D$ values; after $2D$ steps some value repeats, and the items taken between the two occurrences form equal-sum nonempty blocks.
Take an optimal $O=(G\setminus A)\cup B$ minimising $|A|+|B|$. If $|A|,|B|\ge 2D$, find $A^{\prime }\subseteq A$, $B^{\prime }\subseteq B$ of equal weight. Every item of $A$ has density $\ge$ every item of $B$ (prefix vs suffix of the density order), so $v(A^{\prime })\ge v(B^{\prime })$, and $O^{\prime }=O\setminus B^{\prime }\cup A^{\prime }$ has the same weight and value $\ge v(O)$, with a smaller symmetric difference; contradiction. So one of them has fewer than $2D$ items, weight $<2D^2$. If $|A|<2D$: since $w(G)>W-D$ (the next item didn’t fit) and $w(O)\le W$, $w(B)=w(O)-w(G)+w(A)<D+2D^2$. If $|B|<2D$: we may assume $w(O)>W-D$ (otherwise any item of $A$ fits back in without loss), so $w(A)=w(G)-w(O)+w(B)<D+2D^2$.

Related: CF 1132E (weights $\mathrm{1..8}$ with counts up to $10^{16}$): take each weight greedily except for at most $\text{lcm}(\mathrm{1..8})/i$ copies, and DP over the remainder.

Unlimited coins and huge targets

Let $m$ be the smallest coin. Amounts with the same residue mod $m$ are representable from some threshold on: if $d_r$ is the smallest representable amount $\equiv r(\mathrm{mod}m)$, then $x$ is representable iff $x\ge d_{x\mathrm{mod}m}$. Compute $d$ by Dijkstra on $m$ residue vertices with an edge $r\to (r+c)\mathrm{mod}m$ of weight $c$ per coin.

vector<ll> residueDist(const vector<int>& coins) {          // d[r] = smallest representable x, x = r (mod m)
    int m = *min_element(all(coins)); vector<ll> d(m, LLONG_MAX); d[0] = 0;
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq; pq.push({0, 0});
    while (sz(pq)) {
        auto [dv, r] = pq.top(); pq.pop();
        if (dv != d[r]) continue;
        for (int c : coins) { int s = (r + c) % m; if (dv + c < d[s]) d[s] = dv + c, pq.push({d[s], s}); }
    }
    return d;
}
// representable count in [0, X]: sum over r with d[r] <= X of (X - d[r]) / m + 1

A heap-free $O(nm)$ version: for each coin $c$, the edges $r\to r+c$ form $\gcd (c,m)$ cycles; start each cycle at its current minimum and relax around it twice.

Two coprime coins $a,b$: the largest non-representable amount is $ab-a-b$ and exactly $\frac{(a-1)(b-1)}{2}$ amounts are non-representable.

Proof: residue shortest paths and the two-coin formula

Any multiset of coins with sum $x$, taken in any order, is a walk from residue 0 to residue $x\mathrm{mod}m$ of length $x$, so $x\ge d_{x\mathrm{mod}m}$. Conversely the shortest walk is a multiset of coins summing to $d_r$, and adding copies of $m$ reaches every $d_r+km$. So $x$ is representable iff $x\ge d_{x\mathrm{mod}m}$.
For coins $a<b$ coprime and $m=a$: the residues $kb\mathrm{mod}a$, $k=\mathrm{0..}a-1$, are distinct, and $d_{kb\mathrm{mod}a}=kb$ (any representation of an amount in that residue class uses at least $k$ copies of $b$). The largest non-representable amount is ${\max }_r{d}_r-a=(a-1)b-a$. The number of non-representable amounts is ${\sum }_r\lfloor d_r/a\rfloor ={\sum }_{k<a}\lfloor kb/a\rfloor =\frac{(a-1)(b-1)}{2}$ (the classical floor-sum identity for coprime $a,b$).

Coin change: three different questions

Given denominations, making amount $W$. Three distinct questions, three different recurrences — mixing them up is the most common error in this family:

Question	Recurrence	Loop order
is $W$ reachable / minimum coins	unbounded knapsack: dp[w] = min(dp[w], dp[w-c]+1)	capacity increasing
number of combinations (multiset, order irrelevant)	dp[w] += dp[w-c]	coins outer, amount inner
number of permutations (sequences, order matters)	same recurrence body	amount outer, coins inner

The loop order is the semantics

Identical recurrence bodies, swapped loop order, different answers. Target 3, coins $\{1,2\}$: combinations gives 2 ($1+1+1$, $1+2$); permutations gives 3 ($1+1+1$, $1+2$, $2+1$). This is the same combinations-outer-vs-sequences-outer rule as DP Foundations’ order table.

Greedy (always take the largest coin that fits) is not generally optimal: coins $\{1,3,4\}$, target 6 — greedy gives $4+1+1$ (3 coins), optimum is $3+3$ (2 coins). A coin system where greedy is always optimal is called canonical; real currencies happen to be canonical, which is why the wrong intuition persists. Checking whether a given system is canonical is itself nontrivial — Pearson’s algorithm decides it in $O(n^3)$ by checking a bounded set of counterexample candidates. Never assume greedy works unless you’ve verified it for the given denominations.

For two coprime coins, the largest unrepresentable amount and the count of unrepresentable amounts are proved above (Unlimited coins and huge targets); for 3+ coins there’s no closed form and computing the Frobenius number is NP-hard in general, though the same residue-shortest-path technique above still decides representability of one specific (possibly huge) target.

Partitioning problems

Three more DP families that are “knapsack-shaped” but don’t fit the weight/value framing above.

Partition a sequence into contiguous segments (order fixed, choose where to cut):
$dp[i][j]={\min }_{k<i}(dp[k][j-1]+\mathrm{cost}(k,i))$
— best cost splitting the first $i$ elements into $j$ segments. $O(K{n}^2)$ naively; the same optimisations as elsewhere in this chapter apply directly:

Condition	Technique	Time
$\mathrm{cost}$ satisfies the quadrangle inequality	Knuth optimization	$O(Kn\log n)$
$\mathrm{cost}$ is Monge (monotone argmin)	D&C optimization	$O(Kn\log n)$
$\mathrm{cost}$ linear in a parameter	CHT	$O(Kn)$
answer convex in $K$, $K$ huge	Aliens trick	$O(n\log C)$
segment length bounded	monotone queue	$O(Kn)$

Minimax partitioning needs no DP at all

“Split into $K$ segments minimising the largest segment sum” is not a DP problem: binary search the answer $X$, greedily cut whenever the running sum would exceed $X$, and check the segment count is $\le K$. $O(n\log \sum a)$ — far simpler and faster than any DP formulation, and a common trap for over-applying this section’s table.

Counting integer partitions (write $n$ as a sum of positive integers, order irrelevant — the partition function $p(n)$): this is exactly the coin-change combinations recurrence above with coins $\mathrm{1..}n$, giving $p(n)$ in $O(n^2)$.

Proof: Euler's pentagonal number theorem gives $O(n\sqrt{n})$

(Stated, not re-derived — a full proof is a generating-function argument beyond this note’s scope, consistent with how this repo cites rather than re-derives genuinely deep classical theorems elsewhere, e.g. Gordon’s theorem in 01-problem-solving/05.) Euler’s identity ${\prod }_{k\ge 1}(1-x^k)={\sum }_{k=-\infty }^{\infty }(-1{)}^k{x}^{k(3k-1)/2}$ gives, after inverting (the partition generating function is the reciprocal of this product), the recurrence $p(n)={\sum }_{k\ge 1}(-1{)}^{k+1}(p(n-\frac{k(3k-1)}{2})+p(n-\frac{k(3k+1)}{2})),$ summed over $k$ with both pentagonal numbers $\le n$ — only $O(\sqrt{n})$ terms, each an $O(1)$ lookup, giving $O(n\sqrt{n})$ total for all of $p(\mathrm{0..}n)$.

Variants (small modifications to the same coin-change-style DP, or the generating function): partitions into distinct parts, into odd parts (equinumerous with distinct parts, a classical Euler bijection), into at most $k$ parts, with parts of bounded size.

Rod cutting (unbounded knapsack in disguise — cut a rod of length $n$ into pieces to maximise total price):

Variant	Change
plain	unbounded knapsack: dp[len] = max(dp[len], dp[len-i]+price[i])
cost $c$ per cut	dp[len] = max(price[len], max_i(dp[i]+dp[len-i]-c))
at most $k$ pieces	add a dimension, $O(n^{2}k)$
each length usable once	0/1 knapsack — weight loop downward
maximise the product of piece lengths	see below
cutting at given positions, cost = piece length	interval DP, see below

Proof: maximum product of pieces uses only parts 2 and 3

No part is 1: merging a part of $1$ with any neighbouring part $x$ into a single part $x+1$ keeps the total length fixed and scales the product by $(x+1)/x>1$ — strictly better, so an optimal split has no part equal to $1$. No part exceeds 4: replacing a part $k\ge 5$ by two parts $3$ and $k-3$ keeps the length fixed and scales the product by $3(k-3)/k$, which exceeds $1$ exactly when $3k-9>k$, i.e. $k>4.5$ — true for every $k\ge 5$, so no optimal split uses a part $>4$. No part is 4: a part of $4$ splits into two parts of $2$ with the same product ($2\times 2=4$) and the same length, so we may always rewrite it that way without loss. At most two parts equal 2: three parts of $2$ sum to the same length as two parts of $3$ ($6=6$), but $2\times 2\times 2=8<3\times 3=9$, so replacing any three $2$s by two $3$s strictly improves the product — hence an optimal split has at most two $2$s. Combining these, every optimal split uses only $2$s and $3$s with at most two $2$s; writing $n=3q+r$, $r\in \{0,1,2\}$, that forces $r=0\Rightarrow$ all $3$s, $r=1\Rightarrow$ two $2$s and $q-1$ threes (since $4=3+1$ is handled as $2+2$, not a bare leftover $1$), $r=2\Rightarrow$ one $2$ and $q$ threes. ($3^{1/3}>2^{1/2}>4^{1/4}>\cdots$ is the continuous intuition for why $3$ dominates — the continuous optimum is $e\approx 2.718$, nearest integer $3$.) $■$

Cutting sticks (a stick of length $L$ must be cut at $m$ given positions, each cut costs the length of the piece being cut, minimise total cost):
$dp[i][j]={\min }_{i<k<j}(dp[i][k]+dp[k][j])+(x_j-x_i)$
with the cut positions (plus $0$ and $L$) as the DP’s endpoints. $O(m^3)$ naively, $O(m^2)$ with Knuth optimization (the cost satisfies the quadrangle inequality). This is the same recurrence as matrix chain multiplication and merging-stones problems — interval DP is one pattern wearing several costumes.

Reconstruction

• Keep take[i] as a bitset<W+1> per item ($nW$ bits), then walk back: if take[i][w], use item $i$ and set $w-=c_i$.
• Or keep the full table and compare dp[i+1][w] != dp[i][w].
• Subset sum with a 1D array: record from[s] = item that first made $s$ reachable; walking back through from uses each item at most once because sums become reachable in item order.