Unbounded Knapsack Problem in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Unbounded Knapsack Recursive Call

What is the output of the following C# code that solves the Unbounded Knapsack problem recursively for given weights and values?

DSA C#

using System;

class Program {
    static int UnboundedKnapsack(int W, int[] wt, int[] val, int n) {
        if (n == 0 || W == 0) return 0;
        if (wt[n - 1] <= W) {
            return Math.Max(val[n - 1] + UnboundedKnapsack(W - wt[n - 1], wt, val, n), UnboundedKnapsack(W, wt, val, n - 1));
        } else {
            return UnboundedKnapsack(W, wt, val, n - 1);
        }
    }

    static void Main() {
        int[] val = {10, 40, 50, 70};
        int[] wt = {1, 3, 4, 5};
        int W = 8;
        int n = val.Length;
        Console.WriteLine(UnboundedKnapsack(W, wt, val, n));
    }
}

A 130

B 120

C 110

D 140

💡 Hint

Think about how many times you can pick items given the weight limit and the option to reuse items unlimited times.

The maximum value for weight 8 is 110 by choosing items with weights 3 and 5 or multiple smaller items. The recursive function explores all combinations allowing unlimited picks.

❓ Predict Output

intermediate

Output of Bottom-Up DP for Unbounded Knapsack

What is the output of this bottom-up dynamic programming solution for the Unbounded Knapsack problem?

DSA C#

using System;

class Program {
    static int UnboundedKnapsack(int W, int[] wt, int[] val, int n) {
        int[] dp = new int[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] = Math.Max(dp[i], dp[i - wt[j]] + val[j]);
                }
            }
        }
        return dp[W];
    }

    static void Main() {
        int[] val = {10, 40, 50, 70};
        int[] wt = {1, 3, 4, 5};
        int W = 8;
        int n = val.Length;
        Console.WriteLine(UnboundedKnapsack(W, wt, val, n));
    }
}

A 110

B 120

C 100

D 90

💡 Hint

The dp array stores max values for all weights up to W, considering unlimited picks.

The bottom-up DP approach calculates the maximum value for each weight from 0 to W. The final dp[W] is 110 for the given inputs.

🔧 Debug

advanced

Identify the Runtime Error in Unbounded Knapsack Code

Which option will cause a runtime error when running this Unbounded Knapsack code snippet?

DSA C#

int UnboundedKnapsack(int W, int[] wt, int[] val, int n) {
    int[] dp = new int[W + 1];
    for (int i = 1; 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] = Math.Max(dp[i], dp[i - wt[j]] + val[j]);
            }
        }
    }
    return dp[W];
}

A No runtime error, code runs fine

B NullReferenceException due to uninitialized array

C IndexOutOfRangeException due to dp array access

D DivideByZeroException due to division by zero

💡 Hint

Check array indices carefully and initialization.

The code initializes dp array correctly and accesses indices within bounds. No runtime error occurs.

🧠 Conceptual

advanced

Understanding Time Complexity of Unbounded Knapsack DP

What is the time complexity of the bottom-up dynamic programming solution for the Unbounded Knapsack problem with capacity W and n items?

A O(n + W)

B O(n^2 * W)

C O(W^2)

D O(n * W)

💡 Hint

Consider the nested loops over weights and items.

The outer loop runs W times and the inner loop runs n times, resulting in O(n * W) complexity.

🚀 Application

expert

Maximum Value and Items Chosen in Unbounded Knapsack

Given the bottom-up DP solution for Unbounded Knapsack, which option correctly outputs the maximum value and the count of items chosen for capacity 8 with values {10, 40, 50, 70} and weights {1, 3, 4, 5}?

DSA C#

using System;
using System.Collections.Generic;

class Program {
    static (int maxValue, Dictionary<int,int> itemCount) UnboundedKnapsack(int W, int[] wt, int[] val, int n) {
        int[] dp = new int[W + 1];
        int[] itemChoice = new int[W + 1];
        for (int i = 0; i <= W; i++) {
            dp[i] = 0;
            itemChoice[i] = -1;
        }
        for (int i = 0; i <= W; i++) {
            for (int j = 0; j < n; j++) {
                if (wt[j] <= i && dp[i] < dp[i - wt[j]] + val[j]) {
                    dp[i] = dp[i - wt[j]] + val[j];
                    itemChoice[i] = j;
                }
            }
        }
        Dictionary<int,int> count = new Dictionary<int,int>();
        int w = W;
        while (w > 0 && itemChoice[w] != -1) {
            int idx = itemChoice[w];
            if (!count.ContainsKey(idx)) count[idx] = 0;
            count[idx]++;
            w -= wt[idx];
        }
        return (dp[W], count);
    }

    static void Main() {
        int[] val = {10, 40, 50, 70};
        int[] wt = {1, 3, 4, 5};
        int W = 8;
        int n = val.Length;
        var result = UnboundedKnapsack(W, wt, val, n);
        Console.WriteLine($"Max Value: {result.maxValue}");
        foreach(var kvp in result.itemCount) {
            Console.WriteLine($"Item {kvp.Key} count: {kvp.Value}");
        }
    }
}

A { "Max Value": 100, "Item Counts": { "3": 2 } }

B { "Max Value": 110, "Item Counts": { "1": 2, "3": 1 } }

C { "Max Value": 110, "Item Counts": { "0": 8 } }

D { "Max Value": 120, "Item Counts": { "2": 3 } }

💡 Hint

Trace back the chosen items from the itemChoice array to count how many times each item is picked.

The maximum value is 110. The chosen items are two of item 1 (weight 3, value 40) and one of item 3 (weight 5, value 70).

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