Unbounded Knapsack Problem in DSA C++

Mental Model

You want to fill a bag with items to get the most value, and you can use each item as many times as you want.

Analogy: Imagine you have a basket and many types of fruits. You want to fill the basket with fruits to get the most sweetness, and you can pick any fruit multiple times.

Capacity: 10
Items: [weight, value]
[2, 10] -> [3, 15] -> [5, 40]
Knapsack capacity -> 10

Knapsack state array (dp):
Index: 0 1 2 3 4 5 6 7 8 9 10
Value: 0 0 10 15 20 40 40 50 55 60 80

Dry Run Walkthrough

Input: items: [(2,10), (3,15), (5,40)], capacity: 10

Goal: Find the maximum value we can get by filling the knapsack of capacity 10 using unlimited items

Step 1: Start with capacity 0, max value is 0

dp: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Why: Base case: no capacity means no items can be added

Step 2: For capacity 2, try item (2,10): dp[2] = max(dp[2], dp[0] + 10) = 10

dp: [0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0]

Why: We can add item (2,10) once to fill capacity 2

Step 3: For capacity 3, try item (3,15): dp[3] = max(dp[3], dp[0] + 15) = 15

dp: [0, 0, 10, 15, 0, 0, 0, 0, 0, 0, 0]

Why: We can add item (3,15) once to fill capacity 3

Step 4: For capacity 4, try item (2,10): dp[4] = max(dp[4], dp[2] + 10) = 20

dp: [0, 0, 10, 15, 20, 0, 0, 0, 0, 0, 0]

Why: We can add item (2,10) twice to fill capacity 4

Step 5: For capacity 5, try item (5,40): dp[5] = max(dp[5], dp[0] + 40) = 40

dp: [0, 0, 10, 15, 20, 40, 0, 0, 0, 0, 0]

Why: Adding item (5,40) once gives max value for capacity 5

Step 6: For capacity 6, try item (2,10): dp[6] = max(dp[6], dp[4] + 10) = 30; try item (3,15): dp[6] = max(30, dp[3] + 15) = 30; try item (5,40): dp[6] = max(30, dp[1] + 40) = 40

dp: [0, 0, 10, 15, 20, 40, 40, 0, 0, 0, 0]

Why: Best value for capacity 6 is 40 by adding item (5,40) (capacity 1 unused)

Step 7: For capacity 7, try item (2,10): dp[7] = max(dp[7], dp[5] + 10) = 50; try item (3,15): dp[7] = max(50, dp[4] + 15) = 50; try item (5,40): dp[7] = max(50, dp[2] + 40) = 50

dp: [0, 0, 10, 15, 20, 40, 40, 50, 0, 0, 0]

Why: Best value for capacity 7 is 50 by adding item (5,40) plus item (2,10)

Step 8: For capacity 8, try item (2,10): dp[8] = max(dp[8], dp[6] + 10) = 50; try item (3,15): dp[8] = max(50, dp[5] + 15) = 55; try item (5,40): dp[8] = max(55, dp[3] + 40) = 55

dp: [0, 0, 10, 15, 20, 40, 40, 50, 55, 0, 0]

Why: Best value for capacity 8 is 55 by adding item (3,15) plus item (5,40)

Step 9: For capacity 9, try item (2,10): dp[9] = max(dp[9], dp[7] + 10) = 60; try item (3,15): dp[9] = max(60, dp[6] + 15) = 60; try item (5,40): dp[9] = max(60, dp[4] + 40) = 60

dp: [0, 0, 10, 15, 20, 40, 40, 50, 55, 60, 0]

Why: Best value for capacity 9 is 60 by adding item (2,10) plus item (5,40)

Step 10: For capacity 10, try item (2,10): dp[10] = max(dp[10], dp[8] + 10) = 65; try item (3,15): dp[10] = max(65, dp[7] + 15) = 65; try item (5,40): dp[10] = max(65, dp[5] + 40) = 80

dp: [0, 0, 10, 15, 20, 40, 40, 50, 55, 60, 80]

Why: Adding two items (5,40) gives max value 80 for capacity 10

Result:

dp array: [0, 0, 10, 15, 20, 40, 40, 50, 55, 60, 80]
Maximum value for capacity 10 is 80

Annotated Code

DSA C++

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

using namespace std;

// Item structure with weight and value
struct Item {
    int weight;
    int value;
};

// Function to solve unbounded knapsack
int unboundedKnapsack(int capacity, const vector<Item>& items) {
    vector<int> dp(capacity + 1, 0); // dp[i] = max value for capacity i

    for (int i = 1; i <= capacity; i++) {
        for (const auto& item : items) {
            if (item.weight <= i) {
                dp[i] = max(dp[i], dp[i - item.weight] + item.value); // update max value
            }
        }
    }
    return dp[capacity];
}

int main() {
    vector<Item> items = {{2, 10}, {3, 15}, {5, 40}};
    int capacity = 10;
    int maxValue = unboundedKnapsack(capacity, items);
    cout << "Maximum value for capacity " << capacity << " is " << maxValue << endl;
    return 0;
}

for (int i = 1; i <= capacity; i++) {

iterate over all capacities from 1 to max capacity

for (const auto& item : items) {

check each item for current capacity

if (item.weight <= i) {

only consider item if it fits in current capacity

dp[i] = max(dp[i], dp[i - item.weight] + item.value);

update dp[i] with max value by including current item

Output

Maximum value for capacity 10 is 80

Complexity Analysis

Time: O(n * capacity) because we check each item for every capacity from 1 to capacity

Space: O(capacity) because we use a dp array of size capacity + 1

vs Alternative: Compared to the 0/1 knapsack which only allows one use per item, unbounded knapsack allows repeated use, but the time complexity remains similar with dynamic programming.

Edge Cases

capacity = 0

Returns 0 because no items can be added

DSA C++

for (int i = 1; i <= capacity; i++) {

items list empty

Returns 0 because no items to add

DSA C++

for (const auto& item : items) {

item weight greater than capacity

Item is skipped because it cannot fit

DSA C++

if (item.weight <= i) {

When to Use This Pattern

When you see a problem asking for maximum value with unlimited item usage and capacity constraints, reach for the unbounded knapsack pattern because it allows repeated item selection.

Common Mistakes

Mistake: Using 0/1 knapsack logic which disallows repeated items
Fix: Allow repeated use by checking dp[i - item.weight] instead of dp[i - 1]

Mistake: Not initializing dp array with zeros
Fix: Initialize dp array with zeros to represent base case of zero capacity

Summary

Finds the maximum value achievable with unlimited items within a capacity limit.

Use when items can be chosen multiple times to fill a capacity for max value.

The key is to build solutions for all capacities by reusing previous results with repeated items.

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