Knapsack and subset selection

intermediateCommon atGoogleAmazonMetatrading firmsRead firstDynamic programming: 1DDynamic programming: 2DPractise in the Sandbox →

Knapsack DP answers “which items fit within a budget for the best total?” with a table dp[i][c] = best value using the first i items with capacity c. Each cell chooses skip (dp[i−1][c]) or take (dp[i−1][c−w] + v for 0/1, dp[i][c−w] + v for unbounded). O(n · W) time, O(W) space with one row, where the loop runs downward for 0/1 and upward for unbounded. Subset sum and “count the ways” are the same table with or or + in place of max.

The idea in plain words

You have a bag that holds 7 kg and four items: (1 kg, $1), (3 kg, $4), (4 kg, $5), (5 kg, $7). Which ones?

Greedy by value per kg grabs the 5 kg item ($1.40/kg) and then only the 1 kg item fits: $8. Taking the 3 kg and 4 kg items gives $9. Greedy fails because items are whole: you can’t take 2 kg of the 5 kg item. (If you could, the problem is “fractional knapsack” and greedy is optimal. See greedy.)

So consider items one at a time and ask the only question that matters about each: skip it, or take it?

• Skip item i: the best you can do is whatever the first i − 1 items achieved with the same capacity.
• Take item i: you get v now, and the remaining capacity c − w must be filled by the first i − 1 items (0/1), or by the first i items again if copies are unlimited (unbounded).

That’s the whole recurrence. The capacity dimension is what makes it work: the past is summarised by “how much room is left”, not by which items were taken.

See it

Step through the 0/1 table, then switch to Unbounded and watch the “take” arrow come from the same row instead of the row above. Subset sum is the same table with true/false values.

Knapsack tables: 0/1, unbounded, subset sum

step through

0/1UnboundedSubset sum

items weight:valuecapacity (≤ 12)

capacity7

cell being filledoption chosenoption rejectedwalk back

dp[i][c] = best value using only the first i items with capacity c. Row 0 (no items) is all 0.

↺◀▶ Play▶1 / 34

With one row instead of a table, the same difference becomes the loop direction. Run it forward, then backward:

Why the 1-D loop direction matters

step through

item weightitem value

0

0

0

0

0

0

0

0

0

0

0

012345678910

dp[c]: best value at capacity c

0

0

0

0

0

0

0

0

0

0

0

copies of the item inside dp[c]

w2

v3

directionc = w → C

cell writtenread: old valueread: already includes the itemholds 2+ copies

One array, overwritten in place. Each cell reads dp[c − 2]. The question: has that cell already been updated for this same item?

↺◀▶ Play▶1 / 11

When to reach for it

The problem says…	Variant
“each item at most once”, “choose a subset with total weight ≤ W maximising value”	0/1 knapsack.
“unlimited supply”, “any number of each coin”, “rod cutting”	Unbounded knapsack.
“can some subset sum to exactly T?”, “split into two equal-sum halves”	Subset sum (boolean).
“how many ways to make T?”	Counting: + instead of max. Combinations vs permutations depends on loop order.
“fewest items to reach exactly T”	min with +1, infinity for unreachable.
budget is huge (10⁹) but n is small (≤ 40)	Not this table: meet in the middle, or backtracking with pruning.
budget is huge but values are small	Swap roles: dp[v] = minimum weight to reach value v.

How it works

1. State: best[c] = best value with total weight ≤ c, using the items processed so far (one row of the 2-D table).
2. Transition: best[c] = max(best[c], best[c − w] + v): skip or take.
3. Base: all zeros (no items, any capacity, value 0). For “exactly c” variants, best[0] = 0 and the rest −∞ (or false).
4. Order: items outer. Capacities high to low for 0/1 so best[c − w] still means “without this item”; low to high for unbounded so it may already include it.
5. Answer: best[W]. Keep the 2-D table (or a took[i][c] flag) if you need to recover which items.

Python

knapsack_01.py

