On this page

The Knapsack Family

A hiker has a backpack that holds 7 kg. On the table are four items: a 1 kg snack worth 1 point of happiness, a 3 kg tent worth 4, a 4 kg stove worth 5, and a 5 kg camera worth 7. Each item is either packed or left behind — you can't take half a tent. Which items should go in the bag?

The camera has the best value per kilogram (1.4), so a greedy packer grabs it first, then the snack: weight 6, value 8. But the tent and the stove together weigh exactly 7 and are worth 9. Greedy loses. Trying every subset works for 4 items ( subsets) but not for 100 ().

This is the 0/1 knapsack problem, and the dynamic programming that solves it is one of the most reused ideas in algorithms. Change "value" to "1 if possible", and it is subset sum. Allow unlimited copies, and it is unbounded knapsack — and, with coins as items, coin change. Add a second capacity (memory and CPU), and it is multi-dimensional knapsack. All of them are one table: rows are items, columns are "how much capacity is used", and each cell asks one question: take this item, or not?

This lesson builds on 1D DP & Classic Sequences (take-or-skip recurrences, rolling arrays) and DP Foundations. It is the first DP in the module whose state has two coordinates that are not positions in the input: an item index and a remaining budget.

Why this exists

Every time a finite budget meets a set of indivisible options, a knapsack hides inside:

  • a company with a fixed capital budget choosing which projects to fund;
  • a paper mill cutting standard-width rolls into customer-ordered widths;
  • a cluster scheduler placing containers with CPU and memory requests onto machines;
  • a test runner choosing which tests to run in a 10-minute CI window;
  • a vending machine paying out change with the fewest coins.

The earliest known mathematical treatment is G. B. Mathews' 1897 paper "On the partition of numbers"; the problem was studied systematically from the 1950s (George Dantzig's 1957 paper on discrete-variable extremum problems gave the greedy-by-ratio bound and the LP relaxation). In 1972 Richard Karp listed it among his 21 NP-complete problems — so there is (probably) no algorithm that is fast for every input. And yet the DP in this lesson solves real instances with millions of cells in milliseconds. Understanding why both of those are true at once — pseudo-polynomial time — is one of the most useful pieces of complexity theory a working engineer can own.

Pattern triggers

