Unbounded Knapsack Problem in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the Unbounded Knapsack Problem?

It is a problem where you can take unlimited quantities of each item to maximize the total value without exceeding the knapsack's capacity.

beginner

How does the Unbounded Knapsack Problem differ from the 0/1 Knapsack Problem?

In Unbounded Knapsack, you can use each item multiple times, while in 0/1 Knapsack, each item can be used at most once.

intermediate

What is the main idea behind the dynamic programming solution for Unbounded Knapsack?

Build a table where each entry represents the maximum value for a given capacity, considering all items and allowing repeated use of items.

intermediate

What is the time complexity of the Unbounded Knapsack dynamic programming solution?

It is O(n * W), where n is the number of items and W is the knapsack capacity.

intermediate

In the Unbounded Knapsack problem, why can we consider the same item multiple times in the DP table?

Because the problem allows unlimited copies of each item, so after including an item, we can still include it again if capacity allows.

In the Unbounded Knapsack problem, what does 'unbounded' mean?

A You cannot use any item

B You can use unlimited copies of each item

C You can use each item only once

D You must use all items

Unbounded means unlimited copies of each item can be used.

What is the main difference in the DP approach between 0/1 Knapsack and Unbounded Knapsack?

A Unbounded allows reusing items in the same capacity calculation

B 0/1 Knapsack allows unlimited items

C Unbounded does not use DP

D 0/1 Knapsack uses recursion only

Unbounded Knapsack allows reusing items multiple times in the DP table.

What does the DP array represent in the Unbounded Knapsack solution?

A Total number of items

B Number of items used

C Minimum weight possible

D Maximum value achievable for each capacity

The DP array stores the maximum value achievable for each capacity.

If the knapsack capacity is 5 and item weights are 1 and 3 with values 10 and 40, what is the maximum value in Unbounded Knapsack?

A 60

B 40

C 30

D 10

One item of weight 3 (value 40) and two items of weight 1 (value 10 each, total 20) give a total value of 60.

What is the base case value for DP array at capacity 0 in Unbounded Knapsack?

A 1

B Infinity

C 0

D -1

At capacity 0, maximum value is 0 because no items can be taken.

Explain how dynamic programming solves the Unbounded Knapsack problem step-by-step.

Think about building solutions from smaller capacities to larger.

Describe the difference between 0/1 Knapsack and Unbounded Knapsack and how it affects the solution approach.

Focus on how item repetition changes the DP logic.

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