0/1 Knapsack

The 0/1 knapsack problem asks: given n items each with a weight and a value, and a knapsack of capacity W, choose items (each at most once) to maximize total value without exceeding W.

State and Recurrence

State: dp[i][w] = maximum value using the first i items with capacity w.

Recurrence:

• Skip item i: dp[i][w] = dp[i-1][w]
• Take item i (if weights[i-1] <= w): dp[i][w] = dp[i-1][w - weights[i-1]] + values[i-1]
• dp[i][w] = max(skip, take)

Base cases: dp[0][w] = 0 for all w (no items, no value).

function knapsack2D(weights, values, W) {
  const n = weights.length;
  // dp is (n+1) x (W+1), initialized to 0
  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]; // skip item i
      if (weights[i - 1] <= w) {
        dp[i][w] = Math.max(
          dp[i][w],
          dp[i - 1][w - weights[i - 1]] + values[i - 1]
        );
      }
    }
  }
  return dp[n][W];
}

const weights = [1, 3, 4, 5];
const values  = [1, 4, 5, 7];
console.log(knapsack2D(weights, values, 7)); // 9

Time O(n * W), space O(n * W).

1-D Space Optimization (Reverse Iteration)

Because row i only reads row i-1, we can use a single array. The key is to iterate w from W down to weights[i-1]. This ensures that when we read dp[w - weight] it still holds the i-1 value, not the already-updated i value.

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

  for (let i = 0; i < weights.length; i++) {
    // Reverse iteration preserves the "each item at most once" constraint
    for (let w = W; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[W];
}

console.log(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)); // 9

Space is now O(W).

Why Reverse? The 0/1 Constraint

If you iterated forward, dp[w - weights[i]] might already reflect item i being included, so the same item could be counted more than once. Reverse order guarantees each item is considered from the unmodified previous state.

Unbounded Knapsack

If items can be reused any number of times, iterate forward instead:

function unboundedKnapsack(weights, values, W) {
  const dp = new Array(W + 1).fill(0);
  for (let w = 0; w <= W; w++) {
    for (let i = 0; i < weights.length; i++) {
      if (weights[i] <= w) {
        dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
      }
    }
  }
  return dp[W];
}

Forward iteration lets the same item be picked again in the same pass.

Time and Space

Up Next

Longest Common Subsequence extends 2-D DP to two string dimensions and adds path reconstruction.