LearnAbout

Knapsack Patterns

On this page
Quick reference
0/1 Knapsack — full 2D tableO(n × capacity)
0/1 Knapsack — 1D, backward scanO(n × capacity)
Unbounded Knapsack (Coin Change, etc.)O(n × capacity)
The Idea

You pack a hiking backpack. Every item that you could bring has a weight and a "how much you would miss it" value. The bag holds only so much weight before your shoulders give out. You want the combination of items that packs the most value in without going over the limit. This is the knapsack problem. It is the same "remember what you have already solved" idea as every other DP topic so far, but with a budget (capacity) as the second axis instead of a grid coordinate.

The core insight: dp[i][capacity] = the best value you can reach with only the first i items and this much capacity left to spend. For each item, there are exactly two choices. Leave it out, in which case dp[i][capacity] is whatever it was without this item (dp[i-1][capacity]). Or take it, in which case you gain its value but spend its weight (its value + dp[i-1][capacity - its weight]). dp[i][capacity] is whichever of those two is bigger. That is the whole algorithm. Everything below is to apply it carefully.

0/1 knapsack means that each item can be used at most one time: you either pack it or you do not. Unbounded knapsack means that each item can be used any number of times, like coins when you make change. It is the same recurrence shape, with one small but critical difference in how the loop runs. Build It below makes that difference concrete.
Build It
0/1 vs. unbounded — same table, opposite scan direction
# dp[i][capacity] = best value using the first i items, this much capacity left
function knapsack01(items, capacity):
    dp = 2D array, (n + 1) x (capacity + 1), all zeros
    for i from 1 to n:
        for c from 0 to capacity:
            dp[i][c] = dp[i - 1][c]                        // leave item i-1 out
            if items[i - 1].weight <= c:
                dp[i][c] = max(dp[i][c],
                                items[i - 1].value + dp[i - 1][c - items[i - 1].weight])  // take it
    return dp[n][capacity]
0/1 Knapsack — full 2D table
function knapsack01(weights, values, capacity):
    n = len(weights)
    dp = 2D array, (n + 1) x (capacity + 1), all zeros
    for i from 1 to n:
        for c from 0 to capacity:
            dp[i][c] = dp[i - 1][c]                    // do not take item i-1
            if weights[i - 1] <= c:
                dp[i][c] = max(dp[i][c], values[i - 1] + dp[i - 1][c - weights[i - 1]])   // take it
    return dp[n][capacity]
dp[0][*] = 0 (no items means no value, at any capacity) is the whole base case, and it comes naturally from the init of the table to zeros. There is no special case needed here, unlike the first row and column in Grid DP.
0/1 Knapsack, space-optimized — 1D, capacity iterated BACKWARDS
function knapsack01(weights, values, capacity):
    dp = array of size capacity + 1, all zeros
    for i from 0 to len(weights) - 1:
        for c from capacity down to weights[i]:          // ⚠ backwards, not forwards
            dp[c] = max(dp[c], values[i] + dp[c - weights[i]])
    return dp[capacity]
To iterate capacity backwards means that dp[c - weights[i]] on the right-hand side still refers to the LAST item's table (the row above, in 2D terms). It has not been overwritten yet for this item. If you iterate forwards instead, dp[c - weights[i]] might already reflect item i as used, which lets the same item be counted two times in one pass. This single direction flip is the whole difference between 0/1 and unbounded knapsack.
Unbounded Knapsack (e.g. Coin Change) — capacity iterated FORWARDS
function coinChange(coins, amount):
    dp = array of size amount + 1
    dp[0] = 0
    for c from 1 to amount:
        dp[c] = infinity
    for c from 1 to amount:                    // forward: reuse is intentional
        for coin in coins:
            if coin <= c:
                dp[c] = min(dp[c], 1 + dp[c - coin])
    return dp[amount] if dp[amount] != infinity else -1
To scan capacity forward means that dp[c - coin] can already include this same coin used earlier in this same pass, which is exactly what "unlimited supply of each coin" requires. That forward direction is the one-line difference from the backward scan of 0/1 knapsack. It is not a stylistic choice. If you get it backward here, coins can never be reused, which is a different, wrong problem.
Know It

The 2D table of 0/1 knapsack costs O(n × capacity) time and space, one entry per (item count, capacity) pair, each filled in O(1). The 1D rolling trick above drops space to O(capacity): only the previous item's row is ever read. Unbounded knapsack has the identical O(n × capacity) time and space shape. The forward-versus-backward scan changes correctness, not the asymptotic cost.