def knapsack_01(items: list[tuple[int, int]], capacity: int) -> int:
    """Best total value of items (weight, value), each used at most once, within capacity."""
    # 1. state: best[c] = best value with total weight <= c, using the items seen so far
    best = [0] * (capacity + 1)                  # 3. base: no items, value 0 everywhere
    for w, v in items:                           # 4. order: one item at a time ...
        for c in range(capacity, w - 1, -1):     #    ... capacities high to low (!)
            # 2. skip the item (keep best[c]) or take it on top of best[c - w].
            #    Going downward, best[c - w] still means "without this item".
            best[c] = max(best[c], best[c - w] + v)
    return best[capacity]                        # 5. answer


if __name__ == "__main__":
    assert knapsack_01([(1, 1), (3, 4), (4, 5), (5, 7)], 7) == 9   # weights 3 + 4
    assert knapsack_01([(2, 3)], 10) == 3        # one copy only, however much room
    assert knapsack_01([], 5) == 0
    assert knapsack_01([(6, 10)], 5) == 0        # doesn't fit
    print("ok")

TypeScript

knapsack_01.ts

import assert from "node:assert/strict";

/** Best total value of items [weight, value], each used at most once, within capacity. */
export function knapsack01(items: [number, number][], capacity: number): number {
  // 1. state: best[c] = best value with total weight <= c, using the items seen so far
  const best = new Array<number>(capacity + 1).fill(0); // 3. base: no items, value 0
  for (const [w, v] of items) { // 4. order: one item at a time ...
    for (let c = capacity; c >= w; c--) { //    ... capacities high to low (!)
      // 2. skip (keep best[c]) or take on top of best[c - w], which going downward
      //    still means "without this item"
      best[c] = Math.max(best[c], best[c - w] + v);
    }
  }
  return best[capacity]; // 5. answer
}

assert.equal(knapsack01([[1, 1], [3, 4], [4, 5], [5, 7]], 7), 9); // weights 3 + 4
assert.equal(knapsack01([[2, 3]], 10), 3); // one copy only, however much room
assert.equal(knapsack01([], 5), 0);
assert.equal(knapsack01([[6, 10]], 5), 0); // doesn't fit
console.log("ok");

C#

knapsack_01.cs

// Best total value of items (weight, value), each used at most once, within capacity.
static int Knapsack01((int W, int V)[] items, int capacity)
{
    // 1. state: best[c] = best value with total weight <= c, using the items seen so far
    var best = new int[capacity + 1];               // 3. base: no items, value 0
    foreach (var (w, v) in items)                   // 4. order: one item at a time ...
        for (int c = capacity; c >= w; c--)         //    ... capacities high to low (!)
            // 2. skip (keep best[c]) or take on top of best[c - w], which going
            //    downward still means "without this item"
            best[c] = Math.Max(best[c], best[c - w] + v);
    return best[capacity];                          // 5. answer
}

if (Knapsack01([(1, 1), (3, 4), (4, 5), (5, 7)], 7) != 9) throw new Exception("expected 9");
if (Knapsack01([(2, 3)], 10) != 3) throw new Exception("one copy only");
if (Knapsack01([], 5) != 0) throw new Exception("expected 0");
if (Knapsack01([(6, 10)], 5) != 0) throw new Exception("doesn't fit");
Console.WriteLine("ok");

The unbounded version changes only the loop direction. Counting the ways to make change uses the same forward loop with +.

Python

knapsack_unbounded.py

def knapsack_unbounded(items: list[tuple[int, int]], capacity: int) -> int:
    """Best total value when each item (weight, value) may be used any number of times."""
    best = [0] * (capacity + 1)                  # 1. best[c] = best value within weight c
    for w, v in items:
        for c in range(w, capacity + 1):         # 4. capacities LOW to high: the only change
            # 2. best[c - w] may already include this item, which is now allowed
            best[c] = max(best[c], best[c - w] + v)
    return best[capacity]


def count_change(coins: list[int], amount: int) -> int:
    """Number of coin multisets summing to amount (order doesn't matter)."""
    ways = [1] + [0] * amount                    # 3. one way to make 0: no coins
    for c in coins:                              # coins outer: each multiset counted once
        for a in range(c, amount + 1):
            ways[a] += ways[a - c]
    return ways[amount]


