0/1 Knapsack

Dynamic programming for choices under a capacity limit

Take an item or leave it

Each item has a weight and a value, and each item may be chosen at most once. Define dp[i][w] as the greatest value possible using the first i items with capacity w. This state turns an exponential collection of subsets into a table of reusable subproblems.

Read the two source cells

If an item is too heavy, copy the value from the row above. Otherwise compare skipping it with taking it: dp[i-1][w] versus dp[i-1][w-weight] + value. The highlighted cells show both sources for every decision. The bottom-right result is 7, produced by items A and B.

	1	2	3	4	5
∅	0	0	0	0	0
A
B
C
D

With no items or zero capacity, the best value is 0.

1function knapsack(w: number[], v: number[], W: number): number {
const m = w.length;
const dp = Array.from({ length: m + 1 }, () => Array(W + 1).fill(0));
for (let i = 1; i <= m; i++) {
  for (let c = 1; c <= W; c++) {
    if (w[i - 1] > c) {
      dp[i][c] = dp[i - 1][c];
    } else {
      dp[i][c] = Math.max(
        dp[i - 1][c], dp[i - 1][c - w[i - 1]] + v[i - 1]);
    }
  }
}
return dp[m][W];
15}

Capacity5

ItemsA(weight=2, value=3) B(weight=3, value=4) C(weight=4, value=5) D(weight=5, value=6)

1 / 22

Complexity and variations

The table has n * W states, so time and full-table space are O(nW). Because each row only depends on the previous row, a one-dimensional implementation can reduce space to O(W) by iterating capacities backward.

The 0/1 restriction is encoded by reading from the previous row. Complete Knapsack changes that source so the current item can be reused. Subset Sum and many resource-allocation models are close relatives of the same recurrence.

Algorithm Visualizer

0/1 Knapsack

Take an item or leave it

Read the two source cells

Complexity and variations