Unbounded Knapsack Problem in DSA C++ - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the DP array with zeros.

DSA C++

int dp[n+1] = {0};
for (int i = 0; i <= n; i++) {
    dp[i] = [1];
}

Drag options to blanks, or click blank then click option'

A-1

B1

C0

Di

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing dp[i] with 1 or -1 instead of 0.

Using the loop variable i as the value.

The DP array should be initialized with 0 because initially, the maximum value for any capacity is zero.

2fill in blank

medium

Complete the code to iterate over all capacities from 1 to n.

DSA C++

for (int w = 1; w <= [1]; w++) {
    // logic here
}

Drag options to blanks, or click blank then click option'

An

Bcapacity

Cweight

DmaxWeight

Attempts:

3 left

💡 Hint

Common Mistakes

Using an undefined variable like capacity or weight.

Looping beyond the capacity n.

The loop should run from 1 to n, where n is the total capacity of the knapsack.

3fill in blank

hard

Fix the error in the condition to check if the current item's weight fits in the current capacity.

DSA C++

if (wt[i] [1] w) {
    dp[w] = max(dp[w], dp[w - wt[i]] + val[i]);
}

Drag options to blanks, or click blank then click option'

A>

B<=

C==

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using > or == instead of <=.

Using < which excludes equal weight cases.

We check if the item's weight is less than or equal to the current capacity to decide if it can be included.

4fill in blank

hard

Fill both blanks to update the dp array correctly inside the nested loops.

DSA C++

dp[w] = max(dp[w], dp[w [1] wt[i]] [2] val[i]);

Drag options to blanks, or click blank then click option'

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using + instead of - for the index calculation.

Using * or / instead of + for adding the item's value.

We subtract the item's weight from w to find the remaining capacity and add the item's value to the dp value of that remaining capacity.

5fill in blank

hard

Fill all three blanks to complete the nested loops for the unbounded knapsack solution.

DSA C++

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

Drag options to blanks, or click blank then click option'

A<

B<=

C>

D>=

Attempts:

3 left

💡 Hint

Common Mistakes

Using <= in the outer loop causing out of bounds.

Using < in the inner loop missing the last capacity.

Using > or >= incorrectly in the condition.

The outer loop runs from 0 to n-1 (i < n). The inner loop runs from 1 to capacity (w <= capacity). The condition checks if the item's weight is less than or equal to w.

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