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 value. The knapsack can hold a limited weight, but the owner can use unlimited quantities of each item.Each item has a weight and a value. Your task is to find the maximum value that fits in the knapsack.

🎯 Goal: Build a program that calculates the maximum total value for the unbounded knapsack problem using dynamic programming.

📋 What You'll Learn

Create arrays for item weights and values

Create an integer variable for knapsack capacity

Use a dynamic programming array to store maximum values for each capacity

Implement the unbounded knapsack logic using loops

Print the maximum value that fits in the knapsack

💡 Why This Matters

🌍 Real World

This problem models situations like packing goods with unlimited supply to maximize profit or resource allocation with repeatable tasks.

💼 Career

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

1

Create item weights and values arrays

Create an integer array called weights with values 2, 3, 4, 5 and an integer array called values with values 3, 4, 5, 6.

DSA C#

# Create the weights and values arrays
// Your code here

Hint

Use array initialization syntax with curly braces and exact values.

2

Set knapsack capacity

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

DSA C#

int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
// Set the knapsack capacity
// Your code here

Hint

Use a simple integer variable assignment.

3

Implement unbounded knapsack logic

Create an integer array called dp of size capacity + 1 initialized with zeros. Use a for loop with variable w from 1 to capacity. Inside it, use a for loop with variable i from 0 to weights.Length - 1. If weights[i] <= w, update dp[w] to the maximum of dp[w] and dp[w - weights[i]] + values[i].

DSA C#

int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int capacity = 8;
// Implement the unbounded knapsack dynamic programming logic
// Your code here

Hint

Use nested loops and update dp array with maximum values.

4

Print the maximum value

Print the value of dp[capacity] using Console.WriteLine.

DSA C#

