Unbounded Knapsack Problem in DSA C - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Unbounded Knapsack Recursive Call

What is the output of the following C code snippet that calculates the maximum value for an unbounded knapsack problem with given weights and values?

DSA C

#include <stdio.h>

int max(int a, int b) { return (a > b) ? a : b; }

int unboundedKnapsack(int W, int wt[], int val[], int n) {
    if (n == 0 || W == 0)
        return 0;
    if (wt[n-1] <= W) {
        return max(val[n-1] + unboundedKnapsack(W - wt[n-1], wt, val, n),
                   unboundedKnapsack(W, wt, val, n-1));
    } else {
        return unboundedKnapsack(W, wt, val, n-1);
    }
}

int main() {
    int val[] = {10, 40, 50, 70};
    int wt[] = {1, 3, 4, 5};
    int W = 8;
    int n = sizeof(val)/sizeof(val[0]);
    printf("%d", unboundedKnapsack(W, wt, val, n));
    return 0;
}

A 120

B 110

C 130

D 140

💡 Hint

Think about how many times you can take each item given the weight limit.

The maximum value is 110 by taking the items with weights 5 and 3.

🧠 Conceptual

intermediate

Understanding Unbounded Knapsack Item Selection

In the unbounded knapsack problem, why can items be chosen multiple times compared to the 0/1 knapsack problem?

A Because the problem allows infinite copies of each item to maximize value within weight limit.

B Because the items are divisible into fractions to fill the knapsack.

C Because the knapsack capacity is unlimited.

D Because items must be chosen exactly once.

💡 Hint

Think about the difference in constraints between 0/1 and unbounded knapsack.

Unbounded knapsack allows unlimited copies of each item, unlike 0/1 knapsack where each item can be chosen only once.

❓ Predict Output

advanced

Output of Bottom-Up DP Table for Unbounded Knapsack

What is the printed DP table after running the bottom-up unbounded knapsack code for weights {1, 3, 4} and values {15, 50, 60} with capacity 5?

DSA C

#include <stdio.h>

int max(int a, int b) { return (a > b) ? a : b; }

int main() {
    int val[] = {15, 50, 60};
    int wt[] = {1, 3, 4};
    int W = 5;
    int n = 3;
    int dp[6] = {0};

    for (int w = 1; w <= W; w++) {
        for (int i = 0; i < n; i++) {
            if (wt[i] <= w) {
                dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
            }
        }
    }

    for (int i = 0; i <= W; i++) {
        printf("%d ", dp[i]);
    }
    return 0;
}

A [0, 15, 30, 50, 75, 90]

B [0, 15, 15, 50, 60, 60]

C [0, 15, 30, 45, 60, 75]

D [0, 15, 30, 50, 65, 80]

💡 Hint

Check how dp[w] updates by considering all items for each weight w.

The dp array stores max value for each weight. For weight 5, best is 80 by taking item with weight 3 once and weight 1 twice (50 + 15*2 = 80).

🔧 Debug

advanced

Identify the Bug in Unbounded Knapsack Recursive Code

What error does the following code produce when compiled and run?

DSA C

#include <stdio.h>

int max(int a, int b) { return (a > b) ? a : b; }

int unboundedKnapsack(int W, int wt[], int val[], int n) {
    if (n == 0 || W == 0)
        return 0;
    if (wt[n-1] <= W) {
        return max(val[n-1] + unboundedKnapsack(W - wt[n-1], wt, val, n-1),
                   unboundedKnapsack(W, wt, val, n-1));
    } else {
        return unboundedKnapsack(W, wt, val, n-1);
    }
}

int main() {
    int val[] = {10, 40, 50};
    int wt[] = {1, 3, 4};
    int W = 6;
    int n = 3;
    printf("%d", unboundedKnapsack(W, wt, val, n));
    return 0;
}

A The code returns incorrect maximum value because it reduces n when including the item, disallowing multiple picks.

B The code causes infinite recursion and stack overflow.

C The code runs correctly and returns the maximum value 90.

D The code causes a segmentation fault due to invalid array access.

💡 Hint

Check how the recursive call changes the item count when including an item.

In unbounded knapsack, when including an item, n should not decrease because items can be chosen multiple times. Here, n-1 is passed, so items are only chosen once.

🚀 Application

expert

Maximum Value and Item Counts in Unbounded Knapsack

Given weights = {2, 3, 5}, values = {50, 70, 100}, and capacity = 8, what is the maximum value and how many times is the item with weight 3 chosen in the optimal solution?

A Maximum value = 220, item with weight 3 chosen 2 times

B Maximum value = 170, item with weight 3 chosen 2 times

C Maximum value = 200, item with weight 3 chosen 0 times

D Maximum value = 150, item with weight 3 chosen 0 times

💡 Hint

Try combinations of items to fill capacity 8 maximizing value, count how many times weight 3 item is used.

Optimal is four items of weight 2 (50*4=200), item with weight 3 chosen 0 times. Two weight 3 + one weight 2 = 190 < 200. One weight 5 + one weight 3 = 170 < 200.

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