0 1 Knapsack Problem in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of 0 1 Knapsack DP Table

What is the final maximum value stored in the DP table for the given weights and values after running the 0 1 Knapsack algorithm?

DSA C#

int[] weights = {1, 3, 4, 5};
int[] values = {1, 4, 5, 7};
int capacity = 7;

int[,] dp = new int[weights.Length + 1, capacity + 1];

for (int i = 1; i <= weights.Length; i++) {
    for (int w = 1; w <= capacity; w++) {
        if (weights[i - 1] <= w) {
            dp[i, w] = Math.Max(dp[i - 1, w], dp[i - 1, w - weights[i - 1]] + values[i - 1]);
        } else {
            dp[i, w] = dp[i - 1, w];
        }
    }
}

Console.WriteLine(dp[weights.Length, capacity]);

A 11

B 9

C 10

D 12

💡 Hint

Think about which items fit best without exceeding the capacity.

The maximum value achievable with capacity 7 is 11 by choosing items with weights 3 and 5 (values 4 + 7 = 11). Other combinations like 3 and 4 give 9. The DP table confirms 11 as max.

🧠 Conceptual

intermediate

Understanding 0 1 Knapsack Item Inclusion

In the 0 1 Knapsack problem, if the weight of the current item is more than the current capacity, what does the algorithm do?

A Includes the item and reduces capacity accordingly

B Excludes the item and keeps the previous maximum value for that capacity

C Splits the item into smaller parts to fit the capacity

D Throws an error because the item cannot fit

💡 Hint

Remember, 0 1 Knapsack means you either take the whole item or leave it.

If the item is too heavy for the current capacity, the algorithm cannot include it, so it keeps the previous best value without this item.

🔧 Debug

advanced

Identify the bug in this 0 1 Knapsack implementation

What error will this code produce when run?

DSA C#

int[] weights = {2, 3, 4};
int[] values = {3, 4, 5};
int capacity = 5;

int[,] dp = new int[weights.Length, capacity + 1];

for (int i = 1; i <= weights.Length; i++) {
    for (int w = 1; w <= capacity; w++) {
        if (weights[i - 1] <= w) {
            dp[i, w] = Math.Max(dp[i - 1, w], dp[i - 1, w - weights[i - 1]] + values[i - 1]);
        } else {
            dp[i, w] = dp[i - 1, w];
        }
    }
}

Console.WriteLine(dp[weights.Length - 1, capacity]);

A IndexOutOfRangeException

B Correct output: 7

C NullReferenceException

D Compilation error due to missing semicolon

💡 Hint

Check how the dp array is declared and accessed.

The dp array is declared with size weights.Length but accessed with index i which goes up to weights.Length, causing an index out of range error.

❓ Predict Output

advanced

Output of Knapsack with Zero Capacity

What will be the output of the following code snippet?

DSA C#

int[] weights = {1, 2, 3};
int[] values = {10, 20, 30};
int capacity = 0;

int[,] dp = new int[weights.Length + 1, capacity + 1];

for (int i = 1; i <= weights.Length; i++) {
    for (int w = 1; w <= capacity; w++) {
        if (weights[i - 1] <= w) {
            dp[i, w] = Math.Max(dp[i - 1, w], dp[i - 1, w - weights[i - 1]] + values[i - 1]);
        } else {
            dp[i, w] = dp[i - 1, w];
        }
    }
}

Console.WriteLine(dp[weights.Length, capacity]);

A IndexOutOfRangeException

B 10

C Compilation error

D 0

💡 Hint

Think about what happens when capacity is zero.

With zero capacity, no items can be included, so the maximum value is zero.

🧠 Conceptual

expert

Time Complexity of 0 1 Knapsack DP Solution

What is the time complexity of the dynamic programming solution to the 0 1 Knapsack problem with n items and capacity W?

A O(n + W)

B O(n^2 * W)

C O(n * W)

D O(2^n)

💡 Hint

Consider the nested loops over items and capacity.

The DP solution uses a table of size n by W and fills it once, resulting in O(n * W) time complexity.

Practice

1. What does the 0 1 Knapsack Problem aim to maximize given a set of items with weights and values?

easy

A. The minimum weight of items selected

B. The total weight of items without exceeding the value limit

C. The number of items selected regardless of weight

D. The total value of items without exceeding the weight limit

Solution

1. Step 1: Understand the problem goal

   The 0 1 Knapsack Problem tries to select items to maximize total value without exceeding the weight capacity.

2. Step 2: Clarify constraints

   Each item can be chosen only once (0 or 1 times), and total weight must not exceed the limit.

3. Final Answer:

   The total value of items without exceeding the weight limit -> Option D

4. Quick Check:

   Maximize value under weight limit = D [OK]

Hint: Remember: maximize value, not weight or count [OK]

Common Mistakes:

• Confusing weight limit with value limit
• Thinking items can be chosen multiple times
• Maximizing weight instead of value

2. Which of the following is the correct C# syntax to declare a 2D array for dynamic programming table in 0 1 Knapsack?

easy

A. int[,] dp = new int[n, W];

B. int[][] dp = new int[n][W];

C. int dp[][] = new int[n][W];

D. int dp = new int[n, W];

Solution

1. Step 1: Recall C# 2D array declaration

   In C#, 2D arrays are declared as int[,] dp = new int[n, W].

