Unbounded Knapsack Problem in DSA C++ - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Unbounded Knapsack DP Table

What is the final maximum value returned by the unbounded knapsack function for the given input?

DSA C++

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

int main() {
    int val[] = {10, 40, 50, 70};
    int wt[] = {1, 3, 4, 5};
    int W = 8;
    int n = 4;
    int result = unboundedKnapsack(W, n, val, wt);
    std::cout << result << std::endl;
    return 0;
}

A 120

B 110

C 130

D 140

💡 Hint

Think about how many times you can take each item to maximize value without exceeding weight.

The maximum value for weight 8 is 120 by taking items with weights 3 and 5 (40 + 70) or multiple smaller items to maximize value.

🧠 Conceptual

intermediate

Understanding Unbounded Knapsack Item Choices

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

A Because the problem allows unlimited quantity of each item, so items can be repeated any number of times.

B Because the items have zero weight, so they can be added infinitely without affecting capacity.

C Because the knapsack capacity is infinite, so all items fit regardless of repetition.

D Because the problem only considers the first occurrence of each item and ignores duplicates.

💡 Hint

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

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

🔧 Debug

advanced

Identify the Bug in Unbounded Knapsack Implementation

What error will this code produce when run, and why?

DSA C++

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

A Runtime error: accessing dp[W] uninitialized

B Compilation error: missing semicolon

C Logic error: dp array not fully initialized, leading to garbage values

D No error, code runs correctly

💡 Hint

Check the initialization loop for dp array carefully.

The dp array is initialized only up to dp[W-1], leaving dp[W] uninitialized. This causes undefined behavior when dp[W] is accessed.

❓ Predict Output

advanced

Output of Recursive Unbounded Knapsack with Memoization

What is the output of the following code snippet?

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>

int unboundedKnapsackRec(int W, int n, int val[], int wt[], std::vector<int>& dp) {
    if (W == 0) return 0;
    if (dp[W] != -1) return dp[W];
    int maxVal = 0;
    for (int i = 0; i < n; i++) {
        if (wt[i] <= W) {
            maxVal = std::max(maxVal, val[i] + unboundedKnapsackRec(W - wt[i], n, val, wt, dp));
        }
    }
    dp[W] = maxVal;
    return maxVal;
}

int main() {
    int val[] = {5, 10, 15};
    int wt[] = {1, 3, 4};
    int W = 7;
    int n = 3;
    std::vector<int> dp(W+1, -1);
    std::cout << unboundedKnapsackRec(W, n, val, wt, dp) << std::endl;
    return 0;
}

A 30

B 25

C 40

D 35

💡 Hint

Try to find the combination of items that maximizes value for weight 7.

The best combination is two items of weight 3 (10 + 10 = 20) plus one item of weight 1 (5) for total 25, or one item of weight 4 (15) plus three items of weight 1 (5*3=15) total 30, or other combinations. The maximum is 35 by taking one item of weight 4 (15) plus one item of weight 3 (10) plus three items of weight 1 (5*3=15) total 40 is not possible because weight would exceed 7. The code returns 35 as max value.

🧠 Conceptual

expert

Time Complexity of Unbounded Knapsack DP Solution

What is the time complexity of the standard dynamic programming solution for the unbounded knapsack problem with capacity W and n items?

A O(n^W)

B O(n * W)

C O(n * W^2)

D O(W^n)

💡 Hint

Consider the nested loops in the DP solution.

The DP solution uses two nested loops: one over weights from 0 to W, and one over n items, resulting in O(n * W) time complexity.

Practice

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

easy

A. In Unbounded Knapsack, items cannot be repeated.

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

C. In 0/1 Knapsack, items can be used unlimited times.

D. There is no difference; both problems are the same.

Solution

1. Step 1: Understand item usage rules

   In 0/1 Knapsack, each item can be chosen at most once. In Unbounded Knapsack, items can be chosen unlimited times.

2. Step 2: Compare problem definitions

   Unbounded Knapsack allows multiple copies of the same item, unlike 0/1 Knapsack.

3. Final Answer:

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

4. Quick Check:

   Unbounded Knapsack = unlimited item usage [OK]

Hint: Remember: Unbounded means unlimited items allowed [OK]

Common Mistakes:

• Confusing 0/1 Knapsack with Unbounded Knapsack
• Thinking items cannot repeat in Unbounded Knapsack
• Assuming both problems have same constraints

2. Which of the following is the correct way to initialize the DP array for the Unbounded Knapsack problem in C++?

easy