if __name__ == "__main__":
    assert knapsack_unbounded([(2, 3)], 10) == 15            # five copies
    assert knapsack_unbounded([(1, 1), (3, 4), (4, 5), (5, 7)], 7) == 9
    assert knapsack_unbounded([(5, 10), (4, 7), (6, 13)], 12) == 26  # two of (6, 13)
    assert count_change([1, 2, 5], 5) == 4                   # 5, 2+2+1, 2+1+1+1, 1*5
    assert count_change([2], 3) == 0
    print("ok")

TypeScript

knapsack_unbounded.ts

import assert from "node:assert/strict";

/** Best total value when each item [weight, value] may be used any number of times. */
export function knapsackUnbounded(items: [number, number][], capacity: number): number {
  const best = new Array<number>(capacity + 1).fill(0); // 1. best[c] = best value within weight c
  for (const [w, v] of items) {
    for (let c = w; c <= capacity; c++) { // 4. capacities LOW to high: the only change
      best[c] = Math.max(best[c], best[c - w] + v); // 2. best[c - w] may already include this item
    }
  }
  return best[capacity];
}

/** Number of coin multisets summing to amount (order doesn't matter). */
export function countChange(coins: number[], amount: number): number {
  const ways = new Array<number>(amount + 1).fill(0);
  ways[0] = 1; // 3. one way to make 0: no coins
  for (const c of coins) { // coins outer: each multiset counted once
    for (let a = c; a <= amount; a++) ways[a] += ways[a - c];
  }
  return ways[amount];
}

assert.equal(knapsackUnbounded([[2, 3]], 10), 15); // five copies
assert.equal(knapsackUnbounded([[1, 1], [3, 4], [4, 5], [5, 7]], 7), 9);
assert.equal(knapsackUnbounded([[5, 10], [4, 7], [6, 13]], 12), 26); // two of [6, 13]
assert.equal(countChange([1, 2, 5], 5), 4); // 5, 2+2+1, 2+1+1+1, 1*5
assert.equal(countChange([2], 3), 0);
console.log("ok");

C#

knapsack_unbounded.cs

// Best total value when each item (weight, value) may be used any number of times.
static int KnapsackUnbounded((int W, int V)[] items, int capacity)
{
    var best = new int[capacity + 1];               // 1. best[c] = best value within weight c
    foreach (var (w, v) in items)
        for (int c = w; c <= capacity; c++)         // 4. capacities LOW to high: the only change
            best[c] = Math.Max(best[c], best[c - w] + v); // 2. best[c - w] may already include it
    return best[capacity];
}

// Number of coin multisets summing to amount (order doesn't matter).
static long CountChange(int[] coins, int amount)
{
    var ways = new long[amount + 1];
    ways[0] = 1;                                    // 3. one way to make 0: no coins
    foreach (int c in coins)                        // coins outer: each multiset counted once
        for (int a = c; a <= amount; a++) ways[a] += ways[a - c];
    return ways[amount];
}

if (KnapsackUnbounded([(2, 3)], 10) != 15) throw new Exception("five copies");
if (KnapsackUnbounded([(1, 1), (3, 4), (4, 5), (5, 7)], 7) != 9) throw new Exception("expected 9");
if (KnapsackUnbounded([(5, 10), (4, 7), (6, 13)], 12) != 26) throw new Exception("expected 26");
if (CountChange([1, 2, 5], 5) != 4) throw new Exception("expected 4");
if (CountChange([2], 3) != 0) throw new Exception("expected 0");
Console.WriteLine("ok");

Subset sum is 0/1 knapsack where weight = value and the question is yes/no:

Python

can_reach.py

def can_reach(nums: list[int], target: int) -> bool:
    """Is there a subset of nums (non-negative) that sums to exactly target?"""
    reach = [True] + [False] * target            # 1. reach[s]: some subset sums to s. 3. base: {} -> 0
    for x in nums:
        for s in range(target, x - 1, -1):       # 4. downward: each number used at most once
            reach[s] = reach[s] or reach[s - x]  # 2. skip x, or add x to a subset reaching s - x
    return reach[target]