int[] weights = {2, 3, 4, 5};
int[] values = {3, 4, 5, 6};
int capacity = 8;
int[] dp = new int[capacity + 1];
for (int w = 1; w <= capacity; w++)
{
    for (int i = 0; i < weights.Length; i++)
    {
        if (weights[i] <= w)
        {
            dp[w] = Math.Max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
}
// Print the maximum value that fits in the knapsack
// Your code here

Hint

Use Console.WriteLine to print the final dp value at capacity index.

Practice

1. What is the main difference between the Unbounded Knapsack Problem and the 0/1 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 has a fixed number of items to choose from.

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 constraints

   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 A

4. Quick Check:

   Unlimited item usage = In Unbounded Knapsack, you can use unlimited copies of each item. [OK]

Hint: Remember: Unbounded means unlimited item copies allowed [OK]

Common Mistakes:

• Confusing Unbounded with fractional knapsack
• Thinking items can only be chosen once
• Assuming fixed number of items to pick

2. Which of the following C# code snippets correctly initializes the DP array for the Unbounded Knapsack problem of capacity W?

easy

A. int[] dp = new int[W + 1]; for (int i = 0; i <= W; i++) dp[i] = 0;

B. int[] dp = new int[W]; for (int i = 0; i < W; i++) dp[i] = -1;

C. int[] dp = new int[W + 1]; for (int i = 1; i <= W; i++) dp[i] = int.MaxValue;

D. int[] dp = new int[W + 1]; for (int i = 0; i <= W; i++) dp[i] = int.MinValue;

Solution

1. Step 1: Check array size and initialization

   The DP array size should be W+1 to cover capacities from 0 to W. Initializing with 0 is correct for max value problems.

2. Step 2: Validate initialization values

   Setting dp[i] = 0 means no value at start, which is correct. Negative or max int values are incorrect here.

3. Final Answer:

   int[] dp = new int[W + 1]; for (int i = 0; i <= W; i++) dp[i] = 0; -> Option A

4. Quick Check:

   DP array size W+1 and zero initialization = int[] dp = new int[W + 1]; for (int i = 0; i <= W; i++) dp[i] = 0; [OK]

Hint: DP array size = capacity + 1, initialize with zero for max value [OK]

Common Mistakes:

• Using wrong array size (W instead of W+1)
• Initializing with int.MaxValue or int.MinValue incorrectly
• Starting loop from 1 instead of 0

3. What is the output of the following C# code snippet for Unbounded Knapsack?

int W = 5;
int[] wt = {1, 3, 4};
int[] val = {10, 40, 50};
int[] dp = new int[W + 1];
for (int i = 0; i <= W; i++) {
    for (int j = 0; j < wt.Length; j++) {
        if (wt[j] <= i) {
            dp[i] = Math.Max(dp[i], dp[i - wt[j]] + val[j]);
        }
    }
}
Console.WriteLine(dp[W]);

medium

A. 120

B. 100

C. 60

D. 90

Solution

1. Step 1: Trace dp array updates for each capacity

   Calculate dp values: - dp[0]=0 - dp[1]=max(dp[1], dp[0]+10)=10 - dp[2]=max(dp[2], dp[1]+10)=20 - dp[3]=max(dp[3], dp[0]+40, dp[2]+10)=max(0,40,30)=40 - dp[4]=max(dp[4], dp[1]+40, dp[3]+10, dp[0]+50)=max(0,50,50,50)=50 - dp[5]=max(dp[5], dp[2]+40, dp[4]+10, dp[1]+50)=max(0,60,60,60)=60 But re-check dp[5] carefully: dp[5] = max(dp[5], dp[5-1]+10=dp[4]+10=50+10=60, dp[5-3]+40=dp[2]+40=20+40=60, dp[5-4]+50=dp[1]+50=10+50=60) = 60

2. Step 2: Recalculate carefully for maximum value

   Check if multiple items can be combined: - For dp[5], try dp[5-1]+10=dp[4]+10=50+10=60 - For dp[4], dp[4-4]+50=dp[0]+50=50 - For dp[3], dp[3-3]+40=dp[0]+40=40 - For dp[2], dp[2-1]+10=dp[1]+10=10+10=20 - For dp[1], dp[1-1]+10=dp[0]+10=10 So dp[5] = 60

3. Final Answer:

   60 -> Option C

4. Quick Check:

   Maximum value for capacity 5 = 60 [OK]

Hint: Trace dp array from 0 to W, update max values [OK]

Common Mistakes:

• Not considering multiple copies of items
• Incorrect dp array indexing
• Mixing up weights and values

4. Identify the bug in this Unbounded Knapsack C# code snippet:

int W = 7;
int[] wt = {1, 3, 4};
int[] val = {10, 40, 50};
int[] dp = new int[W + 1];
for (int i = 0; i < W; i++) {
    for (int j = 0; j < wt.Length; j++) {
        if (wt[j] <= i) {
            dp[i] = Math.Max(dp[i], dp[i - wt[j]] + val[j]);
        }
    }
}
Console.WriteLine(dp[W]);

medium

A. The inner loop should run from 1 to wt.Length.

B. The condition should be wt[j] < i instead of wt[j] <= i.

C. The dp array size should be W instead of W + 1.

D. The outer loop should run from 0 to W inclusive (i <= W).

Solution

1. Step 1: Check loop ranges for dp array access

   The dp array has size W+1, so valid indices are 0 to W inclusive. The outer loop runs only to i < W, missing dp[W].

2. Step 2: Identify impact of loop range

   Because dp[W] is not computed, the final answer dp[W] will be incorrect or default zero.

3. Final Answer:

   The outer loop should run from 0 to W inclusive (i <= W). -> Option D

4. Quick Check:

   Loop must cover full dp array size = The outer loop should run from 0 to W inclusive (i <= W). [OK]

Hint: Loop dp array fully from 0 to W inclusive [OK]

Common Mistakes:

• Using wrong loop bounds causing incomplete dp calculation
• Incorrect dp array size
• Wrong comparison operators in conditions

5. Given items with weights [2, 3, 5] and values [50, 70, 100], and a knapsack capacity of 8, what is the maximum value achievable using the Unbounded Knapsack approach?

hard

A. 270

B. 200

C. 250

D. 220

Solution

1. Step 1: Calculate dp array values for capacities 0 to 8

   Initialize dp[0]=0. - dp[1]=0 (no item fits) - dp[2]=max(dp[2], dp[0]+50)=50 - dp[3]=max(dp[3], dp[0]+70)=70 - dp[4]=max(dp[4], dp[2]+50=50+50=100, dp[1]+70=0+70=70)=100 - dp[5]=max(dp[5], dp[0]+100=100, dp[3]+50=70+50=120, dp[2]+70=50+70=120)=120 - dp[6]=max(dp[6], dp[4]+50=100+50=150, dp[3]+70=70+70=140, dp[1]+100=0+100=100)=150 - dp[7]=max(dp[7], dp[5]+50=120+50=170, dp[4]+70=100+70=170, dp[2]+100=50+100=150)=170 - dp[8]=max(dp[8], dp[6]+50=150+50=200, dp[5]+70=120+70=190, dp[3]+100=70+100=170)=200

2. Step 2: Check for better combinations

   Try combining items differently: - Using four 2-weight items: 4*50=200 - Using two 3-weight + one 2-weight: 2*70+50=190 - Using one 5-weight + one 3-weight: 100+70=170 - Using one 5-weight + one 3-weight + one 2-weight (over capacity) No better than 200 found, but check dp[8] carefully: - dp[8] = max(200, 190, 170) = 200

3. Step 3: Re-examine for missed combinations

   Try dp[8] = dp[3] + dp[5] = 70 + 120 = 190 (less than 200) Try dp[8] = dp[2] + dp[6] = 50 + 150 = 200 Try dp[8] = dp[0] + 100 (weight 5) + dp[3] (weight 3) = 100 + 70 = 170 Try dp[8] = dp[4] + dp[4] = 100 + 100 = 200 Try dp[8] = dp[7] + dp[1] = 170 + 0 = 170 Try dp[8] = dp[6] + dp[2] = 150 + 50 = 200 Try dp[8] = dp[5] + dp[3] = 120 + 70 = 190 Try dp[8] = dp[8-5] + 100 = dp[3] + 100 = 70 + 100 = 170 Try dp[8] = dp[8-3] + 70 = dp[5] + 70 = 120 + 70 = 190 Try dp[8] = dp[8-2] + 50 = dp[6] + 50 = 150 + 50 = 200 No combination exceeds 200, so 200 is max.

4. Final Answer:

   200 -> Option B

5. Quick Check:

   Max value for capacity 8 = 200 [OK]

Hint: Build dp array stepwise, combine items for max value [OK]

Common Mistakes:

• Ignoring multiple copies of items
• Not checking all item combinations
• Incorrect dp array updates