Unbounded Knapsack Problem in DSA C - Execution Trace

Concept Flow - Unbounded Knapsack Problem

Start with capacity W

↓

Initialize dp array with 0

↓

For each capacity c from 1 to W

↓

For each item i

↓

If item weight <= c

↓

Update dp[c

↓

Repeat for all capacities

↓

Result in dp[W

We fill a dp array where each position c stores max value for capacity c by trying all items repeatedly.

Execution Sample

DSA C

int dp[W+1] = {0};
for (int c = 1; c <= W; c++) {
  for (int i = 0; i < n; i++) {
    if (weight[i] <= c) {
      dp[c] = max(dp[c], dp[c - weight[i]] + value[i]);
    }
  }
}

This code computes max value for each capacity c by considering all items multiple times.

Execution Table

Step	Operation	Capacity c	Item i	Condition (weight[i] <= c)	dp[c] Before	dp[c] After	dp Array State
1	Initialize dp array	-	-	-	-	-	[0,0,0,0,0,0,0,0]
2	c=1, i=0	1	0	1 <= 1 True	0	max(0, dp[1-1]+1)=1	[0,1,0,0,0,0,0,0]
3	c=1, i=1	1	1	3 <= 1 False	1	1	[0,1,0,0,0,0,0,0]
4	c=2, i=0	2	0	1 <= 2 True	0	max(0, dp[2-1]+1)=max(0,1+1)=2	[0,1,2,0,0,0,0,0]
5	c=2, i=1	2	1	3 <= 2 False	2	2	[0,1,2,0,0,0,0,0]
6	c=3, i=0	3	0	1 <= 3 True	0	max(0, dp[3-1]+1)=max(0,2+1)=3	[0,1,2,3,0,0,0,0]
7	c=3, i=1	3	1	3 <= 3 True	3	max(3, dp[3-3]+4)=max(3,0+4)=4	[0,1,2,4,0,0,0,0]
8	c=4, i=0	4	0	1 <= 4 True	0	max(0, dp[4-1]+1)=max(0,4+1)=5	[0,1,2,4,5,0,0,0]
9	c=4, i=1	4	1	3 <= 4 True	5	max(5, dp[4-3]+4)=max(5,1+4)=5	[0,1,2,4,5,0,0,0]
10	c=5, i=0	5	0	1 <= 5 True	0	max(0, dp[5-1]+1)=max(0,5+1)=6	[0,1,2,4,5,6,0,0]
11	c=5, i=1	5	1	3 <= 5 True	6	max(6, dp[5-3]+4)=max(6,2+4)=6	[0,1,2,4,5,6,0,0]
12	c=6, i=0	6	0	1 <= 6 True	0	max(0, dp[6-1]+1)=max(0,6+1)=7	[0,1,2,4,5,6,7,0]
13	c=6, i=1	6	1	3 <= 6 True	7	max(7, dp[6-3]+4)=max(7,4+4)=8	[0,1,2,4,5,6,8,0]
14	c=7, i=0	7	0	1 <= 7 True	0	max(0, dp[7-1]+1)=max(0,8+1)=9	[0,1,2,4,5,6,8,9]
15	c=7, i=1	7	1	3 <= 7 True	9	max(9, dp[7-3]+4)=max(9,5+4)=9	[0,1,2,4,5,6,8,9]
16	End	-	-	-	-	-	dp[7] = 9 (max value)

💡 Capacity c reached W=7, all items considered, dp array fully computed

Variable Tracker

Variable	Start	After Step 2	After Step 4	After Step 6	After Step 7	After Step 8	After Step 13	After Step 15	Final
c	-	1	2	3	3	4	6	7	7
i	-	0	0	0	1	0	1	1	-
dp[c]	0	1	2	3	4	5	8	9	9
dp array	[0,0,0,0,0,0,0,0]	[0,1,0,0,0,0,0,0]	[0,1,2,0,0,0,0,0]	[0,1,2,3,0,0,0,0]	[0,1,2,4,0,0,0,0]	[0,1,2,4,5,0,0,0]	[0,1,2,4,5,6,8,0]	[0,1,2,4,5,6,8,9]	[0,1,2,4,5,6,8,9]

Key Moments - 3 Insights

Why do we update dp[c] multiple times for the same capacity c?

Because we consider all items for each capacity c, dp[c] is updated if using an item improves the value. See steps 6 and 7 where dp[3] changes twice.

Why can we use the same item multiple times in unbounded knapsack?

Because for each capacity c, we check all items and update dp[c] using dp[c - weight[i]] + value[i], allowing repeated use. This is shown in the loop over items inside the capacity loop.

Why does dp array start with zeros?

Because with zero capacity, max value is zero. This base case initializes dp and allows building up solutions for larger capacities.

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is dp[3] after considering item 1?

A 0

B 3

C 4

D 1

💡 Hint

Check dp[c] After column at step 7 in execution_table

At which capacity c does dp[c] first reach the value 5?

A c=4

B c=3

C c=5

D c=6

💡 Hint

Look at dp array state after step 8 in execution_table

If the weight of item 1 was increased to 4, how would dp[3] change at step 7?

A dp[3] would become 0

B dp[3] would remain 3

C dp[3] would become 4

D dp[3] would become 1

💡 Hint

Check condition weight[i] <= c at step 7; if false, dp[c] does not update

Concept Snapshot

Unbounded Knapsack Problem:
- Use dp array of size W+1 for capacities 0..W
- dp[c] = max value for capacity c
- For each capacity c, try all items
- If item weight <= c, dp[c] = max(dp[c], dp[c - weight] + value)
- Items can be used unlimited times
- Result is dp[W]

Full Transcript

The Unbounded Knapsack Problem finds the maximum value achievable with unlimited copies of items within a capacity W. We use a dp array where dp[c] stores max value for capacity c. We initialize dp with zeros. For each capacity from 1 to W, we check each item. If the item's weight is less or equal to the current capacity, we update dp[c] by comparing current dp[c] and dp[c - weight] + value. This allows repeated use of items. After filling dp for all capacities, dp[W] holds the answer. The execution table shows step-by-step updates of dp array and how values improve. Key moments clarify why dp updates multiple times and why dp starts with zeros. The visual quiz tests understanding of dp updates and conditions.