The Knapsack Pattern

The problem

You are packing for a flight with a strict 15 kg baggage limit. Each item has a weight and a value to you — the camera is heavy but precious, the extra shoes are light but you barely care. You cannot take everything. Which subset maximizes the value you carry without going over 15 kg?

Greedily grabbing the most valuable item, or the lightest, or the best value-per-kilogram, all fail on carefully chosen inputs. The choices interact: taking the camera changes what fits afterward. You need to weigh every combination — but there are 2ⁿ of them, and that number runs away fast.

A first attempt

Consider items one at a time. For each, either leave it or take it (if it fits), and recurse on the rest with the remaining capacity.

def knap(w, v, i, cap):
    if i == len(w) or cap == 0:
        return 0
    best = knap(w, v, i + 1, cap)                 # skip item i
    if w[i] <= cap:                                # or take it
        best = max(best, v[i] + knap(w, v, i + 1, cap - w[i]))
    return best

Every item forks the recursion in two, so this is O(2ⁿ). With 40 items you are looking at a trillion calls. But notice: the recursion is fully described by (i, cap) — and many different branches reach the same (i, cap). Overlapping subproblems again.

The insight

There are only n × (capacity + 1) distinct states. Cache them:

Let dp[i][c] be the best value using items i..n-1 with capacity c left. Each state makes one binary choice — skip or take — so it costs O(1), and the whole table costs O(n × capacity).

This is pseudo-polynomial: fast when capacity is a modest number, because the table size depends on the capacity's value, not just the item count. The same two-choice template — for each item, skip or take — powers subset-sum, partition, coin combinations, and more.

How it works

We will fill the table bottom-up over items and capacities.

The code

The tabs show the compact 1D version; the leftmost also notes the 2D shape it comes from.

def knapsack(weights, values, cap):
    dp = [0] * (cap + 1)          # dp[c] = best value with capacity c
    for w, v in zip(weights, values):
        for c in range(cap, w - 1, -1):   # high -> low: use each item once
            dp[c] = max(dp[c], v + dp[c - w])
    return dp[cap]

function knapsack(weights: number[], values: number[], cap: number): number {
  const dp = new Array<number>(cap + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    const w = weights[i], v = values[i];
    for (let c = cap; c >= w; c--) {
      dp[c] = Math.max(dp[c], v + dp[c - w]);
    }
  }
  return dp[cap];
}

class Solution {
    int knapsack(int[] weights, int[] values, int cap) {
        int[] dp = new int[cap + 1];
        for (int i = 0; i < weights.length; i++) {
            int w = weights[i], v = values[i];
            for (int c = cap; c >= w; c--) {
                dp[c] = Math.max(dp[c], v + dp[c - w]);
            }
        }
        return dp[cap];
    }
}

int knapsack(int *weights, int *values, int n, int cap) {
    int dp[cap + 1];
    for (int c = 0; c <= cap; c++) dp[c] = 0;
    for (int i = 0; i < n; i++) {
        int w = weights[i], v = values[i];
        for (int c = cap; c >= w; c--) {
            int take = v + dp[c - w];
            if (take > dp[c]) dp[c] = take;
        }
    }
    return dp[cap];
}

int knapsack(vector<int> &weights, vector<int> &values, int cap) {
    vector<int> dp(cap + 1, 0);
    for (int i = 0; i < (int)weights.size(); i++) {
        int w = weights[i], v = values[i];
        for (int c = cap; c >= w; c--) {
            dp[c] = max(dp[c], v + dp[c - w]);
        }
    }
    return dp[cap];
}

Complexity

This is pseudo-polynomial: linear in the numeric capacity. If capacity were, say, 10⁹, the table would be far too large, and 0/1 knapsack is in fact NP-hard in general.

When to use it

Practice

Recap

• Knapsack is the template for "pick a subset under a limit": for each item, skip or take.
• The state is (item index, remaining capacity); the table is O(n × capacity), pseudo-polynomial.
• Sweep capacity downward for 0/1 (each item once), upward for unbounded (reuse allowed).