Knapsack Variants

The setup

You have n items, each with a weight w[i] and value v[i], and a knapsack with capacity W. The question is "which items to take", and the answer depends on which flavour the question asks:

• 0/1 knapsack: each item is taken at most once. Maximise value subject to total weight ≤ W.
• Unbounded knapsack: each item can be taken any number of times. Same constraint.
• Bounded knapsack: each item has a max count c[i]. Generalisation of 0/1 (where every c[i] = 1) and unbounded (where every c[i] = ∞).
• Fractional knapsack: items can be taken in fractional amounts. (Think: liquid stored in barrels.)

The first three are NP-hard in general but admit pseudo-polynomial DPs. The fractional version is in P and admits a simple greedy.

0/1 knapsack, the canonical DP

State: f(i, w) = max value using the first i items with capacity w. Transition: for item i, either take it (if it fits) or skip it.

def knapsack_01(weights, values, W):
    n = len(weights)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(W + 1):
            dp[i][w] = dp[i-1][w]                                # skip
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i][w],
                               dp[i-1][w - weights[i-1]] + values[i-1])
    return dp[n][W]

Time: O(n × W). Space: O(n × W). The dependency is "previous row only", so we can drop to O(W) with a rolling 1D array, but the iteration order matters.

Space-optimised 0/1, iterate capacity DECREASING

def knapsack_01_1d(weights, values, W):
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        for w in range(W, weights[i] - 1, -1):                  # ←  decreasing
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

Why decreasing? When we update dp[w], we read dp[w − weights[i]]. If we iterate capacity in increasing order, that read sees the current item's already-updated value, equivalent to taking the item multiple times. Decreasing order ensures we read the previous row's value, preserving 0/1 semantics. This is the difference between 0/1 and unbounded; it's purely the iteration direction.

Unbounded, iterate capacity INCREASING

def knapsack_unbounded(weights, values, W):
    dp = [0] * (W + 1)
    for i in range(len(weights)):
        for w in range(weights[i], W + 1):                       # ←  increasing
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

The same code as 0/1, with one index direction reversed. Reading dp[w − weights[i]] in increasing order picks up the current item's already-updated entry, picking the item again. That's exactly the unbounded semantics.

Coin Change, minimum number of coins

"Given coin denominations and a target amount, return the fewest coins that sum to the target." Unbounded knapsack, where weight = coin value, value = 1 (count of coins), and the goal is to minimise.

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

Same shape, minimise instead of maximise. Time: O(coins × amount). Space: O(amount).

Coin Change 2, count of ways

"Given coin denominations and a target amount, count the number of distinct combinations that sum to the target." Same problem family, different aggregation: count instead of maximise.

def coin_change_count(coins, amount):
    dp = [0] * (amount + 1)
    dp[0] = 1                                                    # one way to make 0: pick nothing
    for c in coins:
        for w in range(c, amount + 1):
            dp[w] += dp[w - c]
    return dp[amount]

The outer loop must be coins, not amounts. Reversing them counts permutations rather than combinations, a subtle but important distinction. The "for each coin, for each amount" order ensures we count each multiset of coins exactly once.

Subset sum, does any subset sum to target?

"Given a set of integers, decide if any subset sums to target." This is the boolean version of 0/1 knapsack with weight = value = item.

def subset_sum(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True
    for x in nums:
        for w in range(target, x - 1, -1):
            dp[w] = dp[w] or dp[w - x]
    return dp[target]

The "Partition Equal Subset Sum" problem reduces to this by checking subset sum = total / 2. If total is odd, no equal partition exists; if even, run the DP for half.

Bounded knapsack, c[i] copies allowed

The naïve generalisation: copy each item c[i] times and run 0/1. Works but pads the input. The faster approach is binary-decomposition: replace c[i] copies with items of effective weights/values (w[i], v[i]), (2w[i], 2v[i]), (4w[i], 4v[i])… totalling at most c[i]. This reduces the count from O(c[i]) to O(log c[i]) per item.

def knapsack_bounded(weights, values, counts, W):
    expanded_w, expanded_v = [], []
    for w, v, c in zip(weights, values, counts):
        k = 1
        while k <= c:
            expanded_w.append(k * w)
            expanded_v.append(k * v)
            c -= k
            k *= 2
        if c > 0:
            expanded_w.append(c * w)
            expanded_v.append(c * v)
    return knapsack_01_1d(expanded_w, expanded_v, W)

Fractional knapsack, greedy

If items can be taken in fractional amounts, the DP is unnecessary. Sort by value-per-weight ratio descending; take items greedily until capacity runs out; take a fraction of the next item to fill the remainder.

def knapsack_fractional(weights, values, W):
    items = sorted(zip(weights, values), key=lambda wv: -wv[1] / wv[0])
    total = 0.0
    for w, v in items:
        if w <= W:
            total += v
            W -= w
        else:
            total += v * (W / w)
            break
    return total

Time: O(n log n) for the sort; O(n) for the walk. The exchange argument: if you ever skip an item with a higher ratio in favour of a lower one, swap them, the new arrangement weighs the same and is worth at least as much. Greedy is optimal.

Recognising the variant

Where beginners go wrong

• Wrong iteration direction. Decreasing for 0/1, increasing for unbounded. Mixing them silently swaps the variant.
• Loop order in counting variants. Coin Change 2 counts combinations only when the outer loop is coins. Inner-loop coins counts permutations, different problem.
• Forgetting dp[0] = 1 in counting variants. The "make zero" case is the empty multiset; without it the recurrence has no anchor.
• Trying greedy on 0/1. Greedy works on fractional knapsack but fails on 0/1, counter-example: weights [1, 2, 3], values [6, 10, 12], W = 5. Greedy by ratio takes {1, 2} for value 16; optimal is {2, 3} for value 22.
• Believing knapsack is "polynomial". O(n × W) is pseudo-polynomial. W is a number, not a length. For W = 10^9, the DP is exponential in input bits. Knapsack is genuinely NP-hard.

What to read next

The State Design Templates piece covers all six DP shapes; knapsack is shape 4. The Dynamic Programming module sits above this concept. The blog essay Complexity Is a Contract explains why "pseudo-polynomial" matters for real-world performance.