If the problem says or has…Think of…
"each item can be used at most once", a weight/cost limit, maximise value0/1 knapsack: dp[c] = max(dp[c], dp[c-w] + v), capacity loop backwards
"unlimited supply" of each item / coinUnbounded knapsack: same line, capacity loop forwards
"item is available times"Bounded knapsack: binary splitting into 0/1 items, or monotonic queue
"is there a subset that sums to exactly ?"Subset sum: boolean DP, or a bitset (shift left by , then OR)
"split into two parts with equal sum" / "minimise the difference of two parts"Subset sum to
"assign + or − to each number to reach "Target sum → count subsets with sum
"fewest coins to make amount "Unbounded, min instead of max: dp[a] = min(dp[a], dp[a-c] + 1)
"number of combinations of coins" (order doesn't matter)Coins in the outer loop
"number of sequences / ordered ways" (order matters)Amount in the outer loop
Two budgets ("at most zeros and ones", "CPU and RAM")Multi-dimensional knapsack: dp[a][b], both loops backwards
"which items did you pick?"Keep the 2D table and walk back
Capacity up to but values smallSwap roles: minWeight[value]
Capacity huge and values huge, Meet in the middle
Items in groups, "pick at most one from each group"Group knapsack: loop groups, then capacity backwards, then items in the group

The meta-trigger: you choose a subset (or multiset) of items, and the only thing about your past choices that matters for the future is a small number — the budget used so far. If that number fits in an array (up to ~), the DP is fast.

Intuition & first principles

The one question per cell

Line up the items in any fixed order. Think about the last item, item . Any packing either leaves it out or puts it in.

  • Leave it out: the best you can do is the best packing of items with the same capacity .
  • Put it in (only if its weight fits): it uses of the capacity and earns . The rest of the bag, capacity , should be packed as well as possible from the other items: best of items with capacity , plus .

So "best for items and capacity " depends on "best for items" at two capacities: and . Repeating the argument, every subproblem is "best using the first items with capacity " — at most different questions. For our hiker that is cells instead of 16 subsets; for 100 items and a 10,000-unit bag, about a million cells instead of subsets.

Why greedy fails

Greedy by value-per-weight is optimal for the fractional knapsack (you may take part of an item): fill up on the best ratio, then take a fraction of the next. With indivisible items, the last item that "almost fits" wastes space. The hiker example shows it: greedy takes the camera (ratio 1.4) and the snack (ratio 1.0), using 6 of 7 kg for value 8; the optimum uses all 7 kg for value 9. No single greedy rule (by value, by weight, by ratio) is always right — that is the whole reason the DP exists. (The ratio greedy is still useful: the fractional optimum is an upper bound used by branch-and-bound solvers, and "the better of greedy and the single most valuable item" is always at least half the optimum.) See Greedy Algorithms for when greedy is provably safe.

The state, in words

dp[i][c] = the largest total value achievable using only items (the first items) with total weight at most .

Read "at most" carefully. With "at most", dp[i][C] is directly the answer, and dp[0][c] = 0 for every (no items, value 0). With "exactly", you would initialise unreachable weights to and take the max over the last row. Both work; mixing them up is a classic bug (see Pitfalls).

Mechanics

1. The 0/1 knapsack table

State: dp[i][c] as above, for and . Transition: for item with weight and value :

Base: dp[0][c] = 0. Order: row by row (); inside a row any order works, because a row reads only the row above. Answer: dp[n][C].

graph LR
    UP["dp[i-1][c] skip item"] -->|"max"| CUR["dp[i][c]"]
    DIAG["dp[i-1][c-w] take item"] -->|"+ v"| CUR

Each cell reads two cells of the previous row: the one directly above (skip) and the one columns to the left (take).

Dry run on the hiker's items, capacity 7:

Item0123
weight1345
value1457

The finished table (computed by the generator; row = "using the first items"):

\ capacity01234567
0 (none)00000000
1 (+ item 0: w1 v1)01111111
2 (+ item 1: w3 v4)01145555
3 (+ item 2: w4 v5)01145669
4 (+ item 3: w5 v7)01145789

A few cells, worked by hand:

Cellskip = dp[i−1][c]take = dp[i−1][c−w] + vResult
dp[2][3]dp[1][3] = 1dp[1][0] + 4 = 44 (take the tent)
dp[2][4]dp[1][4] = 1dp[1][1] + 4 = 55 (tent + snack)
dp[3][5]dp[2][5] = 5dp[2][1] + 5 = 66 (stove + snack)
dp[3][7]dp[2][7] = 5dp[2][3] + 5 = 99 (stove + tent)
dp[4][6]dp[3][6] = 6dp[3][1] + 7 = 88 (camera + snack)
dp[4][7]dp[3][7] = 9dp[3][2] + 7 = 89 (skip the camera)

The last row tells the whole story of greedy's mistake: at capacity 7, taking the camera leaves only 2 kg, where the best is 1 (the snack): .

Step through the fill. The cell being computed is amber; the cells it reads (above, and to the left in the row above) are cyan. After the table is full, the walk-back recovers the chosen items.

Every cell is max(skip = the cell above, take = the cell w to the left in the row above + v); walking back, a cell that differs from the one above took its item.

2. Getting the items back (reconstruction)

The table stores values, not choices — but the choices can be read off it. Start at (n, C). For :

  • If dp[i][c] == dp[i-1][c], item is not needed (skipping it already achieves this value). Stay at .
  • Otherwise item must have been taken. Record it and move to .

On the example: dp[4][7] = 9 = dp[3][7] → skip item 3 (camera). dp[3][7] = 9 ≠ dp[2][7] = 5 → take item 2 (stove), capacity 3. dp[2][3] = 4 ≠ dp[1][3] = 1 → take item 1 (tent), capacity 0. dp[1][0] = 0 = dp[0][0] → skip item 0. Result: items {1, 2}, weight 7, value 9.

Reconstruction needs the 2D table

The one-row version below gives the right value but overwrites the information needed to walk back. If you need the items and memory is tight, store one "taken" bit per cell ( bits, 32–64× smaller than the integers), or use Hirschberg-style divide and conquer to recover the choice in extra memory at about twice the time.

3. One row is enough — if you loop backwards

Row reads only row . So keep one array dp[0..C] that holds row before the pass for item and row after it. The pass is:

for c from C down to w:
    dp[c] = max(dp[c], dp[c - w] + v)

Why backwards? The proof. During the pass for item , call a cell "new" once it has been overwritten in this pass and "old" until then. The update at capacity needs the old value at (that's dp[i-1][c], the skip option) and the old value at (that's dp[i-1][c-w], the take option).

Invariant (backward loop): when the loop is about to process capacity , the cells are new and the cells are old.

  • It holds before the first iteration (: nothing is new yet).
  • At capacity we read cell (old, by the invariant) and cell (old, by the invariant). So we compute exactly , and cell becomes new. The invariant holds for .
  • Cells below are never written, and for them anyway (the item doesn't fit).

So after the pass the array is exactly row . ∎

What goes wrong forwards. With a forward loop, when you reach capacity , cell has already been updated in this pass — it may already contain item . Reading it and adding again puts the same item in twice.

Concrete: one item, weight 3, value 4, capacity 7, starting from all zeros.

Loopc = 3c = 4c = 5c = 6c = 7dp after
Backwards (7 → 3)reads dp[0] = 0 → 4reads dp[1] = 0 → 4reads dp[2] = 0 → 4reads dp[3] = 0 (old) → 4reads dp[4] = 0 → 40 0 0 4 4 4 4 4 ✔
Forwards (3 → 7)reads dp[0] = 0 → 4reads dp[1] = 0 → 4reads dp[2] = 0 → 4reads dp[3] = 4 (new!) → 8reads dp[4] = 4 → 80 0 0 4 4 4 8 8 ✘

The forward loop says capacity 6 is worth 8 — two tents, but there is only one. On the hiker's items, the forward loop after the very first item (the 1 kg snack) already claims capacity 7 is worth 7 (seven snacks).

The one-row array after each item (backward loop), matching the table rows above:

After itemdp[0..7]
—0 0 0 0 0 0 0 0
0 (w1 v1)0 1 1 1 1 1 1 1
1 (w3 v4)0 1 1 4 5 5 5 5
2 (w4 v5)0 1 1 4 5 6 6 9
3 (w5 v7)0 1 1 4 5 7 8 9

Inside the pass for item 2 (w4 v5), the loop visits : at it reads the old dp[3] = 4 → 9; at old dp[2] = 1 → 6; at old dp[1] = 1 → 6; at old dp[0] = 0 → 5 (no better than the existing 5).

4. Unbounded knapsack: the "bug" is the feature

If each item may be taken any number of times, the forward loop's "reuse" is exactly what we want. The 2D recurrence becomes

— note dp[i], not dp[i-1], in the take branch: after taking one copy of item , you may still take more. In one row, "read the new value at " is a forward loop:

for c from w up to C:
    dp[c] = max(dp[c], dp[c - w] + v)

The two knapsacks differ by the direction of one loop. Remember it as: backwards = each item once; forwards = each item as often as you like.

For unbounded knapsack you can also put capacity outside and items inside (for c: for item:), since the order in which copies are added doesn't matter for a max. On the hiker's items, unbounded gives 0 1 2 4 5 7 8 9 for capacities 0..7: capacity 2 is now worth 2 (two snacks) instead of 1, and capacity 7 is still 9.

5. Bounded knapsack: binary splitting (and a monotonic queue)

Item has copies. The naive approach treats them as separate 0/1 items: , slow when the counts are large.

Binary splitting. Replace copies of (w, v) by bundles of sizes and a remainder , where is the largest power with . Each bundle becomes one 0/1 item with weight and value multiplied by its size.

Example, : bundles (since and ).

Why every count is reachable, and nothing more: with bundles you can make every number (binary). Adding the bundle of 6 makes . Together: . And the bundles sum to exactly 13, so no subset exceeds the real count. In general bundles cover , and the remainder shifts that range to cover , leaving no gap. So the 0/1 knapsack over bundles explores exactly the choices "take copies".

Cost: .

Monotonic queue (the method). For one item (w, v, k), split capacities by their remainder mod : . Within one residue class, the transition is

a maximum over a sliding window of the last entries — exactly what a monotonic deque maintains in amortised . That gives per item and overall, independent of the counts. It is the standard trick in competitive programming (see cp-algorithms, "Knapsack Problem") and a nice example of a DP optimisation; more in DP Optimizations.

6. Subset sum and partition equal subset sum

Subset sum: given positive integers, is there a subset summing to exactly ? It is 0/1 knapsack where every item's value equals its weight — or, more simply, a boolean DP:

can[c] = "some subset of the items seen so far sums to exactly ". Start with can[0] = true. For each item , for from down to : can[c] = can[c] or can[c - x]. (Backwards, of course: each number is used once.)

Partition equal subset sum: can the list be split into two parts with equal sums? Only if the total is even, and then exactly when some subset sums to (the rest sums to the other ).

Trace on , , target 11 — the set of reachable sums after each number:

AfterReachable sums
start{0}
1{0, 1}
5{0, 1, 5, 6}
11{0, 1, 5, 6, 11, 12, 16, 17}
5{0, 1, 5, 6, 10, 11, 12, 16, 17, 21, 22}

11 is reachable ({11} on one side, {1, 5, 5} on the other), so the answer is true. For the total 11 is odd: false immediately.

The bitset trick. Store the reachable set as the bits of one big integer: bit is 1 iff sum is reachable. Adding item to every reachable sum is a left shift by , and "either with or without " is an OR:

bits = 1              # only sum 0
for x in items:
    bits |= bits << x
answer = (bits >> T) & 1

A machine word holds 64 bits, so each shift-OR processes 64 capacities per instruction: instead of . In C++ use std::bitset<MAXS>; in Python, the built-in arbitrary-precision int does the same thing (and is much faster than a Python loop over a list); in Java, java.util.BitSet lacks a shift, so people roll their own long[] shift. On a sum of with items this is the difference between and about word operations. The bitset works because the DP here is boolean and the transition is the same shift for every capacity; it does not apply to max-value knapsack.

7. Target sum (assign + and − signs)

Each number gets a + or − sign; count the assignments whose total is . For and there are 5 (choose which single 1 is negative).

The reduction: let be the sum of the positive numbers and of the negative ones. Then and , so

So: count subsets with sum exactly . If is odd or , the answer is 0. Counting subsets is subset sum with += instead of or: ways[c] += ways[c - x], capacity backwards, ways[0] = 1. On the example , and there are subsets of four ones.

Zeros are handled correctly by the same loop: for the update ways[c] += ways[c - 0] doubles every count, which is right — a zero can be +0 or −0, two different assignments. On with the answer is 4.

8. Coin change: fewest coins

Coins of given denominations, unlimited supply. Fewest coins to make amount , or −1 if impossible.

State: dp[a] = fewest coins summing to exactly ( if impossible). Base: dp[0] = 0. Transition: dp[a] = min over coins c ≤ a of dp[a - c] + 1. (Unbounded knapsack with min instead of max and "exactly" instead of "at most".)

For coins and : the table for is 0 1 1 2 2 1 2 2 3 3 2 3, so 3 coins (). For coins and : impossible, −1.

Greedy ("take the biggest coin that fits") is optimal for coin systems like — these are called canonical — but not in general. With and , greedy pays (3 coins), while the DP finds (2 coins). Whether a coin system is canonical can be tested in polynomial time (Pearson, 2005); most real currencies are.

9. Coin change: number of ways, and why loop order matters

"How many ways can you make 5 from coins ?" has two different correct answers, depending on whether and are the same way.

  • Combinations (order doesn't matter; LeetCode 518, CSES "Coin Combinations II"): , , , → 4.
  • Permutations / sequences (order matters; LeetCode 377, CSES "Coin Combinations I"): the 8 ordered sequences of 1s and 2s summing to 5, plus → 9.

Both use the same line, ways[a] += ways[a - c], with ways[0] = 1. The only difference is which loop is outside.

Coins outside → combinations:

for c in coins:              # each coin type processed once, in a fixed order
    for a from c to A:
        ways[a] += ways[a - c]
After coinways[0..5]
start1 0 0 0 0 0
11 1 1 1 1 1
21 1 2 2 3 3
51 1 2 2 3 4

Amount outside → permutations:

for a from 1 to A:
    for c in coins:          # "what was the LAST coin?"
        if c <= a: ways[a] += ways[a - c]

gives 1 1 2 3 5 9.

Why. In the coins-outside version, after processing coins , ways[a] counts multisets that use only those coin types. When coin is processed, each multiset is built by first choosing how many of the earlier coins to use and then adding copies of . Every multiset is generated in exactly one canonical order — sorted by coin type — so each is counted once. In the amount-outside version, ways[a] = ways[a - c] classifies sequences by their last coin, exactly like climbing stairs in the 1D DP lesson: and end in different histories and are counted separately.

graph TD
    Q["Does order matter?"] -->|"no: count multisets"| C["coins in the OUTER loop"]
    Q -->|"yes: count sequences"| P["amount in the OUTER loop"]
    C --> E1["{1,2,5}, amount 5 -> 4"]
    P --> E2["{1,2,5}, amount 5 -> 9"]

For min coins, either loop order works: the minimum doesn't care how many orders produce it.

10. Multi-dimensional knapsack: ones and zeroes

You have binary strings and two budgets: at most zeros and at most ones in total. Maximise the number of strings you can pick. Each string is an item with a two-dimensional weight (its count of zeros, its count of ones) and value 1.

State: dp[i][j] = most strings using at most zeros and ones. Transition for a string with zeros and ones: for from down to , for from down to : dp[i][j] = max(dp[i][j], dp[i - z][j - o] + 1). Both loops run backwards for the same reason as before: each string is used once.

On ["10", "0001", "111001", "1", "0"] with , , the answer is 4: "10", "0001", "1", "0" use 5 zeros and 3 ones. ("111001" alone needs 4 ones.)

Every extra budget dimension multiplies the table: budgets of size cost . That is why exact multi-dimensional knapsack is only practical for 2–3 small dimensions, and why real schedulers with CPU, memory, GPU, disk and network budgets use heuristics.

11. Pseudo-polynomial time, and why knapsack is NP-hard

The DP takes time. That looks polynomial. It is not — not in the technical sense.

Running time is measured against the size of the input, i.e. how many bits it takes to write it down. The items take about bits, but the capacity takes only bits. A capacity of is a 60-bit number — about 8 bytes of input — yet the table would need columns. In terms of the input length , can be as large as , so is exponential in the input size. An algorithm that is polynomial in the numeric value of the inputs but not in their length is called pseudo-polynomial.

Bits to write DP cells Feasible?
10014instantly
10020about a second in C++
10030no
4060no — use meet in the middle

NP-hardness. The decision version ("is there a subset with weight and value ?") is NP-complete: it is in NP (a subset is a short certificate), and subset sum — itself NP-complete (it is on Karp's 1972 list, under the name KNAPSACK) — is the special case where every value equals its weight and . So a truly polynomial algorithm for knapsack would give one for every problem in NP, which would prove P = NP. The full story (reductions, NP-completeness, why we believe P ≠ NP) is in Complexity Theory.

These two facts don't conflict. Knapsack is weakly NP-hard: it is hard only when the numbers are huge. When the numbers are polynomially bounded in (say ), the DP is polynomial. Problems that stay hard even with small numbers (bin packing, 3-partition, the travelling salesman) are strongly NP-hard, and no pseudo-polynomial algorithm for them is expected.

Deeper: approximation

Knapsack also admits a fully polynomial-time approximation scheme (FPTAS; Ibarra and Kim, 1975): round every value down to a multiple of , then run the value-indexed DP (Variations below). The answer is within a factor of optimal, in time polynomial in and . So "NP-hard" does not mean "hopeless": for knapsack you can get 99.9% of the optimum quickly. The multi-dimensional version is harder — it has no FPTAS even with two constraints unless P = NP (Kellerer, Pferschy and Pisinger, Knapsack Problems, ch. 9).

12. When the capacity is huge: meet in the middle (and value-indexed DP)

If , the capacity-indexed table is out. Two escape routes:

Small values → index by value. If the total value is small (say ), flip the roles: minW[x] = the minimum weight needed to collect value exactly . Same 0/1 loop (backwards over ), min instead of max, minW[0] = 0, others . The answer is the largest with minW[x] ≤ C. Time , independent of . (AtCoder DP Contest problem E is exactly this.)

Few items → meet in the middle. If or so and both weights and values are huge, split the items into two halves of 20. Enumerate all subsets of each half as (weight, value) pairs. Sort the right half by weight and replace each value by the best value at that weight or less (a prefix maximum, which also discards dominated pairs). Then for each left subset with weight , binary-search the right half for the largest weight and add its best value. Time instead of ; this is the Horowitz–Sahni algorithm (1974). The general technique — and the same split for subset-sum counting — is in Other Searches: meet-in-the-middle.

from bisect import bisect_right


def knapsack_mitm(weights, values, cap):
    """0/1 knapsack for n <= ~40 items with arbitrarily large weights and capacity."""
    def all_subsets(ws, vs):
        out = [(0, 0)]
        for w, v in zip(ws, vs):
            out += [(a + w, b + v) for a, b in out]      # doubling: with and without this item
        return out

    h = len(weights) // 2
    left = all_subsets(weights[:h], values[:h])
    right = sorted(all_subsets(weights[h:], values[h:]))
    rw, best_upto, run = [], [], 0
    for w, v in right:                                   # prefix max: best value at weight <= w
        run = max(run, v)
        rw.append(w)
        best_upto.append(run)
    best = 0
    for w, v in left:
        if w <= cap:
            k = bisect_right(rw, cap - w) - 1            # heaviest right subset that still fits
            best = max(best, v + best_upto[k])           # k >= 0 because (0, 0) is in right
    return best


assert knapsack_mitm([1, 3, 4, 5], [1, 4, 5, 7], 7) == 9
big = 10**15
assert knapsack_mitm([3 * big, 4 * big, 5 * big, 2 * big], [30, 50, 60, 10], 9 * big) == 110

The second test has a capacity of — far beyond any table — and the answer 110 (the items of weight and ) comes back instantly.

The ladder: brute force → better → optimal

Problem: 0/1 knapsack with items and capacity .

Rung 1: try every subset

def knapsack_brute(weights, values, cap):
    n, best = len(weights), 0
    for mask in range(1 << n):
        w = sum(weights[i] for i in range(n) if mask >> i & 1)
        if w <= cap:
            best = max(best, sum(values[i] for i in range(n) if mask >> i & 1))
    return best


assert knapsack_brute([1, 3, 4, 5], [1, 4, 5, 7], 7) == 9

time. Hopeless past , but it is the test oracle for everything below.

Rung 2: recursion with memoization (top-down)

f(i, c) = best using items with capacity = max(f(i+1, c), f(i+1, c - w_i) + v_i). Memoize on : at most states, each, so time and memory. A nice property: it only visits reachable pairs, which can be far fewer than when weights are large and few — sometimes the memoized version beats the table for that reason.

Rung 3: the 2D table (bottom-up)

time and space, no recursion depth problems, and it supports reconstruction.

Rung 4: one row, capacity backwards

time, space. The standard "production" version when only the value is needed.

Rung 5: specialised speed-ups

  • Feasibility only (subset sum): bitset, .
  • Bounded counts: binary splitting or monotonic queue .
  • Huge capacity, small values: value-indexed DP, .
  • Huge everything, small : meet in the middle, .
  • Huge everything, large : no exact polynomial method is known; use branch-and-bound/ILP solvers, or the FPTAS for a guaranteed approximation.
RungMethodTimeSpaceWhy it beats the rung above
1All subsetsBaseline; obviously correct
2Memoized recursion + stack Each (item, capacity) pair solved once
32D tableNo recursion; supports reconstruction
41D, backwardsSame speed, a factor less memory
5aBitset (feasibility)64 capacities per instruction
5bMeet in the middleIndependent of ; square root of brute force

Correctness

0/1 recurrence (optimal substructure). Let be an optimal packing of the first items within capacity . Either item : then is a feasible packing of the first items within , so . Or item : then and is a feasible packing of the first items within , so . Conversely both quantities are achieved by actual feasible packings (the optimal packing for ; the optimal packing for plus item , which fits because the rest weighs at most ). So the maximum of the two options equals the optimum. Induction on with base dp[0][c] = 0 completes the proof.

Reconstruction. If dp[i][c] ≠ dp[i-1][c], the max was achieved only by the take branch, so dp[i][c] = dp[i-1][c-w] + v and some optimal packing for contains item together with an optimal packing for — which is where the walk continues. If they are equal, an optimal packing for is also optimal for . By induction the walk outputs an optimal packing.

Backward one-row loop. Proved by the old/new invariant in Mechanics §3.

Forward one-row loop = unbounded. Invariant: when processing capacity in the pass for item , cells hold dp[i][·] (new) and cells hold dp[i-1][·] (old). So the update computes , which is the unbounded recurrence. That recurrence is correct by the same case split: an optimal unbounded packing either uses no copy of item , or removing one copy leaves an optimal packing for (with copies still allowed).

Binary splitting. Shown in §5: the bundle subset sums are exactly , so 0/1 choices over bundles correspond to choosing copies.

Coin combinations (coins outside). Claim: after processing coins , ways[a] is the number of multisets of summing to . The pass for is an unbounded forward loop, so it computes : multisets with no , plus multisets with at least one (remove one copy). These two groups are disjoint and exhaustive. ∎

Coin sequences (amount outside). ways[a] = : sequences summing to are partitioned by their last coin, and removing it leaves any sequence summing to . ∎

Target sum reduction. Sign assignments correspond one-to-one with subsets (the positive part), and the total equals iff the positive part sums to , by the two linear equations in §7.

Complexity

ProblemTimeSpaceNote
0/1 knapsack (2D)reconstruction possible
0/1 knapsack (1D)value only
Unbounded knapsackforward loop
Bounded, binary splitting
Bounded, monotonic queue
Subset sum / partition, bitset , bitset = word size, 64
Target sum
Coin change (min / ways) coin types, amount
Multi-dimensional, budgets of size ones and zeroes: for strings
Value-indexed 0/1when is huge
Meet in the middlewhen and values are huge

All the table methods are pseudo-polynomial: polynomial in and the numeric value of (or , ), exponential in the number of bits of .

Integer sizes. Values: the best value is at most , so 32-bit is fine unless values are large; use 64-bit by default. Counts (coin ways, target sum ways) grow exponentially: the number of ways to make 2000 from the coins is 23,812,353,521, already past 32 bits (the count first exceeds at amount 1367), so problems usually ask for the answer modulo . LeetCode 377's statement guarantees the final answer fits in 32 bits, but intermediate entries for amounts that are never needed can still overflow in Java/C++ — use 64-bit with a cap, or unsigned arithmetic.

Implementation

Two code groups: 0/1 knapsack with item reconstruction plus unbounded knapsack, then coin change (fewest coins, combinations and permutations). Each block runs its own tests on this lesson's examples; they were also checked against brute-force enumeration on hundreds of random small inputs.

0/1 knapsack with reconstruction, and unbounded knapsack

from typing import List, Tuple


def knapsack_01(weights: List[int], values: List[int], cap: int) -> Tuple[int, List[int]]:
    """Best value with each item used at most once, and the indices of one optimal choice."""
    n = len(weights)
    dp = [[0] * (cap + 1) for _ in range(n + 1)]        # dp[i][c]: first i items, capacity c
    for i in range(1, n + 1):
        w, v = weights[i - 1], values[i - 1]
        for c in range(cap + 1):
            dp[i][c] = dp[i - 1][c]                     # skip item i-1
            if w <= c and dp[i - 1][c - w] + v > dp[i][c]:
                dp[i][c] = dp[i - 1][c - w] + v         # take item i-1
    chosen, c = [], cap
    for i in range(n, 0, -1):                           # walk back through the table
        if dp[i][c] != dp[i - 1][c]:
            chosen.append(i - 1)
            c -= weights[i - 1]
    chosen.reverse()
    return dp[n][cap], chosen


def knapsack_01_value(weights: List[int], values: List[int], cap: int) -> int:
    """Same value in O(cap) memory: capacity loop runs BACKWARDS so each item is used once."""
    dp = [0] * (cap + 1)
    for w, v in zip(weights, values):
        for c in range(cap, w - 1, -1):
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[cap]


def knapsack_unbounded(weights: List[int], values: List[int], cap: int) -> int:
    """Unlimited copies of each item: capacity loop runs FORWARDS."""
    dp = [0] * (cap + 1)
    for w, v in zip(weights, values):
        for c in range(w, cap + 1):
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[cap]


if __name__ == "__main__":
    W, V = [1, 3, 4, 5], [1, 4, 5, 7]
    assert knapsack_01(W, V, 7) == (9, [1, 2])
    assert knapsack_01_value(W, V, 7) == 9
    assert knapsack_01(W, V, 0) == (0, [])
    assert knapsack_01([], [], 5) == (0, [])
    assert knapsack_01([10], [5], 3) == (0, [])
    assert knapsack_unbounded(W, V, 7) == 9
    assert knapsack_unbounded(W, V, 2) == 2 and knapsack_01_value(W, V, 2) == 1
    assert knapsack_unbounded([5, 10, 15], [10, 30, 20], 100) == 300
    print("knapsack tests passed")
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Knapsack {
    /** Returns the best value; fills {@code chosen} with the indices of one optimal choice. */
    static long knapsack01(int[] w, long[] v, int cap, List<Integer> chosen) {
        int n = w.length;
        long[][] dp = new long[n + 1][cap + 1];        // dp[i][c]: first i items, capacity c
        for (int i = 1; i <= n; i++)
            for (int c = 0; c <= cap; c++) {
                dp[i][c] = dp[i - 1][c];                // skip item i-1
                if (w[i - 1] <= c)
                    dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - w[i - 1]] + v[i - 1]);   // take it
            }
        chosen.clear();
        int c = cap;
        for (int i = n; i >= 1; i--)                     // walk back through the table
            if (dp[i][c] != dp[i - 1][c]) {
                chosen.add(i - 1);
                c -= w[i - 1];
            }
        Collections.reverse(chosen);
        return dp[n][cap];
    }

    static long knapsack01Value(int[] w, long[] v, int cap) {
        long[] dp = new long[cap + 1];
        for (int i = 0; i < w.length; i++)
            for (int c = cap; c >= w[i]; c--)            // BACKWARDS: each item once
                dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);
        return dp[cap];
    }

    static long knapsackUnbounded(int[] w, long[] v, int cap) {
        long[] dp = new long[cap + 1];
        for (int i = 0; i < w.length; i++)
            for (int c = w[i]; c <= cap; c++)            // FORWARDS: unlimited copies
                dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]);
        return dp[cap];
    }

    public static void main(String[] args) {
        int[] W = {1, 3, 4, 5};
        long[] V = {1, 4, 5, 7};
        List<Integer> chosen = new ArrayList<>();
        check(knapsack01(W, V, 7, chosen) == 9);
        check(chosen.equals(List.of(1, 2)));
        check(knapsack01Value(W, V, 7) == 9);
        check(knapsack01(W, V, 0, chosen) == 0 && chosen.isEmpty());
        check(knapsack01(new int[]{}, new long[]{}, 5, chosen) == 0);
        check(knapsack01(new int[]{10}, new long[]{5}, 3, chosen) == 0 && chosen.isEmpty());
        check(knapsackUnbounded(W, V, 7) == 9);
        check(knapsackUnbounded(W, V, 2) == 2 && knapsack01Value(W, V, 2) == 1);
        check(knapsackUnbounded(new int[]{5, 10, 15}, new long[]{10, 30, 20}, 100) == 300);
        System.out.println("knapsack tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

// Returns {best value, indices of one optimal choice}.
pair<long long, vector<int>> knapsack01(const vector<int>& w, const vector<long long>& v, int cap) {
    int n = w.size();
    vector<vector<long long>> dp(n + 1, vector<long long>(cap + 1, 0));
    for (int i = 1; i <= n; i++)
        for (int c = 0; c <= cap; c++) {
            dp[i][c] = dp[i - 1][c];                                  // skip item i-1
            if (w[i - 1] <= c)
                dp[i][c] = max(dp[i][c], dp[i - 1][c - w[i - 1]] + v[i - 1]);   // take it
        }
    vector<int> chosen;
    int c = cap;
    for (int i = n; i >= 1; i--)                                       // walk back
        if (dp[i][c] != dp[i - 1][c]) {
            chosen.push_back(i - 1);
            c -= w[i - 1];
        }
    reverse(chosen.begin(), chosen.end());
    return make_pair(dp[n][cap], chosen);
}

long long knapsack01Value(const vector<int>& w, const vector<long long>& v, int cap) {
    vector<long long> dp(cap + 1, 0);
    for (size_t i = 0; i < w.size(); i++)
        for (int c = cap; c >= w[i]; c--)                              // BACKWARDS: each item once
            dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
    return dp[cap];
}

long long knapsackUnbounded(const vector<int>& w, const vector<long long>& v, int cap) {
    vector<long long> dp(cap + 1, 0);
    for (size_t i = 0; i < w.size(); i++)
        for (int c = w[i]; c <= cap; c++)                              // FORWARDS: unlimited copies
            dp[c] = max(dp[c], dp[c - w[i]] + v[i]);
    return dp[cap];
}

int main() {
    vector<int> W = {1, 3, 4, 5};
    vector<long long> V = {1, 4, 5, 7};
    auto res = knapsack01(W, V, 7);
    assert(res.first == 9 && res.second == vector<int>({1, 2}));
    assert(knapsack01Value(W, V, 7) == 9);
    assert(knapsack01(W, V, 0).first == 0 && knapsack01(W, V, 0).second.empty());
    assert(knapsack01({}, {}, 5).first == 0);
    assert(knapsack01({10}, {5}, 3).first == 0);
    assert(knapsackUnbounded(W, V, 7) == 9);
    assert(knapsackUnbounded(W, V, 2) == 2 && knapsack01Value(W, V, 2) == 1);
    assert(knapsackUnbounded({5, 10, 15}, {10, 30, 20}, 100) == 300);
    cout << "knapsack tests passed\n";
    return 0;
}
function knapsack01(w: number[], v: number[], cap: number): [number, number[]] {
  const n = w.length;
  const dp: number[][] = Array.from({ length: n + 1 }, () => new Array<number>(cap + 1).fill(0));
  for (let i = 1; i <= n; i++)
    for (let c = 0; c <= cap; c++) {
      dp[i][c] = dp[i - 1][c]; // skip item i-1
      if (w[i - 1] <= c) dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - w[i - 1]] + v[i - 1]); // take it
    }
  const chosen: number[] = [];
  let c = cap;
  for (let i = n; i >= 1; i--) // walk back through the table
    if (dp[i][c] !== dp[i - 1][c]) {
      chosen.push(i - 1);
      c -= w[i - 1];
    }
  chosen.reverse();
  return [dp[n][cap], chosen];
}

