Knapsack

Overview

The 0/1 knapsack problem: given items with weights and values and a bag with capacity W, choose a subset with maximum total value whose weight fits. Each item is either taken once or not at all. The DP state dp[i][w] is the best value using the first i items with capacity w.

Knapsack is a family of patterns rather than one problem. Subset sum, partition equal subset sum, target sum, and 'ones and zeroes' are 0/1 knapsack. Coin change and rod cutting are unbounded knapsack, where each item can be reused. The difference shows up as the direction of the capacity loop in the 1D version.

When to use it

• Choose a subset under a budget (weight, cost, count) to maximize or minimize something.
• Can a subset reach an exact sum? How many subsets reach it?
• Split items into two groups with a target difference.
• Capacity values are small enough for an array (up to about 10^4 to 10^5).

Problem patterns it solves

Where it is used in real software

Key terms

Capacity W

The budget limit.

0/1

Each item is taken at most once.

Unbounded

Each item can be taken any number of times.

Pseudo-polynomial

O(n x W) depends on the numeric size of W, not just the input length.

How it works, step by step

1. 1
   State

   dp[i][w] = best value using items 0..i-1 with capacity w.

2. 2
   Skip item i

   dp[i][w] = dp[i - 1][w].

3. 3
   Take item i if it fits

   dp[i][w] = max(dp[i][w], dp[i - 1][w - weight] + value).

4. 4
   Compress to 1D

   For 0/1, loop w from W down to weight so each item is used once.

5. 5
   Unbounded version

   Loop w upward so dp[w - weight] may already include the same item.

0/1 knapsack, capacity 5

items (weight, value): A (1, 1), B (3, 4), C (4, 5). dp[w] after each item (1D, capacity loop downward)

Best value 6 with capacity 5: items A and C (weight 5). dp[5] after C = max(5, dp[1] + 5) = 6. Looping capacity downward guaranteed dp[1] still meant 'without C'.

Implementation

1function knapsack01(weights, values, W) {2  const dp = new Array(W + 1).fill(0);3  for (let i = 0; i < weights.length; i++) {4    for (let w = W; w >= weights[i]; w--) { // downward: each item once5      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);6    }7  }8  return dp[W];9}10 11// 416. Partition Equal Subset Sum: can a subset sum to total / 2?12function canPartition(nums) {13  const total = nums.reduce((a, b) => a + b, 0);14  if (total % 2) return false;15  const target = total / 2;16  const dp = new Array(target + 1).fill(false);17  dp[0] = true;18  for (const x of nums) {19    for (let s = target; s >= x; s--) dp[s] = dp[s] || dp[s - x];20  }21  return dp[target];22}23 24// 494. Target Sum: count subsets P with sum(P) = (total + target) / 225function findTargetSumWays(nums, target) {26  const total = nums.reduce((a, b) => a + b, 0);27  if (Math.abs(target) > total || (total + target) % 2) return 0;28  const goal = (total + target) / 2;29  const dp = new Array(goal + 1).fill(0);30  dp[0] = 1;31  for (const x of nums) {32    for (let s = goal; s >= x; s--) dp[s] += dp[s - x];33  }34  return dp[goal];35}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Looping capacity upward for 0/1 knapsack.

  Fix: Upward reuses the same item multiple times; that is the unbounded version.

• Target Sum with an odd (total + target).

  Fix: Return 0: no integer subset sum can satisfy it.

• Using greedy by ratio for 0/1.

  Fix: Counterexample: capacity 50, items (10, 60), (20, 100), (30, 120). Greedy by ratio takes the first two items (160); the optimum takes the last two (220).

Interview questions

Practice problems