DSA · Patterns, not puzzles

How do you solve the knapsack problem?

Hardknapsackdynamic-programmingoptimizationUpdated Oct 2026

Short answer

For 0/1 knapsack, define dp[c] as the best value achievable with capacity c, then process each item and update capacities backwards. The reverse loop prevents using the same item more than once.

In 0/1 knapsack, each item can be taken at most once. The state is the capacity remaining, and the decision is take or skip the current item. Processing items one at a time turns an exponential search into a table with O(n * capacity) states.

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

The capacity loop runs backwards so dp[c - weight] still refers to the previous item's row.

Why the loop direction matters

Backwards iteration gives 0/1 behaviour because each item is used once
Forwards iteration gives unbounded knapsack, where an item can be reused
The state is the capacity, not the item index, in the one-dimensional version
Time is O(n * capacity), space is O(capacity)

function knapsackTable(weights, values, capacity) {
  const rows = weights.length + 1;
  const dp = Array.from({ length: rows }, () =>
    new Array(capacity + 1).fill(0),
  );
  for (let i = 1; i < rows; i++) {
    for (let c = 0; c <= capacity; c++) {
      dp[i][c] = dp[i - 1][c];
      if (weights[i - 1] <= c) {
        dp[i][c] = Math.max(
          dp[i][c],
          dp[i - 1][c - weights[i - 1]] + values[i - 1],
        );
      }
    }
  }
  return dp[weights.length][capacity];
}

The two-dimensional version is easier to read and shows why the one-dimensional version can roll over.

The complexity is pseudo-polynomial because it depends on the numeric capacity, not just the number of items. A huge capacity makes this table impractical.

Follow-ups you should expect

Interviewers use these to check whether the first answer was understanding or memorisation.

1Why does 0/1 knapsack iterate capacity backwards?
2How does unbounded knapsack change the loop?
3How would you reconstruct which items were chosen?
4Why is the complexity called pseudo-polynomial?

Say it in the interview

I define the state as the best value for each capacity, then decide for each item whether taking it improves the current best. I iterate capacity backwards so the item is not reused, which gives the transition dp[c] = max(dp[c], dp[c - weight] + value). If I need the chosen items, I keep a table or store decisions. The runtime depends on capacity, so it is pseudo-polynomial.

Use this as a model, not a script. Saying it in your own words is what makes it survive follow-up pressure.

Now say it out loud.

Understanding an answer and delivering it under pressure are different skills. Rehearse this topic in a live DSA mock interview and get scored feedback on depth, clarity and confidence.

Start a free DSA interview Browse all questions

Why the loop direction matters

Follow-ups you should expect

Related questions

Now say it out loud.