function knapsack01Value(w: number[], v: number[], cap: number): number {
  const dp: number[] = new Array(cap + 1).fill(0);
  for (let i = 0; i < w.length; i++)
    for (let c = cap; c >= w[i]; c--) dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]); // BACKWARDS
  return dp[cap];
}

function knapsackUnbounded(w: number[], v: number[], cap: number): number {
  const dp: number[] = new Array(cap + 1).fill(0);
  for (let i = 0; i < w.length; i++)
    for (let c = w[i]; c <= cap; c++) dp[c] = Math.max(dp[c], dp[c - w[i]] + v[i]); // FORWARDS
  return dp[cap];
}

function check(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

const W = [1, 3, 4, 5], V = [1, 4, 5, 7];
const [best, chosen] = knapsack01(W, V, 7);
check(best === 9 && JSON.stringify(chosen) === "[1,2]");
check(knapsack01Value(W, V, 7) === 9);
check(knapsack01(W, V, 0)[0] === 0 && knapsack01(W, V, 0)[1].length === 0);
check(knapsack01([], [], 5)[0] === 0);
check(knapsack01([10], [5], 3)[0] === 0);
check(knapsackUnbounded(W, V, 7) === 9);
check(knapsackUnbounded(W, V, 2) === 2 && knapsack01Value(W, V, 2) === 1);
check(knapsackUnbounded([5, 10, 15], [10, 30, 20], 100) === 300);
console.log("knapsack tests passed");

Coin change: fewest coins, combinations, permutations

from typing import List


def min_coins(coins: List[int], amount: int) -> int:
    """Fewest coins summing to amount (unlimited supply), or -1 if impossible."""
    INF = amount + 1                                   # more than any real answer
    dp = [0] + [INF] * amount
    for c in coins:
        for a in range(c, amount + 1):                 # forwards: coins reusable
            dp[a] = min(dp[a], dp[a - c] + 1)
    return dp[amount] if dp[amount] <= amount else -1


def count_combinations(coins: List[int], amount: int) -> int:
    """Order does NOT matter: {1,2} and {2,1} are the same way. Coins in the OUTER loop."""
    ways = [1] + [0] * amount
    for c in coins:
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]