def can_split_evenly(nums: list[int]) -> bool:
    """Classic reduction: two equal-sum halves exist iff some subset hits total / 2."""
    total = sum(nums)
    return total % 2 == 0 and can_reach(nums, total // 2)


if __name__ == "__main__":
    assert can_reach([3, 34, 4, 12, 5, 2], 9)        # 4 + 5
    assert not can_reach([3, 34, 4, 12, 5, 2], 30)
    assert can_reach([], 0)
    assert can_split_evenly([1, 5, 11, 5])           # {11} vs {1, 5, 5}
    assert not can_split_evenly([1, 2, 3, 5])
    print("ok")

TypeScript

can_reach.ts

import assert from "node:assert/strict";

/** Is there a subset of nums (non-negative) that sums to exactly target? */
export function canReach(nums: number[], target: number): boolean {
  // 1. reach[s]: some subset sums to s. 3. base: the empty subset reaches 0
  const reach = new Array<boolean>(target + 1).fill(false);
  reach[0] = true;
  for (const x of nums) {
    for (let s = target; s >= x; s--) { // 4. downward: each number used at most once
      reach[s] = reach[s] || reach[s - x]; // 2. skip x, or add x to a subset reaching s - x
    }
  }
  return reach[target];
}

/** Classic reduction: two equal-sum halves exist iff some subset hits total / 2. */
export function canSplitEvenly(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b, 0);
  return total % 2 === 0 && canReach(nums, total / 2);
}

assert.ok(canReach([3, 34, 4, 12, 5, 2], 9)); // 4 + 5
assert.ok(!canReach([3, 34, 4, 12, 5, 2], 30));
assert.ok(canReach([], 0));
assert.ok(canSplitEvenly([1, 5, 11, 5])); // {11} vs {1, 5, 5}
assert.ok(!canSplitEvenly([1, 2, 3, 5]));
console.log("ok");

C#

can_reach.cs

// Is there a subset of nums (non-negative) that sums to exactly target?
static bool CanReach(int[] nums, int target)
{
    var reach = new bool[target + 1];               // 1. reach[s]: some subset sums to s
    reach[0] = true;                                // 3. base: the empty subset reaches 0
    foreach (int x in nums)
        for (int s = target; s >= x; s--)           // 4. downward: each number used at most once
            reach[s] = reach[s] || reach[s - x];    // 2. skip x, or add x to a subset reaching s - x
    return reach[target];
}

// Classic reduction: two equal-sum halves exist iff some subset hits total / 2.
static bool CanSplitEvenly(int[] nums)
{
    int total = nums.Sum();
    return total % 2 == 0 && CanReach(nums, total / 2);
}

if (!CanReach([3, 34, 4, 12, 5, 2], 9)) throw new Exception("4 + 5 = 9");
if (CanReach([3, 34, 4, 12, 5, 2], 30)) throw new Exception("30 is unreachable");
if (!CanReach([], 0)) throw new Exception("empty subset reaches 0");
if (!CanSplitEvenly([1, 5, 11, 5])) throw new Exception("{11} vs {1, 5, 5}");
if (CanSplitEvenly([1, 2, 3, 5])) throw new Exception("odd total");
Console.WriteLine("ok");

Combinations vs permutations when counting

With items in the outer loop and amounts inside, each multiset is counted once: 1+2 and 2+1 are the same way. With amounts outer and items inside, every order is counted separately (that’s “climbing stairs with these step sizes”). Interviewers love asking which loop order gives which.

What it costs

	Time	Space
Try every subset	O(2ⁿ · n)	O(n)
2-D table	O(n · W)	O(n · W)
1-D row	O(n · W)	O(W)
Meet in the middle (n ≤ ~40, any W)	O(2^(n/2) · n)	O(2^(n/2))
Bitset subset sum	O(n · W / 64)	O(W / 64)

Pseudo-polynomial. O(n · W) looks polynomial, but W is a number, not a count of inputs. Writing W takes only log W bits, so the running time is exponential in the input size. That’s why 0/1 knapsack is NP-hard and still solvable in practice when W is up to ~10⁶-10⁷. Always check the size of W before proposing this table.

