Knapsack DP: 0/1, Unbounded, Bounded and Counting

The knapsack family covers every problem of the form "pick items, each with a cost (weight) and a gain (value), under a capacity limit". Whether each item can be used once, without limit, or up to k times decides which variant you are in, and the difference often boils down to the direction of a single loop.

Intuition

Process items one at a time and keep, for every capacity j from 0 to W, the best value achievable with the items seen so far. Adding item i with weight w and value v gives two choices for each j:

• skip it: the best stays f[i-1][j];
• take it: f[i-1][j-w] + v (if j >= w).

So f[i][j] = max(f[i-1][j], f[i-1][j-w] + v). Row i only reads row i - 1, so one array is enough, as long as the update order does not read values already overwritten in this round. That is where the famous loop direction rule comes from.

When to use it in interviews / OAs

• "Choose a subset whose total weight/cost is at most / exactly X" and optimize a value or count the choices.
• Partition an array into two parts with equal or closest sums (subset sum).
• Assign + or - to every number to hit a target (it reduces to subset sum).
• Make an amount from coins: fewest coins, or number of ways.
• Constraints like n up to a few hundred and capacity up to ~10^4 hint at an O(n * W) table.

0/1 knapsack: each item at most once

def knapsack_01(weights: list[int], values: list[int], cap: int) -> int:
    f = [0] * (cap + 1)  # f[j] = best value with total weight <= j
    for w, v in zip(weights, values):
        for j in range(cap, w - 1, -1):  # descending: f[j - w] is still the old row
            f[j] = max(f[j], f[j - w] + v)
    return f[cap]

Why descending? When j goes down, f[j - w] has not been touched in this round, so it still describes "without item i", which is exactly what the 2D recurrence asks for. Going upward would let f[j - w] already include item i, so the item could be taken again.

Unbounded knapsack: unlimited copies

Now f[i][j] = max(f[i-1][j], f[i][j-w] + v): taking item i leads to a state that may still take item i. In one array that is just the ascending loop:

def knapsack_unbounded(weights: list[int], values: list[int], cap: int) -> int:
    f = [0] * (cap + 1)
    for w, v in zip(weights, values):
        for j in range(w, cap + 1):  # ascending: f[j - w] may already use this item
            f[j] = max(f[j], f[j - w] + v)
    return f[cap]

Bounded knapsack: at most k copies

Treating k copies as k separate items costs O(W * sum(k)). Binary splitting is better: bundle the copies into groups of 1, 2, 4, ... plus a remainder (13 = 1 + 2 + 4 + 6). Every count from 0 to k is a sum of distinct bundles, so a 0/1 knapsack over the bundles covers all choices with only O(log k) items per type.

def knapsack_bounded(weights: list[int], values: list[int], counts: list[int], cap: int) -> int:
    f = [0] * (cap + 1)
    for w, v, k in zip(weights, values, counts):
        size = 1
        while k > 0:
            take = min(size, k)  # bundle of `take` copies, used as one 0/1 item
            bw, bv = take * w, take * v
            for j in range(cap, bw - 1, -1):
                f[j] = max(f[j], f[j - bw] + bv)
            k -= take
            size *= 2
    return f[cap]

Exactly full vs at most full

The initial values decide the meaning of f[j]:

• f = [0] * (cap + 1) means "total weight at most j" (every capacity starts with the empty choice).
• f[0] = 0 and everything else -inf (or +inf when minimizing) means "total weight exactly j". Unreachable sums stay at infinity.

Fewest coins to make an amount is the "exactly" version with min instead of max:

def min_coins(coins: list[int], amount: int) -> int:
    INF = float("inf")
    f = [0] + [INF] * amount  # f[j] = fewest coins summing to exactly j
    for c in coins:
        for j in range(c, amount + 1):  # unlimited coins: ascending
            f[j] = min(f[j], f[j - c] + 1)
    return -1 if f[amount] == INF else f[amount]

Counting the ways

Replace max with + and start from f[0] = 1 (the empty selection). Loop order now matters in a second way:

def count_combinations(coins: list[int], amount: int) -> int:
    f = [1] + [0] * amount
    for c in coins:  # coins outside: each multiset counted once
        for j in range(c, amount + 1):
            f[j] += f[j - c]
    return f[amount]


def count_sequences(nums: list[int], target: int) -> int:
    f = [1] + [0] * target
    for j in range(1, target + 1):  # amount outside: every order counted
        for x in nums:
            if x <= j:
                f[j] += f[j - x]
    return f[target]

With items in the outer loop, coins are added in a fixed order, so 1+2 and 2+1 are the same combination. With the amount in the outer loop, any coin can be the last one, so different orders are different sequences.

Subset sum: partition and target sum

Partitioning into two equal halves asks whether some subset sums to total / 2. In Python an arbitrary-size integer works as a bitset: bit s is set when sum s is reachable, and taking x shifts all reachable sums by x.

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    if total % 2:
        return False
    reachable = 1  # bit s set <=> some subset sums to s
    for x in nums:
        reachable |= reachable << x
    return bool(reachable >> (total // 2) & 1)


def count_subsets_with_sum(nums: list[int], target: int) -> int:
    f = [1] + [0] * target  # f[s] = number of subsets with sum s
    for x in nums:
        for s in range(target, x - 1, -1):  # 0/1: descending
            f[s] += f[s - x]
    return f[target]


def target_sum_ways(nums: list[int], target: int) -> int:
    # plus - minus = target and plus + minus = total  =>  plus = (total + target) / 2
    total = sum(nums)
    if abs(target) > total or (total + target) % 2:
        return 0
    return count_subsets_with_sum(nums, (total + target) // 2)

Complexity

Variant	Time	Space
0/1, unbounded, coin change, counting	O(n * W)	O(W)
Bounded with binary splitting	O(W * sum(log k))	O(W)
Bitset subset sum	O(n * total / 64) word operations	O(total) bits

W is the capacity or target, so this is pseudo-polynomial: it depends on the numeric value, not the input length. When the capacity is huge but values are small, index the table by value instead (see DP state design).

Common pitfalls

• Loop direction: descending for 0/1, ascending for unlimited. Mixing them silently changes the problem.
• Initial values: 0 everywhere means "at most W", -inf except f[0] means "exactly W". Fewest coins with 0 initialization returns nonsense.
• Combinations vs sequences: items outer counts multisets; amount outer counts ordered sequences.
• Zero-weight items: in counting problems each zero doubles the count (both +0 and -0); make sure your loop includes s = 0 as the code above does.
• Negative targets: target sum with a negative target is symmetric; check parity and abs(target) <= total before indexing.
• Overflow and modulo: counts grow exponentially; in C++/Java use 64-bit integers or take the modulo the problem asks for.

Interview variations

• Equal subset partition and last stone weight II (minimize the difference of two subset sums: find the reachable sum closest to total / 2).
• Target sum with signs: reduce to counting subsets with sum (total + target) / 2.
• Coin change: fewest coins (min, ascending) and number of combinations (count, coins outer).
• Combination sum IV: ordered sequences, amount outer.
• Perfect squares: unbounded knapsack where the items are 1, 4, 9, ...
• Multiple constraints (for example counts of zeros and ones per string): add one dimension per constraint, see knapsack variants.