def count_sequences(coins: List[int], amount: int) -> int:
    """Order DOES matter: [1,2] and [2,1] are different. Amount in the OUTER loop."""
    ways = [1] + [0] * amount
    for a in range(1, amount + 1):
        for c in coins:                                # classify by the last coin
            if c <= a:
                ways[a] += ways[a - c]
    return ways[amount]


if __name__ == "__main__":
    assert min_coins([1, 2, 5], 11) == 3
    assert min_coins([2], 3) == -1
    assert min_coins([1, 3, 4], 6) == 2               # greedy would use 3 coins
    assert min_coins([7], 0) == 0
    assert count_combinations([1, 2, 5], 5) == 4
    assert count_sequences([1, 2, 5], 5) == 9
    assert count_combinations([1, 2, 3], 4) == 4 and count_sequences([1, 2, 3], 4) == 7
    assert count_combinations([2], 3) == 0
    assert count_combinations([10], 10) == 1
    assert count_combinations([5], 0) == 1 and count_sequences([5], 0) == 1
    print("coin change tests passed")
import java.util.Arrays;

public class CoinChange {
    static int minCoins(int[] coins, int amount) {
        int INF = amount + 1;                          // more than any real answer
        int[] dp = new int[amount + 1];
        Arrays.fill(dp, INF);
        dp[0] = 0;
        for (int c : coins)
            for (int a = c; a <= amount; a++)          // forwards: coins reusable
                dp[a] = Math.min(dp[a], dp[a - c] + 1);
        return dp[amount] <= amount ? dp[amount] : -1;
    }

