Dynamic Programming

Items:

A|⚖️2|💎6

B|⚖️2|💎10

C|⚖️3|💎12

DP Table — dp[item][capacity]

↓item / w→	0	1	2	3	4	5
∅ (none)	0	0	0	0	0	0
Aw=2	0	0	0	0	0	0
Bw=2	0	0	0	0	0	0
Cw=3	0	0	0	0	0	0

Tabulation Matrix

Press Play to fill the DP table and find the optimal combination.

Debugger · v1.0

LIVE

1function knapsack(items, W) {

2 const n = items.length;

3 // Build n+1 × W+1 table

4 const dp = buildTable(n, W);

5

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

7 for (let w = 0; w <= W; w++) {

8 if (items[i-1].weight > w) {

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

10 } else {

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

12 dp[i-1][w], // skip

13 dp[i-1][w-items[i-1].weight]

14 + items[i-1].value // take

15 );

16 }

17 }

18 }

19

20 // Backtrack to find items

21 return { value: dp[n][W], dp };

22}

Debugger · v1.0

LIVE

1function knapsack(items, W) {

2 const n = items.length;

3 // Build n+1 × W+1 table

4 const dp = buildTable(n, W);

5

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

7 for (let w = 0; w <= W; w++) {

8 if (items[i-1].weight > w) {

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

10 } else {

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

12 dp[i-1][w], // skip

13 dp[i-1][w-items[i-1].weight]

14 + items[i-1].value // take

15 );

16 }

17 }

18 }

19

20 // Backtrack to find items

21 return { value: dp[n][W], dp };

22}

State Inspector

?

No variables in scope.

Capacity:5

38

1x

Dynamic Programming

0/1 Knapsack (Bottom-Up DP)

Step 1 of 6

Tabulation (Bottom-Up DP) solves all sub-problems iteratively from smallest to largest, filling a 2D table. No recursion needed — just a nested loop that builds the answer from scratch.

The Problem

Given N items with weights and values, and a knapsack of capacity W, pick items to maximize total value without exceeding W. Each item can only be picked once (0/1).