Knapsack Problem

The bag that won't stretch

You're a burglar with a knapsack that holds 15 kilograms. The room is full of loot — a 12 kg gold bar worth $4, a 2 kg diamond worth $3, a 1 kg watch worth $2 — and you have one trip. Which subset maximizes your haul without snapping the straps? That choice, repeated for every possible item set and bag size, is the knapsack problem: among all items with a weight and a value, pick a subset whose total weight stays within a capacity W while total value is as large as possible.

The word "subset" is doing all the work. With n items there are 2ⁿ subsets, so brute force is hopeless past 40-ish items. The breakthrough — and the reason this problem appears in every algorithms course — is that you don't need to look at all subsets. Most of them share sub-decisions. Dynamic programming exploits that overlap: solve "best value using the first i items in a bag of size w" once, store it, and reuse it.

This is the 0/1 knapsack — each item is taken zero times or one time, never split. That single integrality constraint is what makes it hard; relax it and the problem collapses (see variants).

How the DP table fills

Define dp[i][w] = the maximum value achievable using only the first i items with a bag that holds at most w. The recurrence asks one question per item: take it, or leave it?

dp[i][w] = max(
    dp[i-1][w],                                  // leave item i out
    dp[i-1][w - weight[i]] + value[i]            // take item i (only if w ≥ weight[i])
)

The first line says "ignore item i — the answer is whatever i-1 items already gave you." The second says "take i, pay its weight, and add its value to the best you could do with the remaining capacity." You keep the larger. Base case: dp[0][w] = 0 — zero items, zero value, for every capacity.

Fill the table row by row, capacity by capacity, and the final answer sits in dp[n][W]. There are (n+1)(W+1) cells and each costs O(1), so the whole thing runs in O(nW) time and O(nW) space — or O(W) space if you only keep one row (see below).

The optimality argument is the principle of optimal substructure: the best packing of items 1..i either uses item i or doesn't, and in each case the rest of the bag is itself an optimal sub-packing. No subset is ever recomputed because every (i, w) state is solved exactly once.

Why O(nW) is a trap

O(nW) reads like a polynomial, and beginners conclude knapsack is "easy." It isn't. The catch is W: it's a single number, and the size of the input is the number of bits needed to write it, which is log₂ W. A capacity of one billion is only 30 bits of input but forces a billion columns. So O(nW) is pseudo-polynomial — polynomial in the value of W, exponential in its bit-length.

The decision form ("is value ≥ k achievable?") is one of Karp's original 21 NP-complete problems, proved in 1972. The optimization form is NP-hard. The DP doesn't contradict that — it just means knapsack is among the friendliest NP-hard problems, because when weights are small integers, W is small and the DP is genuinely fast.

When W explodes but values stay small, flip the table: index by total value instead of weight, storing the minimum weight that reaches each value, for an O(n·V) solution where V = Σ value. That dual is the engine behind the FPTAS, which scales values down and rounds to hit any (1−ε) guarantee in O(n³/ε) time.

When knapsack DP is the right tool

• Integer weights and a modest capacity. If W is in the thousands or low millions, O(nW) is trivially fast and exact.
• You need the exact optimum, not a near-optimum. Budget allocation, cutting stock, cargo loading where being 1% off costs real money.
• The "pick a subset under a budget" shape. Subset-sum, partition into equal halves, coin change, and "can these tasks fit the sprint?" are all knapsack in disguise.

Reach for something else when capacity is astronomically large with no value bound (use the FPTAS or a branch-and-bound solver), when items are divisible (use fractional greedy), or when you have many constraints at once (use an ILP solver like CBC or Gurobi).

0/1 vs the other knapsacks

	0/1 knapsack	Unbounded	Bounded (count cᵢ)	Fractional	Multi-dimensional	Subset-sum
Item reuse	0 or 1	unlimited	0..cᵢ	any fraction	0 or 1	0 or 1
Best algorithm	DP	DP	DP (binary split)	greedy	DP / ILP	DP
Time	O(nW)	O(nW)	O(nW log c)	O(n log n)	O(nW₁W₂…)	O(nW)
Space (compressed)	O(W)	O(W)	O(W)	O(1)	O(W₁W₂…)	O(W) bitset
1-D loop direction	W → wᵢ (down)	wᵢ → W (up)	down, per copy	—	down	down
Greedy optimal?	No	No	No	Yes (provably)	No	No
Complexity	NP-hard	NP-hard	NP-hard	P	NP-hard	NP-complete

The headline split is integrality. The moment you allow fractions, a one-line greedy by value-per-weight is optimal and the problem drops into P. Forbid fractions and you're stuck with DP or exponential search. Notice the loop direction row: a single byte of difference — iterating capacity up versus down — is the entire distinction between unbounded and 0/1 in the compressed implementation.

What the numbers actually say

• Brute force dies at ~40 items. 2⁴⁰ ≈ 1.1 trillion subsets; at 10⁹ subset-checks/second that's ~18 minutes for one instance. 2⁵⁰ would take ~13 days. The DP handles 1,000 items and W = 100,000 — 10⁸ cells, roughly 0.1–0.5 s in C — without breaking a sweat.
• Meet-in-the-middle beats both for small n, large W. Split items in half, enumerate 2^(n/2) subsets of each, sort and binary-search: O(2^(n/2)·n) ≈ 2²⁰ for n = 40, about a million operations — done in milliseconds where naive 2⁴⁰ would not.
• Space is the real ceiling. A 2-D int table with n = 1,000 and W = 1,000,000 is 4 GB. The 1-D rolling array drops that to 4 MB — a 1,000× cut — which is why production code almost always compresses to one row.
• FPTAS trades exactness for speed. Want within 1% of optimal (ε = 0.01)? O(n³/ε) = 10⁸ for n = 100, independent of how huge the weights are.

