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.

Practice

1. What is the main difference between the 0/1 Knapsack Problem and the Unbounded Knapsack Problem?

easy

A. In Unbounded Knapsack, you can use unlimited copies of each item.

B. In Unbounded Knapsack, items cannot be repeated.

C. Unbounded Knapsack only works with fractional items.

D. Unbounded Knapsack requires items to be sorted by weight.

Solution

1. Step 1: Understand item usage in 0/1 Knapsack

   In 0/1 Knapsack, each item can be chosen at most once.

2. Step 2: Understand item usage in Unbounded Knapsack

   In Unbounded Knapsack, items can be chosen unlimited times.

3. Final Answer:

   In Unbounded Knapsack, you can use unlimited copies of each item. -> Option A

4. Quick Check:

   Unbounded means unlimited usage [OK]

Hint: Remember: Unbounded means unlimited item usage [OK]

Common Mistakes:

• Confusing 0/1 and unbounded usage
• Thinking items must be sorted
• Assuming fractional items allowed

2. Which of the following is the correct syntax to initialize the DP array dp for an Unbounded Knapsack problem with capacity W in C?

easy

A. int dp[W+1] = {0};

B. int dp[W]; memset(dp, 0, sizeof(dp));

C. int dp[W+1]; for(int i=0; i<=W; i++) dp[i] = 0;

D. int dp[W+1]; dp = {0};

Solution

1. Step 1: Understand array declaration in C

   Array size must be W+1 to include capacity 0 to W.

2. Step 2: Initialize all elements to zero

   Using a for loop to set dp[i] = 0 is correct and safe.

3. Final Answer:

   int dp[W+1]; for(int i=0; i<=W; i++) dp[i] = 0; -> Option C

4. Quick Check:

   Proper array size and initialization [OK]

Hint: Use loop to initialize arrays in C safely [OK]

Common Mistakes:

• Using dp = {0} after declaration (invalid)
• Declaring dp with size W instead of W+1
• Using memset incorrectly on non-char arrays

3. What will be the output of the following C code snippet for Unbounded Knapsack with weights = {1, 3}, values = {10, 40}, and capacity = 5?

int weights[] = {1, 3};
int values[] = {10, 40};
int W = 5;
int dp[6] = {0};
for (int i = 0; i <= W; i++) {
  for (int j = 0; j < 2; j++) {
    if (weights[j] <= i) {
      int val = dp[i - weights[j]] + values[j];
      if (val > dp[i]) dp[i] = val;
    }
  }
}
printf("%d\n", dp[W]);

medium

A. 50

B. 80

C. 70

D. 60

Solution

1. Step 1: Calculate dp values step-by-step

   dp[0]=0; dp[1]=max(dp[0]+10)=10; dp[2]=max(dp[1]+10)=20; dp[3]=max(dp[0]+40, dp[2]+10)=max(40,30)=40; dp[4]=max(dp[1]+40, dp[3]+10)=max(50,50)=50; dp[5]=max(dp[2]+40, dp[4]+10)=max(60,60)=60.

2. Step 2: Final dp[5] value is 60

   This is the maximum value achievable with capacity 5.

3. Final Answer:

   60 -> Option D

4. Quick Check:

   dp[5] = 60 [OK]

Hint: Build dp array from 0 to W, update max value [OK]

Common Mistakes:

• Not considering multiple uses of items
• Mixing up indices in dp array
• Forgetting to check if weight fits capacity

4. Identify the error in the following Unbounded Knapsack code snippet and choose the correct fix:

int dp[W+1];
for (int i = 0; i < W; i++) {
  dp[i] = 0;
}
for (int i = 1; i <= W; i++) {
  for (int j = 0; j < n; j++) {
    if (weights[j] <= i) {
      dp[i] = max(dp[i], dp[i - weights[j]] + values[j]);
    }
  }
}

medium

A. Change first loop to for (int i = 0; i <= W; i++) to initialize dp correctly.

B. Change second loop to start from i = 0 instead of i = 1.

C. Remove the first loop; dp array is automatically zero-initialized.

D. Change max function to min function for correct calculation.

Solution

1. Step 1: Check dp array initialization loop

   The dp array size is W+1, but loop runs only till i < W, missing dp[W].

2. Step 2: Fix initialization loop range

   Change loop to i <= W to initialize all dp elements including dp[W].

3. Final Answer:

   Change first loop to for (int i = 0; i <= W; i++) to initialize dp correctly. -> Option A

4. Quick Check:

   Initialize full dp array size [OK]

Hint: Initialize dp array fully from 0 to W inclusive [OK]

Common Mistakes:

• Initializing dp array partially
• Starting dp loop from 0 instead of 1
• Using min instead of max function

5. Given items with weights = {2, 3, 5}, values = {50, 70, 100}, and capacity = 8, what is the maximum value achievable using the Unbounded Knapsack approach?

hard

A. 250

B. 200

C. 220

D. 270

Solution

1. Step 1: Calculate dp array values for capacity 0 to 8

   dp[0]=0; dp[1]=0 (no item fits); dp[2]=max(dp[0]+50)=50; dp[3]=max(dp[0]+70)=70; dp[4]=max(dp[2]+50, dp[1]+70)=max(100,0)=100; dp[5]=max(dp[0]+100, dp[3]+50, dp[2]+70)=max(100,120,120)=120; dp[6]=max(dp[4]+50, dp[3]+70, dp[1]+100)=max(150,140,0)=150; dp[7]=max(dp[5]+50, dp[4]+70, dp[2]+100)=max(170,170,150)=170; dp[8]=max(dp[6]+50, dp[5]+70, dp[3]+100)=max(200,190,170)=200.

2. Step 2: Re-check combinations for better value

   Try dp[8] as dp[3]+dp[5] or dp[2]+dp[6], but dp[8] = 200 is max from above. However, check dp[8] = dp[3]+dp[5] = 70 + 120 = 190, dp[8] = dp[5]+dp[3] = 120 + 70 = 190. Try dp[8] = dp[8-5]+100 = dp[3]+100 = 70 + 100 = 170. So 200 is max so far.

3. Step 3: Consider multiple 3s and 5s

   Try 3*3=9 > 8, so max is 200.

4. Final Answer:

   200 -> Option B

5. Quick Check:

   Maximum value dp[8] = 200 [OK]

Hint: Build dp array and check all item combinations for max value [OK]

Common Mistakes:

• Ignoring multiple item usage
• Not checking all item weights for each capacity
• Assuming only one item type per capacity