Unbounded Knapsack Problem in DSA C - Build from Scratch

Unbounded Knapsack Problem

📖 Scenario: You are helping a shop owner who wants to fill a knapsack with items to maximize profit. The shop owner can take unlimited quantities of each item.

🎯 Goal: Build a program that calculates the maximum profit possible with a given knapsack capacity and unlimited items.

📋 What You'll Learn

Create arrays for item weights and profits with given values

Create an integer variable for knapsack capacity

Implement the unbounded knapsack logic using dynamic programming

Print the maximum profit achievable

💡 Why This Matters

🌍 Real World

This problem models situations where you can use unlimited quantities of resources to maximize profit, like packing goods or cutting raw materials.

💼 Career

Understanding dynamic programming and knapsack problems is important for software engineers working on optimization, resource allocation, and algorithm design.

1

Create item weights and profits arrays

Create two integer arrays called weights and profits with these exact values: weights = {1, 3, 4, 5} and profits = {10, 40, 50, 70}.

DSA C

# Your code here

Hint

Use array syntax to create weights and profits with the exact values.

2

Add knapsack capacity variable

Add an integer variable called capacity and set it to 8.

DSA C

#include 

int main() {
    int weights[] = {1, 3, 4, 5};
    int profits[] = {10, 40, 50, 70};
    // Your code here
    return 0;
}

Hint

Declare an integer variable capacity and assign it the value 8.

3

Implement unbounded knapsack logic

Implement the unbounded knapsack logic using a for loop with variable w from 1 to capacity, and inside it another for loop with variable i from 0 to 3. Use an integer array dp of size capacity + 1 initialized to zero. Update dp[w] to the maximum profit possible by including items multiple times.

DSA C

#include 

int main() {
    int weights[] = {1, 3, 4, 5};
    int profits[] = {10, 40, 50, 70};
    int capacity = 8;
    int dp[capacity + 1];
    // Your code here
    return 0;
}

Hint

Use dynamic programming array dp to store max profit for each weight. Update dp[w] inside nested loops.

4

Print the maximum profit

Print the maximum profit stored in dp[capacity] using printf.

DSA C

#include 

int main() {
    int weights[] = {1, 3, 4, 5};
    int profits[] = {10, 40, 50, 70};
    int capacity = 8;
    int dp[capacity + 1];

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

    // Print the maximum profit
    // Your code here
    return 0;
}

Hint

Use printf("%d\n", dp[capacity]); to print the result.

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