Unbounded Knapsack Problem in DSA C

Mental Model

You can pick items multiple times to fill a bag with maximum value without exceeding its weight limit.

Analogy: Imagine you have a backpack and unlimited candies of different weights and values. You want to fill your backpack to get the most tasty candies without breaking it.

Capacity: 5
Items: [weight: 1, value: 10], [weight: 3, value: 40], [weight: 4, value: 50]

Bag capacity -> 5
Items ->
[1,10] -> [3,40] -> [4,50]

Goal: Maximize value by choosing items any number of times.

Dry Run Walkthrough

Input: items: weights = [1, 3, 4], values = [10, 40, 50], capacity = 5

Goal: Find the maximum value we can get by picking items any number of times without exceeding capacity 5

Step 1: Initialize dp array with 0 for capacity 0 to 5

dp = [0, 0, 0, 0, 0, 0]

Why: Start with no items chosen, so max value is 0 for all capacities

Step 2: For capacity 1, check items: weight 1 fits, update dp[1] = max(dp[1], dp[1-1] + 10) = 10

dp = [0, 10, 0, 0, 0, 0]

Why: Choosing item with weight 1 and value 10 fits capacity 1

Step 3: For capacity 2, item weight 1 fits: dp[2] = max(dp[2], dp[2-1] + 10) = 20

dp = [0, 10, 20, 0, 0, 0]

Why: We can pick item with weight 1 twice to fill capacity 2

Step 4: For capacity 3, check items: weight 1 fits dp[3] = max(0, dp[2]+10)=30; weight 3 fits dp[3] = max(30, dp[0]+40)=40

dp = [0, 10, 20, 40, 0, 0]

Why: Choosing item with weight 3 and value 40 is better than three times item 1

Step 5: For capacity 4, check items: weight 1 fits dp[4] = max(0, dp[3]+10)=50; weight 3 fits dp[4] = max(50, dp[1]+40)=50; weight 4 fits dp[4] = max(50, dp[0]+50)=50

dp = [0, 10, 20, 40, 50, 0]

Why: Picking item with weight 4 and value 50 or item 1 + item 3 both give max 50

Step 6: For capacity 5, check items: weight 1 fits dp[5] = max(0, dp[4]+10)=60; weight 3 fits dp[5] = max(60, dp[2]+40)=60; weight 4 fits dp[5] = max(60, dp[1]+50)=60

dp = [0, 10, 20, 40, 50, 60]

Why: Best is picking item 1 five times or item 3 + item 1 or item 4 + item 1

Result:

dp = [0, 10, 20, 40, 50, 60]
Maximum value for capacity 5 is 60

Annotated Code

DSA C

#include <stdio.h>

int unboundedKnapsack(int capacity, int weights[], int values[], int n) {
    int dp[capacity + 1];
    for (int i = 0; i <= capacity; i++) {
        dp[i] = 0; // initialize dp array
    }

    for (int w = 1; w <= capacity; w++) {
        for (int i = 0; i < n; i++) {
            if (weights[i] <= w) {
                int val = dp[w - weights[i]] + values[i];
                if (val > dp[w]) {
                    dp[w] = val; // update max value for capacity w
                }
            }
        }
    }
    return dp[capacity];
}

int main() {
    int weights[] = {1, 3, 4};
    int values[] = {10, 40, 50};
    int capacity = 5;
    int n = sizeof(weights) / sizeof(weights[0]);

    int maxValue = unboundedKnapsack(capacity, weights, values, n);
    printf("Maximum value for capacity %d is %d\n", capacity, maxValue);
    return 0;
}

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

initialize dp array with 0 for all capacities

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

iterate over all capacities from 1 to capacity

for (int i = 0; i < n; i++) {

check each item for current capacity

if (weights[i] <= w) {

item fits in current capacity

int val = dp[w - weights[i]] + values[i];

calculate value if we include this item

if (val > dp[w]) { dp[w] = val; }

update dp[w] if new value is better

return dp[capacity];

return max value for full capacity

Output

Maximum value for capacity 5 is 60

Complexity Analysis

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

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

vs Alternative: Compared to recursive exponential approach, this dynamic programming solution is much faster and uses less time by storing intermediate results.

Edge Cases

capacity = 0

returns 0 because no items can be chosen

DSA C

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

items with weight greater than capacity

those items are ignored because they don't fit

DSA C

if (weights[i] <= w) {

single item with weight 1

dp fills with multiples of that item's value

DSA C

int val = dp[w - weights[i]] + values[i];

When to Use This Pattern

When you can use items unlimited times to maximize value within a weight limit, reach for the Unbounded Knapsack pattern because it handles repeated item choices efficiently.

Common Mistakes

Mistake: Using 2D dp array like 0/1 knapsack and not allowing repeated items
Fix: Use 1D dp array and update dp[w] considering dp[w - weight[i]] to allow multiple picks

Summary

Finds max value by picking items unlimited times without exceeding capacity

Use when items can be chosen multiple times and you want max total value within weight limit

Key insight: dp[w] depends on dp[w - weight[i]] allowing repeated item inclusion

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