0 1 Knapsack Problem in DSA C# - Cheat Sheet & Quick Revision

Recall & Review

beginner

What does the '0 1' in the 0 1 Knapsack Problem mean?

It means each item can either be taken completely (1) or not taken at all (0). You cannot take fractional parts of an item.

beginner

What is the main goal of the 0 1 Knapsack Problem?

To maximize the total value of items placed in the knapsack without exceeding its weight capacity.

intermediate

In the 0 1 Knapsack Problem, what does the dynamic programming table represent?

Each cell represents the maximum value achievable with a given number of items and a specific weight limit.

intermediate

What is the time complexity of the classic dynamic programming solution for the 0 1 Knapsack Problem?

O(n * W), where n is the number of items and W is the maximum weight capacity of the knapsack.

intermediate

Why can't greedy algorithms solve the 0 1 Knapsack Problem optimally?

Because choosing items based only on value or weight ratio can miss combinations that yield higher total value within the weight limit.

In the 0 1 Knapsack Problem, what does each item represent?

A An item that can be taken fully or not at all

B An item that must be taken

C An item that can be taken partially

D An item with unlimited quantity

Each item can either be taken fully (1) or not taken at all (0), hence the name 0 1 Knapsack.

What does the dynamic programming table store in the 0 1 Knapsack Problem?

A The maximum value for each weight and item count

B The minimum weight for each value

C The total number of items

D The fractional parts of items

The table stores the maximum value achievable for each combination of items and weight limits.

What is the main constraint in the 0 1 Knapsack Problem?

A Total value must be less than capacity

B Items must be sorted by value

C Number of items must be fixed

D Total weight must not exceed capacity

The total weight of chosen items must not exceed the knapsack's capacity.

Which approach is commonly used to solve the 0 1 Knapsack Problem optimally?

A Greedy algorithm

B Dynamic programming

C Divide and conquer

D Brute force without optimization

Dynamic programming efficiently solves the problem by building solutions to smaller subproblems.

What is the time complexity of the dynamic programming solution for 0 1 Knapsack?

A O(n)

B O(W)

C O(n * W)

D O(n^2)

The solution runs in O(n * W), where n is the number of items and W is the knapsack capacity.

Explain the 0 1 Knapsack Problem and how dynamic programming solves it.

Think about choosing items step by step and remembering best values for smaller capacities.

Describe why greedy algorithms do not work for the 0 1 Knapsack Problem.

Consider an example where picking the best item first is not the best overall choice.

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