Unit 5.7 · about 4 h
125 / 324Knapsack, subset and bitmask dynamic programming
One table shape answers min-coins, counting and feasibility. The loop direction decides whether an item is reusable.
- derive
- implement
You can now
- Derive take-or-skip recurrences with the correct inner-loop direction for \(0/1\) versus unbounded choice.
- Reduce subset-sum and counting variants to one knapsack table.
- Encode small-set state as bitmasks and bound the \(2^n\) state cost.
Covers
- Knapsack, subset and bitmask state
Study, in this order
4 steps
- \(0/1\) knapsack and the backward inner loopDSA Handbook - dynamic programming
The 1D table fill; Why the inner loop sweeps right-to-left; Worked example: LC 416 on
[1, 5, 11, 5]; Reformulations: when the problem doesn't say "knapsack" (LC 494, 1049, 474) - Unbounded knapsack and the reversed loopDSA Handbook - dynamic programming
What changes from \(0/1\) knapsack; The mechanics: filling \(\text{dp}[a]\) left to right; Counting unordered combinations: LC 518; Counting ordered sequences: LC 377
- Bitmask state for small setsDSA Handbook - dynamic programming
The pattern; Worked example: LC 847 on a 3-node line; What it actually costs; Permutation / assignment: position is
popcount(mask)(LC 526) - Subset Sum and the Nadiria change problemAlgorithms - dynamic programming
Section 3.8 (pp. 116-117): \(\operatorname{SS}(i, t)\) recurrence with the \(O(nT)\) table, and Exercise 1 Nadiria change (p. 123): greedy failure first, then recurrence, then DP
Focus on
- \(0/1\) sweeps capacity right to left so item \(i\) cannot fund itself in the same pass. Unbounded sweeps left to right so \(\text{dp}[a-c]\) already includes item \(i\).
- Subset Sum \(O(nT)\) is pseudopolynomial: \(T\) is a value, not the input size. Tabulation loses to backtracking when \(T\) dwarfs \(2^n\).
- Bitmask state costs \(2^n\) subsets times \(n\) transitions. It fits only small ground sets; that boundary is the content, not a footnote.
Reproduce closed-book
coin_change([1,2,5], 11) = 3, coin_change_ii(5, [1,2,5]) = 4, can_partition([1,5,11,5]) = True and can_partition([1,2,3,5]) = False. Also show largest-first greedy on ([1,3,4], 6) gives 3 coins versus optimal 2. State the amounts and all five expected outputs.Traps
- Sweeping \(0/1\) capacity left to right. Item \(i\) then reuses its own update and the \(0/1\) table silently becomes unbounded.
- Reading min-coins -1 as zero ways. Coin Change returns -1 when unreachable; Coin Change II returns 0 ways. Different families, different sentinels.
- Applying bitmask DP past \(n = 20\) without counting. \(2^{20}\) rows times \(n\) columns already exceeds ten million cells; state the bound first.
Practice
Attempt cold. Check ([1,2,5], 11) = 3, ([2], 3) = -1 and ([1], 0) = 0, then submit.
Attempt cold: write the reuse direction before coding. After submitting, read the AlgoMaster Coin Change lesson (https://algomaster.io/learn/dsa/coin-change).
LeetCode 416 - Partition Equal Subset Sum
Check [1,5,11,5] = True and [1,2,3,5] = False, then submit.
Reduce to subset sum with target \(\text{total}/2\). After submitting, compare with the DSA Handbook knapsack-01 reformulation section.
Self-test
-
Why does the \(0/1\) inner loop run right to left?
Left to right lets \(\text{dp}[a]\) read \(\text{dp}[a-c]\) written in the same item pass, reusing item \(i\). Right to left keeps every read on the previous item row. -
Coins
[1,3,4], amount 6: what does largest-first greedy give and why is it wrong?\(4+1+1 = 3\) coins. Optimal is \(3+3 = 2\). Greedy commits to 4 without comparing the two-coin completion; only the recurrence compares all last-coin choices. -
Subset Sum runs \(O(nT)\). Why is that not polynomial?
\(T\) measures a value in the input, which takes \(\log T\) bits to write. The bound is polynomial in the numeric value but exponential in the input length. -
When is bitmask state the only state that fits?
When feasibility depends on exactly which items are used, not just how many or how much. Assignment and visit-all paths need the subset identity itself.
Completion criterion
Stop when
The five reproduce numbers come out of a blank file, and you can state each loop direction and why.
Mark passed, then open 5.8 Only mark this when you can do it without notes.Leads to
- 5.8 Recurrence proofs and differential validation Validate loop directions with differential tests that catch reuse bugs.
- 5.9 Dynamic programming as shortest paths, formulations and limits Read coin change as allocation and state when the subset space is too large.
Comes after
- 5.5 Grid, path and interval dynamic programmingMove from spatial intervals to capacity and subset state.
- 5.6 Tree dynamic programmingTrade the tree order for capacity and subset orders.
Resources for this unit
- DSA Handbook - dynamic programming Study Part 9 in order from state and recurrence through sequence, grid, tree and bitmask families. For every example, close the page and reconstruct the state, transition and evaluation order.
- Algorithms - dynamic programming Use the dynamic-programming chapter to derive states and recurrences from first principles and to separate DP from greedy reasoning and shortest paths.
Also in this section
- AlgoMaster DSA - dynamic programming slice Attempt Coin Change, Longest Common Subsequence and House Robber III cold. Write the state, transition, base case and evaluation order first; compare against brute force on small inputs and reconstruct a witness when available.
- Hypothesis - exhaustive and differential DP tests Generate small valid instances, compare memoized, tabulated and exhaustive results, and retain shrunk failures for wrong state, base case, order and compression defects.
- NeetCode - unseen mixed problems Use two tag-hidden mixed problems as the final transfer test. One must require rejecting a tempting greedy or insufficient-state solution with a counterexample.
- Python sys: recursion limit Read
sys.getrecursionlimitandsys.setrecursionlimit: the limit guards the C stack and its safe maximum is platform-dependent. Check the default withgetrecursionlimit(1000 on CPython 3.13), raise it once for memoized DP, or switch to tabulation for deep inputs. - Erickson lecture note D - Advanced Dynamic Programming Read Section D.1 (Saving Space: Divide and Conquer) for the Hirschberg Half-table split that recovers an optimal edit sequence in \(O(m + n)\) space.
- Erickson lecture note J - Approximation Algorithms Read Section J.1 (Load Balancing) for the Partition reduction that makes exact scheduling NP-hard, the
GreedyLoadBalanceheuristic, and Theorem J.1 with its factor-2 proof.