    /** Order does NOT matter. Coins in the OUTER loop. */
    static long countCombinations(int[] coins, int amount) {
        long[] ways = new long[amount + 1];
        ways[0] = 1;
        for (int c : coins)
            for (int a = c; a <= amount; a++)
                ways[a] += ways[a - c];
        return ways[amount];
    }

    /** Order DOES matter. Amount in the OUTER loop. */
    static long countSequences(int[] coins, int amount) {
        long[] ways = new long[amount + 1];
        ways[0] = 1;
        for (int a = 1; a <= amount; a++)
            for (int c : coins)                        // classify by the last coin
                if (c <= a) ways[a] += ways[a - c];
        return ways[amount];
    }

    public static void main(String[] args) {
        check(minCoins(new int[]{1, 2, 5}, 11) == 3);
        check(minCoins(new int[]{2}, 3) == -1);
        check(minCoins(new int[]{1, 3, 4}, 6) == 2);
        check(minCoins(new int[]{7}, 0) == 0);
        check(countCombinations(new int[]{1, 2, 5}, 5) == 4);
        check(countSequences(new int[]{1, 2, 5}, 5) == 9);
        check(countCombinations(new int[]{1, 2, 3}, 4) == 4 && countSequences(new int[]{1, 2, 3}, 4) == 7);
        check(countCombinations(new int[]{2}, 3) == 0);
        check(countCombinations(new int[]{10}, 10) == 1);
        check(countCombinations(new int[]{5}, 0) == 1 && countSequences(new int[]{5}, 0) == 1);
        System.out.println("coin change tests passed");
    }

