Suggest an edit

Improve this article

Refine the answer for “How is the classic "knapsack problem" solved in dynamic programming?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 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(n*W) time and O(n*W) 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(n*W); memory O(n*W), 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

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

Markdown · drag & drop images · ⌘B / ⌘I shortcuts764 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.