Dynamic Programming • 2D Arrays

0/1 Knapsack

Given a set of items with weights and values, find the subset that maximizes value without exceeding a capacity W.

Overview

The 0/1 Knapsack is the foundation for all subset and combinatorics DP problems. You can either pick an item (1) or skip it (0).

We use a 2D table `dp[i][w]`, representing the maximum value attainable using the first `i` items with a knapsack capacity of `w`.

If the item's weight exceeds current capacity `w`, we CANNOT pick it. If it fits, we take the maximum between picking it and skipping it.

Because row `i` only depends on row `i-1`, we can optimize this to a 1D array of size `W`, iterating backwards to prevent reusing the same item.

Item \ Cap	0	1	2	3	4	5
None	0	0	0	0	0	0
I1 (w2,v3)	0	0	0	0	0	0
I2 (w3,v4)	0	0	0	0	0	0
I3 (w4,v5)	0	0	0	0	0	0

Code Tracker

:::

1for (let i = 1; i <= n; i++) {

2 for (let w = 1; w <= W; w++) {

3 if (wt[i-1] <= w) {

4 dp[i][w] = Math.max(

5 dp[i-1][w], // Skip

6 val[i-1] + dp[i-1][w - wt[i-1]] // Pick

7 );

8 } else {

9 dp[i][w] = dp[i-1][w]; // Must skip

10 }

11 }

12}