    static void check(boolean ok) {
        if (!ok) throw new AssertionError("test failed");
    }
}
#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

int minCoins(const vector<int>& coins, int amount) {
    int INF = amount + 1;                              // more than any real answer
    vector<int> dp(amount + 1, INF);
    dp[0] = 0;
    for (int c : coins)
        for (int a = c; a <= amount; a++)              // forwards: coins reusable
            dp[a] = min(dp[a], dp[a - c] + 1);
    return dp[amount] <= amount ? dp[amount] : -1;
}

// Order does NOT matter. Coins in the OUTER loop.
long long countCombinations(const vector<int>& coins, int amount) {
    vector<long long> ways(amount + 1, 0);
    ways[0] = 1;
    for (int c : coins)
        for (int a = c; a <= amount; a++)
            ways[a] += ways[a - c];
    return ways[amount];
}

// Order DOES matter. Amount in the OUTER loop.
long long countSequences(const vector<int>& coins, int amount) {
    vector<long long> ways(amount + 1, 0);
    ways[0] = 1;
    for (int a = 1; a <= amount; a++)
        for (int c : coins)                            // classify by the last coin
            if (c <= a) ways[a] += ways[a - c];
    return ways[amount];
}

int main() {
    assert(minCoins({1, 2, 5}, 11) == 3);
    assert(minCoins({2}, 3) == -1);
    assert(minCoins({1, 3, 4}, 6) == 2);
    assert(minCoins({7}, 0) == 0);
    assert(countCombinations({1, 2, 5}, 5) == 4);
    assert(countSequences({1, 2, 5}, 5) == 9);
    assert(countCombinations({1, 2, 3}, 4) == 4 && countSequences({1, 2, 3}, 4) == 7);
    assert(countCombinations({2}, 3) == 0);
    assert(countCombinations({10}, 10) == 1);
    assert(countCombinations({5}, 0) == 1 && countSequences({5}, 0) == 1);
    cout << "coin change tests passed\n";
    return 0;
}
function minCoins(coins: number[], amount: number): number {
  const INF = amount + 1; // more than any real answer
  const dp: number[] = new Array(amount + 1).fill(INF);
  dp[0] = 0;
  for (const c of coins)
    for (let a = c; a <= amount; a++) dp[a] = Math.min(dp[a], dp[a - c] + 1); // forwards
  return dp[amount] <= amount ? dp[amount] : -1;
}

// Order does NOT matter. Coins in the OUTER loop.
function countCombinations(coins: number[], amount: number): number {
  const ways: number[] = new Array(amount + 1).fill(0);
  ways[0] = 1;
  for (const c of coins)
    for (let a = c; a <= amount; a++) ways[a] += ways[a - c];
  return ways[amount];
}

// Order DOES matter. Amount in the OUTER loop.
function countSequences(coins: number[], amount: number): number {
  const ways: number[] = new Array(amount + 1).fill(0);
  ways[0] = 1;
  for (let a = 1; a <= amount; a++)
    for (const c of coins) if (c <= a) ways[a] += ways[a - c]; // classify by the last coin
  return ways[amount];
}

function check(ok: boolean, msg = "test failed"): void {
  if (!ok) throw new Error(msg);
}

check(minCoins([1, 2, 5], 11) === 3);
check(minCoins([2], 3) === -1);
check(minCoins([1, 3, 4], 6) === 2);
check(minCoins([7], 0) === 0);
check(countCombinations([1, 2, 5], 5) === 4);
check(countSequences([1, 2, 5], 5) === 9);
check(countCombinations([1, 2, 3], 4) === 4 && countSequences([1, 2, 3], 4) === 7);
check(countCombinations([2], 3) === 0);
check(countCombinations([10], 10) === 1);
check(countCombinations([5], 0) === 1 && countSequences([5], 0) === 1);
console.log("coin change tests passed");

Notes on the choices: min_coins uses amount + 1 as "infinity" (no answer can use more than amount coins when every coin is at least 1), which avoids overflow from INT_MAX + 1. The counting functions use 64-bit integers; for real problems apply the modulus inside the loop. TypeScript number is exact only up to — use bigint or a modulus for large counts.

