Unbounded Knapsack Problem in DSA C - Time & Space Complexity

Time Complexity: Unbounded Knapsack Problem

O(n * W)

Understanding Time Complexity

We want to understand how the time needed to solve the Unbounded Knapsack problem changes as the input size grows.

Specifically, how the number of items and the knapsack capacity affect the work done.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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] = dp[i] > dp[i - wt[j]] + val[j] ? dp[i] : dp[i - wt[j]] + val[j];
            }
        }
    }
    return dp[W];
}
    

This code finds the maximum value for a knapsack of capacity W using unlimited copies of n items.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops: outer loop runs from 0 to W, inner loop runs over n items.
• How many times: Outer loop runs W+1 times, inner loop runs n times for each outer iteration.

How Execution Grows With Input

As the knapsack capacity W grows, the outer loop runs more times. For each capacity, we check all n items.

Input Size (W)	Approx. Operations (n * W)
10	10 * n
100	100 * n
1000	1000 * n

Pattern observation: The work grows linearly with both the knapsack capacity and the number of items.

Final Time Complexity

Time Complexity: O(n * W)

This means the time needed grows proportionally with the number of items and the knapsack capacity.

Common Mistake

[X] Wrong: "The time depends only on the number of items, not the capacity."

[OK] Correct: The capacity W controls how many times the outer loop runs, so it directly affects the total work.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming solves problems efficiently by breaking them into smaller parts.

Self-Check

"What if we used recursion with memoization instead of this bottom-up approach? How would the time complexity change?"

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