A. int dp[W+1]; fill(dp, dp+W+1, 0);

B. int dp[W]; // uninitialized array

C. int dp[W+1]; fill(dp, dp+W+1, -1);

D. int dp[W+1] = {0}; // W is max weight

Solution

1. Step 1: Understand DP array role

   DP array stores max value for weights from 0 to W. It should start with 0 for no items chosen.

2. Step 2: Choose correct initialization

   Filling dp with 0 means no value at start, which is correct. int dp[W+1]; fill(dp, dp+W+1, 0); uses fill with 0 correctly.

3. Final Answer:

   int dp[W+1]; fill(dp, dp+W+1, 0); -> Option A

4. Quick Check:

   DP array initialized to 0 for all weights [OK]

Hint: Initialize DP with zeros for max value calculations [OK]

Common Mistakes:

• Leaving dp uninitialized causing garbage values
• Initializing dp with -1 which is incorrect here
• Using wrong array size causing out-of-bound errors

3. What will be the output of the following C++ code snippet for Unbounded Knapsack with weights = {2, 3}, values = {10, 15}, and max weight W = 5?

int weights[] = {2, 3};
int values[] = {10, 15};
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) {
      dp[i] = max(dp[i], dp[i - weights[j]] + values[j]);
    }
  }
}
std::cout << dp[W] << std::endl;

medium

A. 30

B. 35

C. 25

D. 40

Solution

1. Step 1: Trace dp array updates for weights 0 to 5

   Calculate dp[i]: dp[0]=0 For i=1: dp[1]=0 (no items fit) For i=2: dp[2]=max(dp[2], dp[0]+10)=10 For i=3: dp[3]=max(dp[3], dp[0]+15)=15 For i=4: dp[4]=max(dp[4], dp[2]+10=20, dp[1]+15=15)=20 For i=5: dp[5]=max(dp[5], dp[3]+10=25, dp[2]+15=25) so dp[5]=25

2. Step 2: Confirm final dp[5] value

   Maximum value for weight 5 is 25 by choosing items (3 + 2) or (2 + 3).

3. Final Answer:

   25 -> Option C

4. Quick Check:

   Max value at W=5 is 25 [OK]

Hint: Check dp updates for each weight carefully [OK]

Common Mistakes:

• Adding values incorrectly for dp updates
• Ignoring multiple item usage possibilities
• Mixing up indices in dp array

4. Identify the bug in this Unbounded Knapsack C++ code snippet:

int dp[W+1];
for (int i = 0; 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. dp array is not initialized before use.

B. Loop indices are incorrect.

C. Weights and values arrays are not declared.

D. The max function is used incorrectly.

Solution

1. Step 1: Check dp array initialization

   dp array is declared but not initialized, so it contains garbage values affecting max calculations.

2. Step 2: Importance of initializing dp

   dp should be initialized to 0 for all indices before the loops to ensure correct max value updates.

3. Final Answer:

   dp array is not initialized before use. -> Option A

4. Quick Check:

   Uninitialized dp causes wrong results [OK]

Hint: Always initialize dp array before loops [OK]

Common Mistakes:

• Forgetting to initialize dp array
• Assuming dp defaults to zero
• Ignoring garbage values in dp

5. Given items with weights = {1, 3, 4}, values = {15, 50, 60}, and max weight W = 7, what is the maximum value achievable using the Unbounded Knapsack approach?

hard

A. 105

B. 120

C. 150

D. 115

Solution

1. Step 1: Calculate dp values from 0 to 7

   dp[0]=0 For i=1: dp[1]=max(0, dp[0]+15)=15 For i=2: dp[2]=max(0, dp[1]+15)=30 For i=3: dp[3]=max(0, dp[0]+50, dp[2]+15)=50 For i=4: dp[4]=max(0, dp[1]+50, dp[0]+60, dp[3]+15)=65 For i=5: dp[5]=max(0, dp[2]+50, dp[1]+60, dp[4]+15)=80 For i=6: dp[6]=max(0, dp[3]+50, dp[2]+60, dp[5]+15)=100 For i=7: dp[7]=max(0, dp[4]+50=115, dp[3]+60=110, dp[6]+15=115)=115

2. Step 2: Confirm maximum value at W=7

   The maximum value achievable is 115 by combining items optimally.

3. Final Answer:

   115 -> Option D

4. Quick Check:

   Max value at W=7 is 115 [OK]

Hint: Build dp array stepwise for each weight [OK]

Common Mistakes:

• Not considering all item combinations
• Incorrect dp updates for each weight
• Mixing up weights and values indices