0 1 Knapsack Problem in DSA C# - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the DP table for the 0 1 Knapsack problem.

DSA C#

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

Drag options to blanks, or click blank then click option'

Acapacity

Bweights.Length

Cvalues.Length

Dcapacity + 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using weights.Length instead of capacity + 1 for the second dimension.

Forgetting to add 1 to capacity.

The DP table has rows for items and columns for capacities from 0 to capacity, so the second dimension is capacity + 1.

2fill in blank

medium

Complete the code to check if the current item's weight fits in the current capacity.

DSA C#

if (weights[i - 1] [1] w) {

Drag options to blanks, or click blank then click option'

A>

B==

C<=

D<

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' which checks if the item is too heavy.

Using '==' which is too restrictive.

We check if the item's weight is less than or equal to the current capacity to decide if we can include it.

3fill in blank

hard

Fix the error in the return statement to get the maximum value from the DP table.

DSA C#

return dp[[1], capacity];

Drag options to blanks, or click blank then click option'

Aweights.Length

Bcapacity

Cvalues.Length

Dweights.Length - 1

Attempts:

3 left

💡 Hint

Common Mistakes

Using capacity as row index instead of weights.Length.

Using weights.Length - 1 which misses the last item.

The last row of the DP table corresponds to all items considered, which is weights.Length.

4fill in blank

hard

Fill both blanks to correctly update the DP table when the item fits.

DSA C#

dp[i, w] = Math.Max(dp[i - 1, w], dp[i - 1, w [1] weights[i - 1]] [2] values[i - 1]);

Drag options to blanks, or click blank then click option'

A-

B+

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' instead of '-' for capacity adjustment.

Using '*' or '/' which are incorrect operations here.

We subtract the item's weight from current capacity and add the item's value to the previous best.

5fill in blank

hard

Fill all three blanks to complete the nested loops for filling the DP table.

DSA C#

for (int [1] = 1; [1] <= weights.Length; [1]++) {
    for (int [2] = 1; [2] <= [3]; [2]++) {
        // DP logic here
    }
}

Drag options to blanks, or click blank then click option'

Ai

Bw

Ccapacity

Dn

Attempts:

3 left

💡 Hint

Common Mistakes

Using 'n' instead of 'capacity' for inner loop limit.

Using same variable for both loops.

The outer loop iterates over items (i), the inner loop over capacities (w) up to capacity.

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