JavaScript implementation

The 1-D rolling array — the version you actually ship. The downward inner loop is what enforces "each item at most once":

function knapsack01(weights, values, W) {
  const n = weights.length;
  const dp = new Array(W + 1).fill(0);

  for (let i = 0; i < n; i++) {
    // iterate capacity HIGH → LOW so item i is used at most once
    for (let w = W; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[W];                 // max value that fits in capacity W
}

// Example: capacity 10, three items
knapsack01([6, 5, 5], [10, 9, 9], 10);   // → 18  (take the two 5-kg items, not the 6-kg one)

To recover which items were chosen — not just the total value — you need the full 2-D table and a backtrack pass:

function knapsackItems(weights, values, W) {
  const n = weights.length;
  const dp = Array.from({ length: n + 1 }, () => new Array(W + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= W; w++) {
      dp[i][w] = dp[i - 1][w];                                  // leave item out
      if (weights[i - 1] <= w) {
        const take = dp[i - 1][w - weights[i - 1]] + values[i - 1];
        if (take > dp[i][w]) dp[i][w] = take;                  // take item in
      }
    }
  }

  // backtrack from (n, W): a changed cell means the item was taken
  const chosen = [];
  let w = W;
  for (let i = n; i > 0; i--) {
    if (dp[i][w] !== dp[i - 1][w]) {
      chosen.push(i - 1);
      w -= weights[i - 1];
    }
  }
  return { value: dp[n][W], items: chosen.reverse() };
}

Python implementation

Both the compact 1-D DP and the unbounded variant, side by side, to show that the only difference is the loop direction:

def knapsack_01(weights, values, W):
    """Each item used at most once — iterate capacity DOWNWARD."""
    dp = [0] * (W + 1)
    for wt, val in zip(weights, values):
        for w in range(W, wt - 1, -1):          # W, W-1, ..., wt
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]


def knapsack_unbounded(weights, values, W):
    """Unlimited copies allowed — iterate capacity UPWARD."""
    dp = [0] * (W + 1)
    for wt, val in zip(weights, values):
        for w in range(wt, W + 1):              # wt, wt+1, ..., W
            dp[w] = max(dp[w], dp[w - wt] + val)
    return dp[W]


# Subset-sum as a knapsack: can any subset hit exactly target?
def subset_sum(nums, target):
    reachable = 1                                # bitset, bit k = "sum k reachable"
    for x in nums:
        reachable |= reachable << x               # add x to every reachable sum
    return (reachable >> target) & 1 == 1


print(knapsack_01([6, 5, 5], [10, 9, 9], 10))   # 18
print(knapsack_unbounded([2, 3], [3, 4], 10))   # 15  (five 2-kg items)
print(subset_sum([3, 34, 4, 12, 5, 2], 9))      # True  (4 + 5)

The subset_sum trick is worth internalizing: Python's big integers let you run the entire DP as one shift-and-OR over a bitset, which is roughly 64× faster than a boolean array because it processes 64 capacities per machine word.

Variants worth knowing

Unbounded knapsack. Unlimited copies of each item. The only change from 0/1 is iterating capacity upward, so dp[w - wt] may already include the current item. This is exactly coin change (minimum coins / number of ways).

Bounded knapsack. Each item has a cap cᵢ on copies. The naive fix loops cᵢ times per item; the elegant fix is binary splitting — represent cᵢ as powers of two (1, 2, 4, …) and treat each chunk as a 0/1 item, dropping the cost to O(nW log c).

Fractional knapsack. You may take a fraction of any item. Sort by value-per-weight, greedily fill with the best ratios, take a fraction of the last item that fits. Provably optimal in O(n log n) — the one knapsack that lives in P.

Multi-dimensional knapsack. Two or more capacity constraints (weight and volume). The table gains a dimension per constraint: O(nW₁W₂…). Common in resource scheduling.

Meet-in-the-middle. For large W but small n (≤ 40), split items in half, enumerate all subsets of each half, then merge with sorting + binary search in O(2^(n/2)·n) — exponential, but the square root of brute force.

Common bugs and edge cases

• Looping capacity the wrong way in the 1-D DP. Going up in a 0/1 problem silently solves unbounded — each item gets reused. The bug produces a larger, wrong answer that looks plausible. Always go high → low for 0/1.
• Off-by-one between item index and array index. In the 2-D table dp[i] means "first i items," so item i lives at weights[i-1]. Mixing the two conventions is the most common crash.
• Forgetting the w ≥ weight[i] guard. Without it, dp[w - weight[i]] indexes negative and either throws or wraps.
• Assuming greedy works. Sorting by value, by weight, or by ratio all fail on 0/1. Greedy is only correct for the fractional variant.
• Integer overflow on summed values. With thousands of items, total value can exceed 32-bit range; use 64-bit accumulators.
• Treating O(nW) as polynomial. A capacity of 10⁹ blows up memory and time even with a handful of items. If W is huge, switch to the value-indexed DP or meet-in-the-middle.