jsschools

0/1 Knapsack Problem

Finds the maximum value subset of items that fits within a weight capacity, where each item can be taken at most once, using dynamic programming.

Spec ↗

Syntax

knapsack01(weights, values, capacity)

Parameters

NameTypeRequiredDescription
weights number[] Yes Array of item weights (non-negative integers).
values number[] Yes Array of item values, parallel to weights.
capacity number Yes Maximum total weight the knapsack can hold.

Returns

number — Maximum total value achievable without exceeding capacity.

Examples

function knapsack01(weights, values, capacity) {
  const n = weights.length;
  // dp[w] = max value achievable with capacity w
  const dp = new Array(capacity + 1).fill(0);

  for (let i = 0; i < n; i++) {
    // Iterate backwards to avoid using item i twice
    for (let w = capacity; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[capacity];
}

const weights  = [2, 3, 4, 5];
const values   = [3, 4, 5, 6];
const capacity = 5;
console.log(knapsack01(weights, values, capacity));
Output 
7

// Reconstruct which items were chosen
function knapsack01WithItems(weights, values, capacity) {
  const n = weights.length;
  const dp = Array.from({length: n + 1}, () => new Array(capacity + 1).fill(0));
  for (let i = 1; i <= n; i++)
    for (let w = 0; w <= capacity; w++) {
      dp[i][w] = dp[i-1][w];
      if (weights[i-1] <= w)
        dp[i][w] = Math.max(dp[i][w], dp[i-1][w-weights[i-1]] + values[i-1]);
    }
  // Backtrack
  const chosen = [];
  let w = capacity;
  for (let i = n; i > 0; i--)
    if (dp[i][w] !== dp[i-1][w]) { chosen.push(i-1); w -= weights[i-1]; }
  return { maxValue: dp[n][capacity], items: chosen.reverse() };
}

console.log(knapsack01WithItems([2,3,4,5],[3,4,5,6],5));
Output 
{ maxValue: 7, items: [ 0, 1 ] }

Notes

| Case | Time | Space | |---------|------------|------------| | Best | O(n·W) | O(W) | | Average | O(n·W) | O(W) | | Worst | O(n·W) | O(W) | where n = number of items and W = capacity. This is **pseudo-polynomial** — it is exponential in the input size if W is encoded in binary. The 1D DP array (bottom-up, right-to-left) uses O(W) space vs the 2D table's O(nW). Traversing weights right-to-left in the 1D version ensures each item is used at most once. For the unbounded knapsack (items reusable), iterate weights left-to-right instead.

See also