0‑1 Knapsack Problem: Detailed Explanation and JavaScript Implementation

The 0‑1 knapsack problem asks for the maximum total value that can be placed into a knapsack of capacity W when each of the n items can be taken at most once, with weight weights[i] and value values[i].

We define f(i, j) as the maximum value achievable using items i…n with remaining capacity j. The recurrence is:

f(i, j) = max( f(i‑1, j), f(i‑1, j‑weights[i]) + values[i] )
if j < weights[i] then f(i, j) = f(i‑1, j)

Using this recurrence we fill a DP table row by row. The first row (item 0) is initialized directly: if the capacity is less than its weight the value is 0, otherwise it equals values[0]. Subsequent rows are computed by comparing the two cases above.

A complete JavaScript implementation follows, preserving the original code structure:

function knapsack(weights, values, W){
  var n = weights.length - 1;
  var f = [[]];
  for (var j = 0; j <= W; j++){
    if (j < weights[0]) f[0][j] = 0;
    else f[0][j] = values[0];
  }
  for (var i = 1; i <= n; i++){
    f[i] = [];
    for (var j = 0; j <= W; j++){
      if (j < weights[i]) f[i][j] = f[i-1][j];
      else f[i][j] = Math.max(f[i-1][j], f[i-1][j-weights[i]] + values[i]);
    }
  }
  return f[n][W];
}
var a = knapsack([2,2,6,5,4],[6,3,5,4,6],10);
console.log(a);

Optimizations include merging the outer loops, using a single‑dimensional array with a “‑1” row to avoid special‑case handling for the first item, and careful boundary checks (e.g., using j < weights[i] without equality). These tweaks reduce branching and improve cache locality.

The article also discusses why modern implementations prefer zero‑based indexing and a sentinel row, contrasting with older tutorials that start counting from 1.