How is the classic "knapsack problem" solved in dynamic programming?

AlgorithmsJunior~3 min read

Short answer

The classic 0/1 knapsack problem is solved with dynamic programming. We define the state dp[i][w] as the maximum value using the first i items under weight limit w. Transition: dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]) when w >= weight[i], otherwise dp[i][w] = dp[i-1][w]. Base cases: dp[0][w] = 0 and dp[i][0] = 0. Complexity: O(nW) time and O(nW) memory, optimized down to O(W) memory with a single-pass update of w from W to 0.

Detailed breakdown

The setup

Given n items, item i has weight weight[i] and value value[i]. There is a knapsack with capacity W. We need to maximize the total value without exceeding W. Each item can be taken at most once (0/1).

The dynamic programming idea

State: dp[i][w] is the maximum value using the first i items at allowed weight w.
Transition:
Don't take item i: dp[i-1][w].
Take item i (if weight[i] <= w): dp[i-1][w - weight[i]] + value[i]. Total: dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i]) when weight[i] <= w; otherwise dp[i][w] = dp[i-1][w].
Base: dp[0][w] = 0 for all w, and dp[i][0] = 0 for all i.
Computation order: i from 1 to n, w from 0 to W.
Complexity: time O(nW); memory O(nW), optimized to O(W) with a 1D array and a reverse pass over w.

Example

weights = [3, 2, 4, 5], values = [4, 3, 5, 6], W = 8. The optimal choice is the items with weights 3 and 5 (values 4 and 6): total value = 10, total weight = 8.

Implementation (2D DP + reconstructing the answer)

javascript

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

  for (let i = 1; i <= n; i++) {
    const wt = weights[i - 1];
    const val = values[i - 1];
    for (let w = 0; w <= W; w++) {
      // Don't take item i
      dp[i][w] = dp[i - 1][w];

      // Try taking item i, if it fits
      if (wt <= w) {
        const candidate = dp[i - 1][w - wt] + val;
        if (candidate > dp[i][w]) {
          dp[i][w] = candidate;
          take[i][w] = true;
        }
      }
    }
  }

  // Reconstruct the chosen item indices
  const chosenIndices = [];
  let w = W;
  for (let i = n; i >= 1; i--) {
    if (take[i][w]) {
      chosenIndices.push(i - 1);
      w -= weights[i - 1];
    }
  }
  chosenIndices.reverse();

  return { maxValue: dp[n][W], chosenIndices, dp }; // dp is returned optionally
}

// Example
const weights = [3, 2, 4, 5];
const values = [4, 3, 5, 6];
const W = 8;
const result = knapsack01(weights, values, W);
console.log(result); // { maxValue: 10, chosenIndices: [0, 3] }

Memory optimization down to O(W)

To avoid overwriting the current item iteration's values, iterate w in reverse order (from W down to wt). In this form it's harder to reconstruct the chosen items without extra structures, but it computes the maximum value correctly.

javascript

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

  for (let i = 0; i < n; i++) {
    const wt = weights[i];
    const val = values[i];
    for (let w = W; w >= wt; w--) {
      dp[w] = Math.max(dp[w], dp[w - wt] + val);
    }
  }
  return dp[W];
}

// Example
console.log(knapsack01Optimized([3, 2, 4, 5], [4, 3, 5, 6], 8)); // 10

Common knapsack pitfalls

For the 1D DP version you must iterate w from W down to 0, otherwise you get an "unbounded" knapsack (each item could be used multiple times).
Distinguish the 0/1 knapsack from the variant with an unlimited number of items and from the "fractional" knapsack (which is solved greedily).
Correctly initialize the base: the row and column with zero indices are zeros.
It's convenient to store the answer reconstruction through a take[i][w] matrix or a parent pointer; with 1D DP this is harder without extra structures.

What's important to say in the interview

The definition of the dp state and why it correctly models the subproblems.
The transition and the justification for choosing max between the two options (take/don't take).
The base, the traversal order, and the complexity estimate.
The memory optimization down to O(W) and why a reverse pass over w is needed.
How to reconstruct the set of items (via take/parent, or storing extra data).

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.