0/1 Knapsack: What the One-Array Rewrite Costs You

A cost optimiser I worked on picked a set of jobs to run under a fixed compute budget. It printed a number: the best achievable value. Finance was happy. Then someone asked the obvious follow-up — which jobs? — and the service had nothing to say, because the day before I had collapsed the DP table into a single array and shaved 687 MB off the heap.

That rewrite is taught everywhere as a free win. It is not free. It costs you the item list, and it hands you a loop-direction bug that returns a wrong answer confident enough to pass review. This post is about both prices and how to pay neither.

The two-dimensional version, and the thing it knows

You have n items with integer weights and values, and a knapsack of integer capacity W. Take each item whole or not at all. Maximise value.

The textbook table indexes items against capacity. table[i][w] is the best value using the first i items under capacity w.

const assert = (cond, msg) => { if (!cond) throw new Error(msg); };
 
function knapsackTable2D(weights, values, capacity) {
  const n = weights.length;
  const table = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));
 
  for (let i = 1; i <= n; i++) {
    const wt = weights[i - 1];
    const val = values[i - 1];
    for (let w = 0; w <= capacity; w++) {
      table[i][w] = table[i - 1][w];                       // skip item i
      if (wt <= w) {
        const take = val + table[i - 1][w - wt];           // take item i
        if (take > table[i][w]) table[i][w] = take;
      }
    }
  }
  return table;
}

Note the i - 1 on weights and values. Row i means "the first i items", so item i lives at index i - 1. Recurrences written as value[i] + dp[i-1][w - weight[i]] are off by one against this indexing, and that mismatch survives into code more often than it should.

Because every row is still on the heap, the table answers a second question the value alone cannot. Walk backwards from the last row: if table[i][w] differs from table[i-1][w], item i was taken.

function chosenItems2D(weights, values, capacity) {
  const table = knapsackTable2D(weights, values, capacity);
  const picked = [];
  let w = capacity;
 
  for (let i = weights.length; i > 0; i--) {
    if (table[i][w] !== table[i - 1][w]) {
      picked.push(i - 1);
      w -= weights[i - 1];
    }
  }
  return { value: table[weights.length][capacity], picked: picked.reverse() };
}

One array, and one direction that has to be right

Row i reads only row i - 1. So keep one array and overwrite it in place.

function knapsackValue1D(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0);
 
  for (let i = 0; i < weights.length; i++) {
    const wt = weights[i];
    const val = values[i];
    for (let w = capacity; w >= wt; w--) {            // descending
      const take = val + dp[w - wt];
      if (take > dp[w]) dp[w] = take;
    }
  }
  return dp[capacity];
}

The descending inner loop is the only thing separating this from a different problem. When you compute dp[w], you read dp[w - wt]. Descending, index w - wt is below w and has not been touched yet this item, so it still holds row i - 1 — item i unused. Ascending, dp[w - wt] was already rewritten this item, so you add item i on top of a state that already contains item i. Each item becomes reusable without limit. You have written unbounded knapsack.

Here is the ascending version, kept separate so both can run in one file.

function knapsackForwardBug(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0);
 
  for (let i = 0; i < weights.length; i++) {
    const wt = weights[i];
    const val = values[i];
    for (let w = wt; w <= capacity; w++) {            // ascending: wrong
      const take = val + dp[w - wt];
      if (take > dp[w]) dp[w] = take;
    }
  }
  return dp[capacity];
}

The answer can be right while the array is already wrong

Take the smallest instance that separates them: weights [2, 3, 4], values [3, 4, 6], capacity 8.

const w3 = [2, 3, 4];
const v3 = [3, 4, 6];
 
console.log(knapsackValue1D(w3, v3, 8));   // 10
console.log(knapsackForwardBug(w3, v3, 8)); // 12

Printed output from Node 22.23.2: 10, then 12. The correct set is the 3-weight and the 4-weight item, weight 7, value 10. The ascending loop reports 12, which is the 4-weight item counted twice — weight 8, value 12, a knapsack you cannot actually pack.

The uncomfortable part is how often the two agree anyway. Run the classic two-item teaching example, weights [2, 3], values [3, 4], capacity 5, and print the full array rather than the last cell:

