Unbounded Knapsack Problem in DSA C++ - Build from Scratch

Unbounded Knapsack Problem

📖 Scenario: You are packing a bag for a hiking trip. You have different items, each with a weight and a value. You can take any number of each item (unlimited quantity). Your goal is to maximize the total value without exceeding the bag's weight limit.

🎯 Goal: Build a program that calculates the maximum value you can carry in your bag using the unbounded knapsack approach.

📋 What You'll Learn

Create arrays for item weights and values

Set the maximum weight capacity of the bag

Use dynamic programming to find the maximum value for the given capacity

Print the maximum value achievable

💡 Why This Matters

🌍 Real World

This problem models packing problems where you can take unlimited quantities of items, such as filling a backpack with supplies or cutting raw materials.

💼 Career

Understanding unbounded knapsack helps in optimization tasks, resource allocation, and dynamic programming skills useful in software engineering and data science roles.

1

Create item weights and values arrays

Create two arrays called weights and values with these exact elements: weights = {2, 3, 4} and values = {40, 50, 100}.

DSA C++

// Your code here

Hint

Use C++ array syntax to create weights and values with the given numbers.

2

Set the maximum weight capacity

Add an integer variable called maxWeight and set it to 10.

DSA C++

#include 
using namespace std;

int main() {
    int weights[] = {2, 3, 4};
    int values[] = {40, 50, 100};
    
    // Set the maximum weight capacity
    // Your code here
    
    return 0;
}

Hint

Declare int maxWeight = 10; inside main().

3

Calculate maximum value using unbounded knapsack

Create an integer array dp of size maxWeight + 1 initialized with zeros. Use a for loop with variable w from 1 to maxWeight. Inside it, use another for loop with variable i from 0 to 2 to check if weights[i] is less than or equal to w. If yes, update dp[w] to the maximum of its current value and values[i] + dp[w - weights[i]].

DSA C++

#include 
using namespace std;

int main() {
    int weights[] = {2, 3, 4};
    int values[] = {40, 50, 100};
    int maxWeight = 10;
    
    // Create dp array and fill it using unbounded knapsack logic
    // Your code here
    
    return 0;
}

Hint

Use two nested loops: outer loop for w from 1 to maxWeight, inner loop for i from 0 to 2. Update dp[w] with the best value.

4

Print the maximum value achievable

Print the value of dp[maxWeight] using cout.

DSA C++

#include 
using namespace std;

int main() {
    int weights[] = {2, 3, 4};
    int values[] = {40, 50, 100};
    int maxWeight = 10;
    int dp[maxWeight + 1] = {0};

    for (int w = 1; w  dp[w]) {
                    dp[w] = val;
                }
            }
        }
    }

    // Print the maximum value achievable
    // Your code here

    return 0;
}

Hint

Use cout << dp[maxWeight] << endl; to print the result.

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