OperationTimeSpaceWhy
0/1 Knapsack — full 2D tableO(n × capacity)O(n × capacity)One dp[i][c] is computed per (item, capacity) pair, with O(1) work each.
0/1 Knapsack — 1D, backward scanO(n × capacity)O(capacity)The same number of cells is filled. Only one row of the table needs to exist at a time, because each item's row reads only the row before it.
Unbounded Knapsack (Coin Change, etc.)O(n × capacity)O(capacity)This is the same shape as the 1D version of 0/1. The forward scan is what allows reuse, not a change in how many cells are touched.
Break It

Iterating capacity forward in the 0/1 space-optimized version

the 1D dp array is scanned low-to-high instead of high-to-low

This is the most important knapsack bug, worth real attention. In the 1D version, dp[c - weight] on the right-hand side must still be the "last item's" value. A forward scan updates a smaller capacity first. A larger capacity's update then reads that already-updated (this item's) value. This quietly lets the same item be packed two times in one call, which turns 0/1 knapsack into unbounded knapsack by accident. The fix is always: 0/1 scans capacity backward.

Confusing 0/1 vs. unbounded iteration direction for the problem actually being solved

an item can be reused (coins, unlimited stock) but the code scans backward, or the reverse

The two scan directions are not interchangeable defaults. Which one is correct depends completely on whether the problem allows reuse of an item. Partition Equal Subset Sum (each number used one time) needs the backward scan. Coin Change (each coin denomination reusable) needs the forward scan. To copy one pattern onto the other problem produces code that runs fine and returns a plausible-looking wrong answer.

Getting dp[0][*] / dp[*][0] base cases backwards

zero items or zero capacity

dp[0][c] = 0 for every c (no items to choose from means zero value, however much room there is). dp[i][0] = 0 for every i (no room means nothing fits, however many options there are). If you swap which index represents "items used" and which represents "capacity", or seed only one of the two zero-rows, you produce a table that is correct in one direction and quietly wrong in the other.

Trusting greedy instead of knapsack DP

you pick items by best value-to-weight ratio first, for 0/1 knapsack

The coin-change counterexample from Basic Greedy applies here directly. 0/1 knapsack is exactly a case where the greedy "take the best ratio first" instinct is provably not optimal. Consider capacity 10 with items (weight 6, value 30), (weight 5, value 24), and (weight 5, value 24). Greedy takes the weight-6 item first (the best ratio, value 5.0) and then has room for nothing else, for a total of 30. But to skip it for the two weight-5 items gives 48. Greedy locks in a choice that it can never undo. Knapsack DP considers both options at every step and cannot be fooled this way.

Use It
Partition Equal Subset Sum
This is 0/1 knapsack in disguise: can a subset of nums sum to exactly total/2? The capacity is total/2. The "value" and "weight" of each number are the number itself. Scan backward.
Medium
Target Sum
Reframe the +/- assignments as a subset-sum split (the positives sum to P, the negatives to N, P - N = target, P + N = total). Then it is the shape of Partition Equal Subset Sum, but you count ways instead of only a check of feasibility.
Medium
Coin Change
Use coinChange() from Build It, exactly. This is the unbounded knapsack shape, and a direct callback to the coin-change counterexample in Basic Greedy (why greedy fails on denominations like {1, 3, 4}).
Medium
Coin Change II
Use the same unbounded shape as Coin Change, but count combinations instead of a minimum of coins: dp[c] += dp[c - coin]. Put coins as the outer loop so that order does not create duplicate combinations.
Medium
Last Stone Weight II
This is equivalent to Partition Equal Subset Sum. Find the subset closest to total/2. The answer is total - 2 × (the best subset sum that you can reach).
Medium
Ones and Zeroes
This is 0/1 knapsack with two capacities at once: dp[zeros][ones]. Scan both backward per string. To take each string costs some of the zero-budget and some of the one-budget.
Medium
Perfect Squares
This is the unbounded knapsack shape. The "coins" are 1², 2², 3², ... up to n. Minimize how many of them sum to exactly n.
Medium
Combination Sum IV
Review this from Backtracking, now solved with unbounded-knapsack DP instead of an exhaustive search. But order matters this time (different orderings count as different combinations). So capacity is the outer loop and the candidates are the inner loop, the reverse of Coin Change II.
Medium