Unbounded Knapsack Problem in DSA C#

Mental Model

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

Analogy: Imagine you have a backpack and unlimited candies of different sizes and tastiness. You want to fill your backpack to get the tastiest mix, and you can pick any candy multiple times.

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

Backpack capacity -> [0][1][2][3][4][5]
Values stored -> [0][ ][ ][ ][ ][ ]

Dry Run Walkthrough

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

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

Step 1: Start with capacity 0, max value is 0 because no space

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

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

Step 2: Check capacity 1: try item weight 1 (value 10), fits, update dp[1] = 10

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

Why: At capacity 1, only item 1 fits, so max value is 10

Step 3: Check capacity 2: try item 1 (weight 1), dp[2] = max(dp[2], dp[1] + 10) = 20

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

Why: We can use item 1 twice to fill capacity 2 for value 20

Step 4: Check capacity 3: try item 1 (dp[3] = dp[2] + 10 = 30), try item 2 (weight 3, value 40), dp[3] = max(30, 40) = 40

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

Why: Item 2 fits exactly and gives better value than three item 1s

Step 5: Check capacity 4: try item 1 (dp[4] = dp[3] + 10 = 50), item 2 (dp[4] = dp[1] + 40 = 50), item 3 (weight 4, value 50), dp[4] = 50

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

Why: Multiple ways to get value 50 at capacity 4

Step 6: Check capacity 5: try item 1 (dp[5] = dp[4] + 10 = 60), item 2 (dp[5] = dp[2] + 40 = 60), item 3 (dp[5] = dp[1] + 50 = 60), dp[5] = 60

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

Why: Best value at capacity 5 is 60 using combinations of items

Result:

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

Annotated Code

DSA C#

using System;

class UnboundedKnapsack {
    public static int Solve(int[] weights, int[] values, int capacity) {
        int n = weights.Length;
        int[] dp = new int[capacity + 1];

        for (int c = 0; c <= capacity; c++) {
            for (int i = 0; i < n; i++) {
                if (weights[i] <= c) {
                    dp[c] = Math.Max(dp[c], dp[c - weights[i]] + values[i]);
                }
            }
        }

        return dp[capacity];
    }

    static void Main() {
        int[] weights = {1, 3, 4};
        int[] values = {10, 40, 50};
        int capacity = 5;
        int maxValue = Solve(weights, values, capacity);
        Console.WriteLine(maxValue);
    }
}

for (int c = 0; c <= capacity; c++) {

iterate over all capacities from 0 to max

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

try each item for current capacity

if (weights[i] <= c) {

check if item fits in current capacity

dp[c] = Math.Max(dp[c], dp[c - weights[i]] + values[i]);

update max value by including current item multiple times

Output

60

Complexity Analysis

Time: O(n * capacity) because we check all items for each capacity up to the max

Space: O(capacity) because we store max values for each capacity in a single array

vs Alternative: Compared to 0/1 knapsack which uses O(n * capacity) but only allows one use per item, unbounded knapsack allows repeated use and uses a similar DP approach

Edge Cases

capacity = 0

max value is 0 because no items can fit

DSA C#

for (int c = 0; c <= capacity; c++) {

items with weight greater than capacity

those items are ignored because they never fit

DSA C#

if (weights[i] <= c) {

empty items array

max value is 0 because no items to choose

DSA C#

int n = weights.Length;

When to Use This Pattern

When you can use items unlimited times to maximize value within a capacity, reach for the unbounded knapsack pattern because it handles repeated item use efficiently.

Common Mistakes

Mistake: Using 0/1 knapsack logic that disallows repeated items
Fix: Allow repeated use by checking dp[c - weights[i]] + values[i] for all capacities

Mistake: Not initializing dp array properly or starting capacity from 1
Fix: Start from capacity 0 to handle base case correctly

Summary

Finds the max value achievable with unlimited item use within a capacity.

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

The key is to build solutions from smaller capacities allowing 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, 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