0 1 Knapsack Problem in DSA C - Execution Trace

Concept Flow - 0 1 Knapsack Problem

Start with empty knapsack

↓

For each item i

↓

For each weight w from 0 to W

↓

Check if item i fits (weight[i

↓

Include item i: value[i

↓

Update dp[i

↓

Repeat for all items and weights

↓

Final answer in dp[n

We fill a table dp where each cell dp[i][w] stores the best value using first i items with max weight w. For each item and weight, we decide to include or exclude the item to maximize value.

Execution Sample

DSA C

int dp[4][8] = {0};
int weights[] = {1, 3, 4};
int values[] = {1, 4, 5};
int W = 7;

// Fill dp table

This code fills a dp table for 3 items and max weight 7 to find max value.

Execution Table

Step	Operation	Item i	Weight w	Include Item Value	Exclude Item Value	dp[i][w] Updated	dp Table State
1	Initialize dp row 0	0	0-7	-	-	0	[0,0,0,0,0,0,0,0]
2	Process item 1	1	0	-	dp[0][0]=0	0	[0,0,0,0,0,0,0,0]
3	Process item 1	1	1	value=1 + dp[0][0]=0	dp[0][1]=0	1	[0,1,0,0,0,0,0,0]
4	Process item 1	1	2	value=1 + dp[0][1]=0	dp[0][2]=0	1	[0,1,1,0,0,0,0,0]
5	Process item 1	1	3	value=1 + dp[0][2]=0	dp[0][3]=0	1	[0,1,1,1,0,0,0,0]
6	Process item 1	1	4	value=1 + dp[0][3]=0	dp[0][4]=0	1	[0,1,1,1,1,0,0,0]
7	Process item 1	1	5	value=1 + dp[0][4]=0	dp[0][5]=0	1	[0,1,1,1,1,1,0,0]
8	Process item 1	1	6	value=1 + dp[0][5]=0	dp[0][6]=0	1	[0,1,1,1,1,1,1,0]
9	Process item 1	1	7	value=1 + dp[0][6]=0	dp[0][7]=0	1	[0,1,1,1,1,1,1,1]
10	Process item 2	2	0	-	dp[1][0]=0	0	[0,1,1,1,1,1,1,1]
11	Process item 2	2	1	-	dp[1][1]=1	1	[0,1,1,1,1,1,1,1]
12	Process item 2	2	2	-	dp[1][2]=1	1	[0,1,1,1,1,1,1,1]
13	Process item 2	2	3	value=4 + dp[1][0]=0	dp[1][3]=1	4	[0,1,1,4,1,1,1,1]
14	Process item 2	2	4	value=4 + dp[1][1]=1	dp[1][4]=1	5	[0,1,1,4,5,1,1,1]
15	Process item 2	2	5	value=4 + dp[1][2]=1	dp[1][5]=1	5	[0,1,1,4,5,5,1,1]
16	Process item 2	2	6	value=4 + dp[1][3]=4	dp[1][6]=1	8	[0,1,1,4,5,5,8,1]
17	Process item 2	2	7	value=4 + dp[1][4]=5	dp[1][7]=1	9	[0,1,1,4,5,5,8,9]
18	Process item 3	3	0	-	dp[2][0]=0	0	[0,1,1,4,5,5,8,9]
19	Process item 3	3	1	-	dp[2][1]=1	1	[0,1,1,4,5,5,8,9]
20	Process item 3	3	2	-	dp[2][2]=1	1	[0,1,1,4,5,5,8,9]
21	Process item 3	3	3	-	dp[2][3]=4	4	[0,1,1,4,5,5,8,9]
22	Process item 3	3	4	value=5 + dp[2][0]=0	dp[2][4]=5	5	[0,1,1,4,5,5,8,9]
23	Process item 3	3	5	value=5 + dp[2][1]=1	dp[2][5]=5	6	[0,1,1,4,5,6,8,9]
24	Process item 3	3	6	value=5 + dp[2][2]=1	dp[2][6]=8	6	[0,1,1,4,5,6,8,9]
25	Process item 3	3	7	value=5 + dp[2][3]=4	dp[2][7]=9	9	[0,1,1,4,5,6,8,9]
26	End	-	-	-	-	-	Final dp table filled

💡 All items processed for all weights up to W=7, dp table complete

Variable Tracker

Variable	Start	After Step 9	After Step 17	After Step 25	Final
dp row	[0,0,0,0,0,0,0,0]	[0,1,1,1,1,1,1,1]	[0,1,1,4,5,5,8,9]	[0,1,1,4,5,6,8,9]	[0,1,1,4,5,6,8,9]
i (item index)	0	1	2	3	3
w (weight)	0	7	7	7	7

Key Moments - 3 Insights

Why do we add value[i] to dp[i-1][w-weight[i]] when including an item?

Because dp[i-1][w-weight[i]] represents the best value achievable with previous items and remaining weight after including current item. See rows 13,14 where inclusion sums value[i] + dp from smaller weight.

Why do we sometimes keep dp[i][w] same as dp[i-1][w]?

When the item doesn't fit or excluding it gives better value, we keep dp[i][w] same as dp[i-1][w]. For example, in rows 2,3, and 10,11 exclusion is chosen.

Why does the dp table have one extra row and column?

Row 0 and column 0 represent base cases: no items or zero capacity. This simplifies logic by providing initial values, as seen in step 1.

Visual Quiz - 3 Questions

Look at the execution_table at step 16, what is the value of dp[2][6]?

A 6

B 5

C 8

D 9

💡 Hint

Check the 'dp[i][w] Updated' column at step 16 in execution_table

At which step does the dp table first update dp[i][w] to 4?

A Step 21

B Step 13

C Step 14

D Step 22

💡 Hint

Look for dp[i][w] Updated column with value 4 in execution_table

If the weight of item 2 changed from 3 to 2, how would dp[2][3] change at step 13?

A It would become 5

B It would remain 4

C It would become 1

D It would become 0

💡 Hint

Including item 2 at weight 3 would add value[2] + dp[i-1][w-weight[i]]; with smaller weight, dp index changes

Concept Snapshot

0 1 Knapsack Problem:
- Use dp[i][w] for max value with first i items and weight limit w
- For each item and weight, choose max(include, exclude)
- Include: value[i] + dp[i-1][w-weight[i]] if fits
- Exclude: dp[i-1][w]
- Final answer at dp[n][W]

Full Transcript

The 0 1 Knapsack problem uses a table dp where dp[i][w] stores the best value using first i items with max weight w. We fill this table row by row, checking for each item if it fits in the current weight. If it fits, we consider including it by adding its value plus the best value for remaining weight. Otherwise, we exclude it and keep previous best. The final answer is in dp[n][W]. The execution table shows step-by-step how dp is updated for each item and weight. Key moments clarify why we add values and why base cases exist. The visual quiz tests understanding of dp values at specific steps and effects of weight changes.