Real-world uses

  • Capital budgeting. Choosing which projects to fund under a budget, each project all-or-nothing, is 0/1 knapsack; with several budget periods it is multi-dimensional knapsack. Lorie and Savage posed the problem in 1955 ("Three Problems in Rationing Capital", Journal of Business), and H. Martin Weingartner's 1963 book Mathematical Programming and the Analysis of Capital Budgeting Problems formulated it as an integer program. Portfolio-selection tools in large firms still solve such models with integer-programming solvers, which use knapsack bounds internally.
  • Cutting stock. A paper mill cuts large rolls into customer widths with minimum waste. Gilmore and Gomory (Operations Research, 1961 and 1963) solved it by column generation: a linear program chooses how many times to use each cutting pattern, and each new pattern is found by solving a knapsack problem (pack widths into one roll, valued by the LP's dual prices). This is still the textbook method, and it is used in paper, steel, glass and textile industries.
  • Cluster scheduling. Placing tasks with CPU and memory requests onto machines is a multi-dimensional bin-packing / knapsack problem, NP-hard in general. Production schedulers therefore use heuristics: Google's Borg scores feasible machines with a hybrid of best-fit and worst-fit designed to reduce "stranded" resources (Verma et al., "Large-scale cluster management at Google with Borg", EuroSys 2015), and the Kubernetes scheduler filters nodes and scores them with plugins such as NodeResourcesFit (strategies LeastAllocated, MostAllocated, RequestedToCapacityRatio). See Kubernetes Resource Management. Exact knapsack DPs appear in smaller sub-decisions, such as packing jobs into one node or choosing which batch jobs to admit within a quota.
  • Change-making. Vending machines and cash registers use greedy change because real coin systems are designed to be canonical; the DP is the safety net for non-canonical systems, and Pearson's polynomial-time test (2005) decides which case applies.
  • Cryptography (a cautionary tale). The Merkle–Hellman knapsack cryptosystem (1978) based its security on subset sum. Adi Shamir broke the basic scheme in 1982 because its "easy" super-increasing structure could be recovered, and lattice-reduction attacks (Lagarias and Odlyzko, 1985) broke many low-density variants. The lesson: NP-hardness of the worst case does not make typical instances hard. See Cryptography for Engineers.
  • Budgeted selection in software (illustrative). "Run the most valuable tests within a 10-minute CI budget", "load the most useful features within a 5 MB model-size budget", "choose ad creatives to fill a fixed slot length" — each is a small 0/1 knapsack, and with budgets of a few thousand units the DP runs in microseconds.

Pitfalls & edge cases

  • Forward loop in 0/1 knapsack. Silently reuses items. The single most common knapsack bug. Backwards for 0/1, forwards for unbounded.
  • "At most" vs "exactly". Initialising the whole row to 0 means "capacity at most ". For "exactly " (coin change, subset sum counts, "fill the bag completely"), initialise dp[0] = 0 (or 1 for counts) and every other entry to / / 0 as appropriate. Using 0 for unreachable entries in a "max value, exactly " problem returns values for weights that can't be formed.
  • Wrong loop order in coin counting. Coins outside = combinations; amount outside = sequences. Write down which one the problem wants before coding.
  • Target sum parity and range. Check (S + T) % 2 == 0 and |T| <= S before indexing; negative gives a negative array index otherwise.
  • Zeros in target sum and subset counting. They double the count; that is correct, not a bug — but forward-looping a zero-weight item would loop forever in an unbounded variant (dp[c] += dp[c] in an infinite-supply interpretation is meaningless). Unbounded knapsack with zero-weight positive-value items has an infinite answer; handle it explicitly.
  • Reconstruction from the 1D array. Impossible; keep the 2D table or decision bits.
  • Huge capacity. means a -entry array. Check the constraints: if values are small, index by value; if , meet in the middle.
  • Overflow. Counts overflow quickly; use 64-bit and the requested modulus. In min-coin DPs, INT_MAX + 1 overflows to a negative number and wins every min — use amount + 1 as infinity.
  • Off-by-one between items and rows. Row uses item . Padding with a row 0 for "no items" removes special cases.
  • Greedy temptation. Ratio-greedy is optimal only for fractional knapsack; largest-coin-first only for canonical coin systems.

Variations

  • Value-indexed knapsack (huge , small values): minW[value], as in §12.
  • Group knapsack: items in groups, at most one per group. Loop groups; inside, capacity backwards; innermost, the items of the group (so two items of one group never combine).
  • Knapsack with dependencies (an item may be taken only if its parent is): tree knapsack, merging children's capacity arrays; see Tree DP.
  • Count the optimal packings, or find the lexicographically smallest one: carry a count (or compare index lists) alongside each value.
  • -th best value, or the top- packings: keep a sorted list of the best values per cell and merge.
  • Minimum difference partition (LeetCode 1049): subset sum up to ; the answer is .
  • Profit with a minimum threshold (LeetCode 879 "Profitable Schemes"): one dimension capped at "profit at least " — store min(profit, P) so the dimension stays small.
  • Fractional knapsack: greedy by ratio, ; see Greedy Algorithms.
  • Very large with small weights: group equal weights and use bounded knapsack; with only distinct weights the monotonic-queue method is .
  • Subset-sum counting for with huge values: meet in the middle with counts (Other Searches).
  • Exact solvers for large instances: branch-and-bound with the fractional bound, and Pisinger's specialised algorithms, solve many real instances with thousands of items quickly even though the worst case is exponential.

Practice ladder

Each problem is described in my own words; follow the link for the full statement.

1. Knapsack 1 (AtCoder DP Contest D) — Classic 0/1 knapsack, up to 100 items and capacity . Teaches the base recurrence and the backward 1D loop.

Hint

dp[c] = max(dp[c], dp[c - w] + v), c from W down to w. Values reach : use 64-bit.

2. Book Shop (CSES 1158) — Buy books with a money limit to maximise total pages; each book once. Teaches 0/1 knapsack under a tight time limit.

Hint

Same as above with price as weight, pages as value. 1000 books × budget = simple operations: fine in C++, use the 1D array.

3. Partition Equal Subset Sum (LeetCode 416) — Split into two equal-sum halves. Teaches subset sum and the bitset trick.

Solution
def can_partition(nums):
    total = sum(nums)
    if total % 2:
        return False
    bits = 1                              # bit s set <=> some subset sums to s
    for x in nums:
        bits |= bits << x
    return (bits >> (total // 2)) & 1 == 1


assert can_partition([1, 5, 11, 5])
assert not can_partition([1, 2, 3, 5])

4. Coin Change (LeetCode 322) — Fewest coins for an amount. Teaches unbounded knapsack with min and "exactly".

Hint

dp[0] = 0, others "infinity" (amount + 1); forward loop. The code above is a full solution.

5. Coin Change II (LeetCode 518) — Count combinations. Teaches coins-outside counting.

Hint

Coins in the outer loop. ways[0] = 1.

6. Combination Sum IV (LeetCode 377) — Count ordered sequences (despite the name). Teaches amount-outside counting.

Hint

Amount in the outer loop; it is climbing stairs with the coins as step sizes.

7. Coin Combinations I (CSES 1635) and II (CSES 1636) — The same pair under a modulus. Good for checking you can switch loop orders on demand.

Hint

I counts ordered ways (amount outside); II counts unordered ways (coins outside). Apply % (10**9 + 7) inside the loop.

8. Target Sum (LeetCode 494) — Signs on numbers to hit a target. Teaches algebraic reduction to subset counting.

Solution
def find_target_sum_ways(nums, target):
    s = sum(nums)
    if abs(target) > s or (s + target) % 2:
        return 0
    p = (s + target) // 2                 # sum of the numbers that get a '+'
    ways = [1] + [0] * p
    for x in nums:
        for c in range(p, x - 1, -1):     # backwards: each number once
            ways[c] += ways[c - x]
    return ways[p]


assert find_target_sum_ways([1, 1, 1, 1, 1], 3) == 5
assert find_target_sum_ways([0, 0, 1], 1) == 4
assert find_target_sum_ways([1], 2) == 0

9. Last Stone Weight II (LeetCode 1049) — Smash stones; minimise what's left. Teaches spotting a hidden partition.

Hint

The final weight is for some split of the stones into two groups. Find the largest subset sum .

10. Money Sums (CSES 1745) — List every sum that some subset of coins can make. Teaches reading the whole reachable set.

Hint

Boolean subset-sum DP (or bitset) up to the total; print the set bits except 0.

11. Ones and Zeroes (LeetCode 474) — Two budgets. Teaches multi-dimensional knapsack.

Solution
def find_max_form(strs, m, n):
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    for s in strs:
        z = s.count("0")
        o = len(s) - z
        for i in range(m, z - 1, -1):     # both budgets backwards: each string once
            for j in range(n, o - 1, -1):
                dp[i][j] = max(dp[i][j], dp[i - z][j - o] + 1)
    return dp[m][n]


assert find_max_form(["10", "0001", "111001", "1", "0"], 5, 3) == 4
assert find_max_form(["10", "0", "1"], 1, 1) == 2

12. Number of Dice Rolls With Target Sum (LeetCode 1155) — dice with faces, count rolls summing to a target. Teaches group knapsack (each die is a group: pick exactly one face).

Hint

ways[i][t] = sum over face f of ways[i-1][t-f]. Exactly one per group means you build a fresh row per die rather than updating in place.

13. Two Sets II (CSES 1093) — Count ways to split into two equal-sum sets. Teaches subset counting and halving for symmetric pairs.

Hint

Count subsets of with sum , then divide by 2 (each split is counted once from each side) — using the modular inverse of 2.

14. Knapsack 2 (AtCoder DP Contest E) — Capacity up to , values small. Teaches swapping the roles of weight and value.

Solution
def knapsack_by_value(weights, values, cap):
    total = sum(values)
    INF = float("inf")
    min_w = [0] + [INF] * total           # min weight to collect exactly this value
    for w, v in zip(weights, values):
        for x in range(total, v - 1, -1):
            if min_w[x - v] + w < min_w[x]:
                min_w[x] = min_w[x - v] + w
    return max(x for x in range(total + 1) if min_w[x] <= cap)


assert knapsack_by_value([1, 3, 4, 5], [1, 4, 5, 7], 7) == 9
assert knapsack_by_value([10**9, 5 * 10**8], [10, 6], 10**9) == 10

15. Profitable Schemes (LeetCode 879) — Count crime subsets with at most members and at least profit. Teaches a capped "at least" dimension.

Hint

dp[g][p] = number of schemes using members with profit . Loop crimes; both dimensions backwards; clamp profit at .

Common mistakes & interview follow-ups

"Why does the inner loop go backwards?" Give the old/new invariant: backwards means dp[c - w] is still the previous row's value, so each item is used at most once. Then show the 1-item counterexample (weight 3, capacity 6 → two copies forwards).

"Now allow unlimited copies." Flip the loop to forwards. That's the whole change.

"Coin change II gives the wrong count — why?" Almost always the loops are swapped and it is counting sequences. Show , amount 5: 4 vs 9.

"Which items did you take?" Keep the 2D table and walk back (dp[i][c] != dp[i-1][c] ⇒ taken). If memory matters, keep one bit per cell.

"Is this polynomial?" No: is pseudo-polynomial, exponential in the bit length of . Knapsack is NP-hard; the DP is fast only when is modest. Mention the alternatives for huge : value-indexed DP, meet in the middle, FPTAS.

"Can greedy work?" For fractional knapsack, yes (by ratio). For 0/1, no — show the hiker example (greedy 8, optimum 9). For coins, only for canonical systems — show , amount 6.

"What if there are two constraints (weight and volume)?" Add a dimension; cost multiplies by the second budget. Beyond 2–3 small dimensions, use ILP solvers or heuristics.

"Memory limit is tight and doesn't fit, but you need the items." Store decision bits ( bytes), or use divide and conquer: compute the forward DP on the first half of the items and the backward DP on the second half, find the best capacity split, and recurse on each half (Hirschberg's trick).

Mistakes interviewers watch for: forward loop in 0/1; swapped loops in counting; INT_MAX + 1 overflow in min-coins; forgetting (S + T) parity in target sum; "at most" vs "exactly" initialisation; claiming the DP is polynomial.

Quick quiz

1. In the hiker's table, why is dp[4][7] = 9 and not 8?

Answer

Taking the camera (w5, v7) leaves capacity 2, where the best is dp[3][2] = 1: total 8. Skipping it keeps dp[3][7] = 9 (tent + stove). The max is 9.

2. One item (weight 2, value 3), capacity 6, 1D array, forward loop. What is dp[6], and what does it mean?

Answer

dp[6] = 9: three copies of the item. The forward loop computes the unbounded knapsack. Backwards gives 3.

3. Coins , amount 3. How many combinations, and how many sequences?

Answer

Combinations: {1,1,1}, {1,2} → 2. Sequences: 1+1+1, 1+2, 2+1 → 3.

4. Target sum with numbers and target 4. What subset sum do you count, and what is the answer?

Answer

, . Subsets summing to 7: {2, 5} only → 1 way ().

5. A problem has items, capacity , and values up to 1000. Which method do you use?

Answer

Value-indexed DP: total value is at most 50,000, so minW[value] has 50,001 entries, steps. The capacity-indexed table is impossible, and meet in the middle at ( per half) is much slower.

6. Why is called pseudo-polynomial?

Answer

is written with about bits, so can be exponential in the input length. The running time is polynomial in the numeric value of but not in the size of the input.

Further reading / sources

  • Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms (CLRS), 4th ed. — Chapter 14 (dynamic programming), §15.2 on 0/1 vs fractional knapsack (greedy vs DP), and Chapter 34 (NP-completeness, including subset sum).
  • Jon Kleinberg and Éva Tardos, Algorithm Design (2005) — §6.4 "Subset Sums and Knapsacks: Adding a Variable" and §11.8 (an FPTAS for knapsack).
  • Hans Kellerer, Ulrich Pferschy, David Pisinger, Knapsack Problems (Springer, 2004) — the reference monograph: bounded, unbounded, multi-dimensional, approximation.
  • Silvano Martello and Paolo Toth, Knapsack Problems: Algorithms and Computer Implementations (Wiley, 1990).
  • Richard M. Karp, "Reducibility Among Combinatorial Problems", in Complexity of Computer Computations (1972).
  • Ellis Horowitz and Sartaj Sahni, "Computing Partitions with Applications to the Knapsack Problem", Journal of the ACM 21(2), 1974 — meet in the middle.
  • Oscar H. Ibarra and Chul E. Kim, "Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems", Journal of the ACM 22(4), 1975 — the FPTAS.
  • P. C. Gilmore and R. E. Gomory, "A Linear Programming Approach to the Cutting-Stock Problem", Operations Research 9(6), 1961.
  • David Pearson, "A polynomial-time algorithm for the change-making problem", Operations Research Letters 33(3), 2005.
  • Ralph Merkle and Martin Hellman, "Hiding information and signatures in trapdoor knapsacks", IEEE Transactions on Information Theory 24(5), 1978; Adi Shamir, "A polynomial time algorithm for breaking the basic Merkle–Hellman cryptosystem", FOCS 1982.
  • Abhishek Verma et al., "Large-scale cluster management at Google with Borg", EuroSys 2015.
  • cp-algorithms, Knapsack Problem — binary splitting and the monotonic-queue method for bounded knapsack.
  • AtCoder Educational DP Contest, problem list — problems D and E.

Lessons: previous — 1D DP & Classic Sequences · next — Sequence DP · module — Dynamic Programming · course — DSA: Zero to Mastery.

Related Archon pages: 1D DP & Classic Sequences · Grid DP · Greedy Algorithms · Other Searches (meet in the middle) · Bit Manipulation · Monotonic Stack & Deque · Complexity Analysis · Complexity Theory · DP Optimizations.