You’re packing a bag for a trip. Every item has a weight and a value; the bag has a capacity; you must choose a subset that maximizes total value without exceeding the limit.

Each item is either taken whole or skipped — no splitting, hence “0/1.” With a few items this is easy to eyeball; with dozens it becomes combinatorially explosive. Dynamic programming tames it by filling a table one decision at a time.

How It Works

The DP defines dp[i][w] = the best value achievable using only the first i items with a capacity of w:

1. Initialize: every cell in row 0 (no items) and column 0 (no capacity) is 0.
2. Skip: without the current item, the value is dp[i-1][w].
3. Take: if the item fits, the value with it is dp[i-1][w - weight] + value.
4. Choose: store the maximum of the two — that’s the recurrence:

   dp[i][w] = max(dp[i-1][w], dp[i-1][w - weight[i]] + value[i])

Key Insight

Every cell depends only on the cell above (skip) and the cell above-and-left (take). Because any subproblem’s optimal solution builds from optimal solutions of smaller subproblems — optimal substructure — filling the table row-by-row yields the global optimum.

The answer sits in the bottom-right cell dp[n][W]. Walking backward through the table recovers exactly which items were chosen.

Worked Example

The visualizer packs these items into a bag of capacity 7:

Filling the table row by row, the bottom-right cell reaches dp[5][7] = 9. The optimal subset is Laptop (3w, 4v) + Camera (2w, 3v) + Watch (1w, 2v) = total value 4 + 3 + 2 = 9, total weight 3 + 2 + 1 = 6 ≤ 7. Watch the visualizer’s backtrack step highlight this exact path from the bottom-right cell back to the top-left, confirming each chosen item.

Edge Cases & Pitfalls

• Item heavier than capacity — the “take” option is impossible: the cell must use “skip” only (dp[i-1][w]).
• Zero-capacity column — nothing fits: every cell is 0.
• Huge capacities — O(nW) is pseudo-polynomial: fine for moderate W, but exponential in the bit length of W. This is why knapsack is NP-hard in general.
• Ties — multiple subsets can tie for max value; backtracking returns one of them.
• Empty item set — row 0 is all zeros: the answer is 0.

Comparison: 0/1 vs Fractional Knapsack

Applications

• Resource allocation — project selection under a fixed budget
• Cargo loading — maximizing shipment value under weight limits
• Portfolio optimization — selecting investments under a capital cap

Practice Trajectory

1. Hand-fill the dp table for the visualizer’s items and confirm the bottom-right value.
2. Explain why every cell depends only on the cell above and above-left.
3. Backtrack from the optimum by hand to recover the chosen items.
4. Construct an instance where a greedy ratio approach fails for 0/1.
5. Implement the O(W) space optimization that drops the item dimension (length only).