Variations you’ll meet

• Bounded (item i has k_i copies): split into powers of two (1, 2, 4, …) and run 0/1, or use a monotonic deque per residue.
• Minimum items / exact fill: initialise unreachable states to infinity (or false), not 0.
• Two budgets (weight and volume): dp[c1][c2], loop both downward for 0/1.
• Partition into two groups with the smallest difference: subset sum up to total / 2, take the largest reachable.
• Target sum with + and − signs: becomes subset sum on (total + target) / 2.
• Group knapsack (pick at most one item per group): loop capacity outside the items of each group.
• Bitset trick: in Python reach |= reach << x on a big integer, in C++ std::bitset, for 64× fewer operations on subset sum.

Pitfalls

• Wrong loop direction in the 1-D version: forward makes 0/1 into unbounded (see the second visualization). This is the knapsack bug.
• “At most W” vs “exactly W”: zeros everywhere means “at most”; −∞ except best[0] = 0 means “exactly”.
• Huge W. 10⁹ capacity means 10⁹ cells. Ask about bounds before choosing this approach.
• Greedy by ratio for 0/1 items. It’s a heuristic, not an answer. It is optimal only for fractional knapsack.
• Reconstruction from the 1-D row. You can’t; the row has been overwritten. Keep the 2-D table or a per-item “took” bitmap.
• Overflow in counting variants: use long / BigInt / a modulus.
• Zero-weight items with unbounded copies make “max value” infinite. Handle them separately.

In the interview

• Ask: can items be reused? Must the bag be exactly full? How big is W, and how big is n? Are weights integers?
• Explain why greedy fails with a 3-item counterexample, then give the recurrence: “For each item, skip or take; the state is (items considered, capacity left).”
• Draw a tiny table (3 items, capacity 5) and fill a row.
• Compress to 1-D and explain the loop direction in one sentence: “Downward, so when I read best[c − w] it hasn’t been updated for this item yet.”
• Expect: “return the chosen items”, “what if W = 10⁹?” (value-indexed DP, meet in the middle, or approximation), “count the ways”, “items have dependencies”.

Check yourself

Check yourself

pick one

In a 1-D 0/1 knapsack you loop capacity from w up to W. What do you actually compute?

ACorrect 0/1 knapsackBUnbounded knapsack: an item can be added again on top of a cell that already includes itCA smaller answer than the true 0/1 optimum

Check yourself

pick one

Coins {1, 2}, amount 3. Items-outer loop counts combinations; amounts-outer counts orderings. What do they give?

A2 and 3B3 and 3C2 and 2

Check yourself

pick one

n = 30 items, W = 10⁹, weights up to 10⁹. Which approach fits?

AThe O(n·W) tableBMeet in the middle: enumerate 2¹⁵ subsets of each half and combine with sorting + binary searchCGreedy by value per weight

Practice on your own

Classic exercises (not gym questions):

• Can an array be partitioned into two subsets of equal sum?
• Minimum difference between the sums of two groups that partition an array.
• Assign + or − to each number so the total equals a target: how many ways?
• Rod cutting: given prices for each length, maximise revenue for a rod of length n.
• Given strings of 0s and 1s, the largest subset with at most m zeros and n ones in total (two-budget 0/1).

Go deeper

• Introduction to Algorithms (CLRS), §15.1 “Rod cutting” (unbounded) and exercise 16.2-2 on 0/1 knapsack, alongside the fractional version in §16.2 (numbering differs in the 4th edition).
• Kleinberg and Tardos, Algorithm Design, §6.4 “Subset sums and knapsacks: adding a variable”, and the pseudo-polynomial discussion.
• cp-algorithms: knapsack problem, covering 0/1, complete (unbounded) and multiple (bounded) knapsack.

Related

Dynamic programming: 2DThe table shape knapsack lives in.

Advanced DP shapesBitmask DP when n is tiny and W is huge.

Greedy algorithmsWhy value-per-weight works only for fractional items.

BacktrackingEnumerating subsets with pruning.