0/1 Knapsack

How it works, step by step

1. 1

   Build a table: one row per item, one column per capacity from 0 to W. Cell [i][c] means: the best value using only the first i items, with c capacity.

2. 2

   Row zero is all zeros: with no items, every capacity is worth nothing. Every later answer stands on this base.

3. 3

   Fill row by row. Each cell is one decision about item i. Option one, skip it: the value is the cell right above (same capacity, one item fewer).

4. 4

   Option two, take it (only if it fits, c >= weight): its value plus the cell above-left at [i-1][c - weight] - the best you could do with the space that remains.

5. 5

   Write the bigger of the two. That is the whole algorithm: every cell reads at most two earlier cells.

6. 6

   The bottom-right cell is the best possible value. To learn which items: walk back up. If a cell differs from the one above, that item was taken - subtract its weight and keep climbing.

The code, in JavaScript

function knapsack(items, capacity) {
  const n = items.length;
  // (n+1) x (capacity+1), row 0 = "no items" = all zeros
  const dp = Array.from({ length: n + 1 }, () =>
    new Array(capacity + 1).fill(0)
  );

  for (let i = 1; i <= n; i++) {
    const { w, v } = items[i - 1];
    for (let c = 0; c <= capacity; c++) {
      dp[i][c] = dp[i - 1][c];               // option 1: skip the item
      if (c >= w) {
        // option 2: take it - its value + best of the space left
        dp[i][c] = Math.max(dp[i][c], dp[i - 1][c - w] + v);
      }
    }
  }

  return dp[n][capacity];
}

const items = [
  { w: 2, v: 3 },
  { w: 3, v: 4 },
  { w: 4, v: 5 },
  { w: 5, v: 6 },
];
knapsack(items, 8);   // → 10  (items 2 and 4: weight 3+5, value 4+6)

Dry run: packing a bag of capacity 8 from 4 items

The same steps the visualizer plays, written as a table. Generated by running the real algorithm - not written by hand.

• In the 1-D version the capacity loop must run backwards. Forwards, dp[c - w] already contains the current item, so it gets packed again and again - you silently solve unbounded knapsack. With our scene, forwards returns 12 (the 2 kg item four times) instead of 10.
• O(n·W) looks polynomial but is pseudo-polynomial: W is a number in the input, not a size. Capacity 8 means 9 columns; capacity 2 billion means 2 billion columns from the same few input digits. This is why knapsack stays NP-hard despite the 'fast' table.
• Greedy by value-per-weight fails for 0/1. Capacity 4, items (w3, v5) and two of (w2, v3): the ratio picks (w3, v5) first, blocking both others - total 5. Best is the two small ones - total 6. If a greedy answer were enough, you would not need the table.
• Do not mix the problems up in an interview: fractional knapsack IS greedy (ratio sort is provably optimal there), 0/1 is not. Saying 'knapsack, so greedy by ratio' is exactly backwards for the 0/1 version.

0/1 Knapsack vs. its closest relatives