function traceBoth(weights, values, capacity) {
  const down = new Array(capacity + 1).fill(0);
  const up = new Array(capacity + 1).fill(0);
  for (let i = 0; i < weights.length; i++) {
    const wt = weights[i], val = values[i];
    for (let w = capacity; w >= wt; w--) down[w] = Math.max(down[w], val + down[w - wt]);
    for (let w = wt; w <= capacity; w++) up[w] = Math.max(up[w], val + up[w - wt]);
  }
  return { down, up };
}
 
console.log(traceBoth([2, 3], [3, 4], 5));

Output: { down: [0, 0, 3, 4, 4, 7], up: [0, 0, 3, 4, 6, 7] }. Both end at 7, so the example every tutorial traces cannot tell the two loops apart. The corruption is sitting at index 4: dp[4] = 6 is the 2-weight item taken twice. Ask that array about capacity 4 and it lies. The instance you learn on is exactly the instance that hides the bug.

Four thousand instances against exhaustive search

Numbers below come from verify.mjs, run on Node 22.23.2. It generates random instances, enumerates all 2^n subsets as ground truth, and compares.

function bestSubsetBrute(weights, values, capacity) {
  const n = weights.length;
  let best = 0;
  for (let mask = 0; mask < (1 << n); mask++) {
    let w = 0, v = 0;
    for (let i = 0; i < n; i++) {
      if (mask & (1 << i)) { w += weights[i]; v += values[i]; }
    }
    if (w <= capacity && v > best) best = v;
  }
  return best;
}
 
function unboundedOptimum(weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0);
  for (let w = 1; w <= capacity; w++) {
    for (let i = 0; i < weights.length; i++) {
      if (weights[i] > 0 && weights[i] <= w) {
        dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
      }
    }
  }
  return dp[capacity];
}
 
const randInt = (a, b) => a + Math.floor(Math.random() * (b - a + 1));
let matched = 0, forwardHigher = 0, forwardEqual = 0, forwardIsUnbounded = 0;
 
for (let t = 0; t < 4000; t++) {
  const n = randInt(1, 14), capacity = randInt(0, 40);
  const weights = [], values = [];
  for (let i = 0; i < n; i++) { weights.push(randInt(1, 15)); values.push(randInt(0, 20)); }
 
  const truth = bestSubsetBrute(weights, values, capacity);
  const down = knapsackValue1D(weights, values, capacity);
  const up = knapsackForwardBug(weights, values, capacity);
 
  if (down === truth) matched++;
  if (up > truth) forwardHigher++;
  else if (up === truth) forwardEqual++;
  if (up === unboundedOptimum(weights, values, capacity)) forwardIsUnbounded++;
}
assert(matched === 4000, "descending loop disagreed with exhaustive search");
console.log({ matched, forwardHigher, forwardEqual, forwardIsUnbounded });

One run: { matched: 4000, forwardHigher: 3261, forwardEqual: 739, forwardIsUnbounded: 4000 }. Four repeats put forwardEqual between 739 and 744. The descending loop agreed with exhaustive search on all 4000 every time. The ascending loop overshot on about 3,260 and quietly agreed on the rest — and on every single instance it equalled the unbounded-knapsack optimum, which is the precise statement of what the wrong direction computes. A separate sweep of 400 instances at n = 15..18: zero disagreements for the descending loop, 379 overshoots for the ascending one.

Silently agreeing on roughly one instance in five is what makes this dangerous. A bug that always fails gets caught.

What the collapse throws away

Now the part nobody prices. Run chosenItems2D and check that the recovered set is real — weight within capacity, value equal to the reported optimum:

let setsValid = 0;
for (let t = 0; t < 4000; t++) {
  const n = randInt(1, 12), capacity = randInt(0, 35);
  const weights = [], values = [];
  for (let i = 0; i < n; i++) { weights.push(randInt(1, 12)); values.push(randInt(0, 20)); }
 
  const truth = bestSubsetBrute(weights, values, capacity);
  const { value, picked } = chosenItems2D(weights, values, capacity);
  const sumW = picked.reduce((s, i) => s + weights[i], 0);
  const sumV = picked.reduce((s, i) => s + values[i], 0);
  if (value === truth && sumW <= capacity && sumV === truth) setsValid++;
}
assert(setsValid === 4000, "2-D reconstruction produced an invalid set");
console.log({ setsValid });

{ setsValid: 4000 }. Every recovered set packs and every recovered set is worth the reported optimum.