2. Step 2: Check each option

   int[,] dp = new int[n, W]; uses correct syntax. int[][] dp = new int[n][W]; is jagged array but syntax is wrong. int dp[][] = new int[n][W]; is invalid in C#. int dp = new int[n, W]; misses brackets.

3. Final Answer:

   int[,] dp = new int[n, W]; -> Option A

4. Quick Check:

   C# 2D array = int[,] dp = new int[n, W]; [OK]

Hint: Use int[,] for 2D arrays in C# [OK]

Common Mistakes:

• Using jagged array syntax incorrectly
• Missing commas in array declaration
• Confusing C# with Java or C++ syntax

3. What is the output of the following C# code snippet for 0 1 Knapsack with weights = {1, 3, 4}, values = {15, 50, 60}, capacity = 5?

int[] weights = {1, 3, 4};
int[] values = {15, 50, 60};
int capacity = 5;
int n = weights.Length;
int[,] dp = new int[n + 1, capacity + 1];
for (int i = 1; i <= n; i++) {
  for (int w = 1; w <= capacity; w++) {
    if (weights[i - 1] <= w) {
      dp[i, w] = Math.Max(values[i - 1] + dp[i - 1, w - weights[i - 1]], dp[i - 1, w]);
    } else {
      dp[i, w] = dp[i - 1, w];
    }
  }
}
Console.WriteLine(dp[n, capacity]);

medium

A. 75

B. 80

C. 65

D. 60

Solution

1. Step 1: Fill dp table for each item and capacity

   For capacity 5 and items: - Item 1 (weight 1, value 15): dp[1,1..5] = 15 - Item 2 (weight 3, value 50): dp[2,3] = max(50 + dp[1,0], dp[1,3]) = 50, dp[2,4] = max(50 + dp[1,1], dp[1,4]) = 65, dp[2,5] = max(50 + dp[1,2], dp[1,5]) = 65 - Item 3 (weight 4, value 60): dp[3,4] = max(60 + dp[2,0], dp[2,4]) = 65, dp[3,5] = max(60 + dp[2,1], dp[2,5]) = 75

2. Step 2: Identify final dp value

   The maximum value for capacity 5 is dp[3,5] = 75.

3. Final Answer:

   75 -> Option A

4. Quick Check:

   Max value at capacity 5 = 75 [OK]

Hint: Trace dp table row by row for each item [OK]

Common Mistakes:

• Not adding previous dp values correctly
• Mixing up weights and values
• Off-by-one errors in loops

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

int[] weights = {2, 3, 4};
int[] values = {40, 50, 60};
int capacity = 5;
int n = weights.Length;
int[,] dp = new int[n + 1, capacity + 1];
for (int i = 0; i <= n; i++) {
  for (int w = 0; w <= capacity; w++) {
    if (weights[i] <= w) {
      dp[i, w] = Math.Max(values[i] + dp[i - 1, w - weights[i]], dp[i - 1, w]);
    } else {
      dp[i, w] = dp[i - 1, w];
    }
  }
}
Console.WriteLine(dp[n, capacity]);

medium

A. Incorrect comparison operator in if condition

B. Wrong initialization of dp array size

C. Index out of range error due to i starting at 0

D. Missing return statement in method

Solution

1. Step 1: Analyze loop and array indexing

   The loop starts at i=0 and accesses weights[i], values[i], and dp[i-1,...]. At i=0, dp[i-1,...] is dp[-1,...], which is invalid and causes an index error.

2. Step 2: Identify correct loop start

   Loops should start at i=1 to avoid negative indices when accessing dp[i-1,...].

3. Final Answer:

   Index out of range error due to i starting at 0 -> Option C

4. Quick Check:

   Negative index access = error [OK]

Hint: Start loops at 1 when using dp[i-1] indexing [OK]

Common Mistakes:

• Starting loop at 0 causing negative index
• Ignoring dp array bounds
• Confusing loop variables with array indices

5. Given items with weights = {2, 3, 5, 7}, values = {10, 5, 15, 7}, and capacity = 10, which set of items maximizes value without exceeding capacity in 0 1 Knapsack?

hard

A. Items with weights 3 and 7 (total value 12)

B. Items with weights 2, 3, and 5 (total value 30)

C. Items with weights 5 and 7 (total value 22)

D. Items with weights 2 and 7 (total value 17)

Solution

1. Step 1: Calculate total weights and values for each option

   Items with weights 2, 3, and 5 (total value 30): weights 2+3+5=10, values 10+5+15=30 Items with weights 3 and 7 (total value 12): weights 3+7=10, values 5+7=12 Items with weights 5 and 7 (total value 22): weights 5+7=12 (exceeds capacity 10) Items with weights 2 and 7 (total value 17): weights 2+7=9, values 10+7=17

2. Step 2: Choose valid option with max value

   Items with weights 5 and 7 (total value 22) exceeds capacity, so invalid. Among others, Items with weights 2, 3, and 5 (total value 30) has max value 30.

3. Final Answer:

   Items with weights 2, 3, and 5 (total value 30) -> Option B

4. Quick Check:

   Max value under capacity 10 = 30 [OK]

Hint: Sum weights and values, pick max value under capacity [OK]

Common Mistakes:

• Choosing items exceeding capacity
• Ignoring total value calculation
• Not checking all combinations