The knapsack family

Items have a weight and a value, the bag holds capacity C, and you want the most value that fits. Every variant of that — subset sum, partition, coin change, counting the ways to hit a target — is the same table with a different operator in the cell, and one decision separates the two halves of the family: may an item be used once, or as many times as you like?

That decision shows up as the direction of one for loop. Nothing else changes.

The table underneath

Start two-dimensional, with dp[i][c] = the best value using the first i items within capacity c. At item i there are two options:

dp[i][c] = max(dp[i-1][c],              # skip item i
               dp[i-1][c - w] + v)      # take it, if w <= c

n x C states, constant work each, so O(n x C) time — the product from what DP actually is. Row i reads only row i-1, so exactly as in two sequences the table rolls down to a single array of C+1 cells.

The direction of the inner loop

Once rolled, both variants are one line:

dp[c] = max(dp[c], dp[c - w] + v)

The question is what dp[c - w] contains at the moment you read it.

Downward (c from C to w) reaches c - w before it has been rewritten in this round, so it still holds the value from row i-1 — a state in which item i has not been used. Adding item i to it uses the item exactly once. That is 0/1.

Upward (c from w to C) reaches c - w after rewriting it this round, so it may already contain a copy of item i. Adding another copy is legal, and the same item can pile up as many times as the capacity allows. That is unbounded.

One row of a knapsack table swept downward and upward, showing which cells were already updated when dp[4] reads dp[2]100%−+FitSVGEsc

Scroll to zoom · drag to pan · 0 fits · Esc closes

def knapsack_01(items, C):                    # each item at most once
    dp = [0] * (C + 1)
    for w, v in items:
        for c in range(C, w - 1, -1):         # downward
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[C]


def knapsack_unbounded(items, C):             # unlimited copies
    dp = [0] * (C + 1)
    for w, v in items:
        for c in range(w, C + 1):             # upward
            dp[c] = max(dp[c], dp[c - w] + v)
    return dp[C]

Writing range(C, w - 1, -1) when you meant unbounded produces an answer that is too small and passes small tests, because with distinct weights the two agree until an item can usefully repeat. Say which one you need before you type the loop.

Subset sum and partition

Drop the values and the max becomes an or. dp[c] is now a boolean: can some subset sum to exactly c?

def subset_sum(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True                              # the empty subset makes 0
    for x in nums:
        for c in range(target, x - 1, -1):    # 0/1: each number once
            dp[c] = dp[c] or dp[c - x]
    return dp[target]

dp[0] = True is the base case that makes the first number land anywhere. Without it the whole array stays false.

Partition — split the numbers into two groups of equal sum — is subset sum with one line of setup. The total S must be even, or the answer is no immediately; otherwise ask whether any subset sums to S / 2, since the complement then matches it. With 200 numbers summing to 20,000 that is 200 x 10,001 ≈ 2 million cell updates, a few milliseconds of real work.

Coin change, both ways

Coins are unbounded by definition, so the capacity loop goes upward. Minimising:

def min_coins(coins, amount):
    INF = float('inf')
    dp = [0] + [INF] * amount
    for coin in coins:
        for c in range(coin, amount + 1):
            dp[c] = min(dp[c], dp[c - coin] + 1)
    return -1 if dp[amount] == INF else dp[amount]

Counting is the same loop with + instead of min — and here the nesting order matters, which is a separate trap from the direction:

def count_ways(coins, amount):
    dp = [1] + [0] * amount
    for coin in coins:                        # coins outside: combinations
        for c in range(coin, amount + 1):
            dp[c] += dp[c - coin]
    return dp[amount]

With coins of 1 and 2 and an amount of 3, this returns 2: the multisets 1+1+1 and 1+2. Swap the loops so capacity is outside and coins inside and it returns 3, because 1+2 and 2+1 are then counted separately. Neither is wrong: coins outside counts unordered combinations, capacity outside counts ordered sequences. Read the problem to see which it wants.

For minimising, both nestings give the same result, which is why the distinction surprises people the first time counting goes wrong.

The pseudo-polynomial warning

O(n x C) looks polynomial and is not. C is a value in the input, not a measure of its size: writing 10^9 takes 30 bits, so a knapsack instance with 100 items and C = 10^9 fits in a few hundred bytes and still needs 100 x 10^9 = 10^11 cell updates — about 1,000 seconds at the 10^8 simple operations per second used in complexity by counting. The runtime is exponential in the length of the input. This is what "pseudo-polynomial" means, and it is why 0/1 knapsack is NP-hard while this table exists.

Practically: read the capacity bound before choosing the table. C up to about 10^5 with n in the low thousands is comfortable. A capacity of 10^9 says the intended solution is something else — meet in the middle at n ≤ 40, a greedy argument, or a state indexed by value rather than weight.

In an interview

Name the variant first: "each item once, so this is 0/1, so the capacity loop runs downward." Interviewers ask for the reason, and "downward keeps dp[c - w] on the previous item's row" is the answer that shows the rolled array is understood rather than memorised.

Do the size arithmetic out loud first: "n = 100, C = 10,000, a million cells at constant work — milliseconds, and 80 KB for one row of 64-bit integers." That sentence justifies the approach and proves the table fits.

The mistake that loses points: presenting O(n x C) as polynomial when the constraints put C in the billions. Saying "this is pseudo-polynomial, so with C = 10^9 I need a different approach" turns a wrong answer into a demonstration of judgment.

Check yourself

You iterate the capacity upward in a problem where each item may be used once. What answer do you get, and why might the samples still pass?

Too large an answer, because dp[c - w] may already include item i, so the item is packed repeatedly. Small samples often have items that would not usefully repeat within the capacity, so the two directions agree and the bug hides until a case where one light, valuable item fits several times.

Coins are 1 and 2 and the amount is 4. How many combinations, and how many ordered sequences?

Combinations: 1+1+1+1, 1+1+2, 2+2 — three. Ordered: 1111, 112, 121, 211, 22 — five. Coins on the outer loop gives 3; capacity on the outer loop gives 5.

The constraints are n ≤ 100 items and capacity ≤ 10^9. Why is the standard table wrong here, and what does the bound suggest instead?

The table needs 100 x 10^9 = 10^11 updates and 8 GB for a single row: it is polynomial in the value of C, not in its size. A huge capacity with a small item count points at a table indexed by total value instead of total weight, which works when the values are small — or at meet in the middle, if n were 40 rather than 100.