There is no equivalent for knapsackValue1D. The information is destroyed, not hidden: after item i overwrites dp[w], nothing anywhere records whether the new value came from taking item i or from a decision three items ago. You cannot recover an argmax from a maximum you overwrote in place.

What keeping the table costs

Times from bench.mjs, Node 22.23.2, --expose-gc, weights drawn from 1 to W/4. Heap delta is process.memoryUsage().heapUsed measured around the call after a forced GC.

The 1-D array held steady at a 0.35 MB heap delta at n = 2000, W = 20000, since it allocates W + 1 numbers regardless of n. Both are O(n·W) time and the measurements track that: work grows 100× from the first row to the third, 1-D time grows 72×. The 2-D version is consistently 5 to 8 times slower at equal work, which is allocation and pointer chasing through an array of arrays, not extra arithmetic.

So the honest trade is not "same speed, less memory". It is: pay roughly 8 bytes per (item, capacity) pair and several times the wall clock, and in exchange you can name the items.

Getting the set back without keeping the table

That trade is a false binary, and this is the part the tutorials skip. You can recover the chosen set in O(W) space by splitting the item list in half, solving each half forward into its own 1-D array, finding the capacity split that maximises the sum, and recursing into both halves.

function rowDP(indices, weights, values, capacity) {
  const dp = new Array(capacity + 1).fill(0);
  for (const i of indices) {
    const wt = weights[i], val = values[i];
    for (let w = capacity; w >= wt; w--) {
      const take = val + dp[w - wt];
      if (take > dp[w]) dp[w] = take;
    }
  }
  return dp;
}
 
function chosenItemsLinearSpace(weights, values, capacity) {
  const out = [];
  function solve(indices, cap) {
    if (indices.length === 0) return;
    if (indices.length === 1) {
      const i = indices[0];
      if (weights[i] <= cap && values[i] > 0) out.push(i);
      return;
    }
    const mid = indices.length >> 1;
    const left = indices.slice(0, mid), right = indices.slice(mid);
    const f = rowDP(left, weights, values, cap);
    const g = rowDP(right, weights, values, cap);
 
    let best = -1, split = 0;
    for (let w = 0; w <= cap; w++) {
      const total = f[w] + g[cap - w];
      if (total > best) { best = total; split = w; }
    }
    solve(left, split);
    solve(right, cap - split);
  }
  solve(weights.map((_, i) => i), capacity);
  return out.sort((a, b) => a - b);
}

Across 3000 random instances it returned a valid set on 3000, matching the value from the 2-D reconstruction every time. At n = 3000, W = 30000 with 521 items in the optimal set, from recon.mjs:

It is faster here despite doing O(n·W log n) arithmetic instead of O(n·W), because at this size allocating and traversing 687 MB dominates the extra passes. On smaller inputs the 2-D walk wins on time. The memory gap does not close.

The failures that have nothing to do with direction

Three edge cases, all run through verify.mjs against exhaustive search, all found in code that was otherwise correct.

Recursive solutions that stop at capacity === 0. That early return is wrong whenever a zero-weight item carries value: at weight 0 and value 9, capacity 0, the true optimum is 9 and the recursion returns 0. Across 4000 random instances including zero weights, a textbook recursion with that base case disagreed with exhaustive search 177 times. Stop on the item index alone.

Non-integer weights. Every version here indexes dp by weight. Give it weights [1.5, 2.5], values [10, 12], capacity 4, and dp[w - wt] reads a fractional index that holds undefined. Both the 1-D and the 2-D versions returned NaN; the true optimum is 22. There is no error and no warning. If your weights can be decimals, scale them to integers first and state the granularity you scaled to.

Capacity 0, empty item list, every item heavier than the bag, all values zero. All four return 0, which is correct, and all four are worth a fixture: they are the cases where an off-by-one in the loop bounds throws undefined rather than returning a wrong number.

Which question are you answering?

Every knapsack call sits on one side of a line. A budget check, a feasibility gate, a subset-sum yes/no, a score in a ranking loop — those want a number, and the single array is correct, smaller, and faster. A scheduler, a packing plan, a bill of materials, anything a human will read and act on — those want the set, and a number alone will be sent straight back to you.

The mistake is not choosing the 1-D version. The mistake is choosing it before knowing which side of the line you are on, then discovering the answer in a meeting. So before you delete that table: who is going to ask which items, and what will you tell them?