0 1 Knapsack Problem in DSA C# - Time & Space Complexity

Time Complexity: 0 1 Knapsack Problem

O(n * capacity)

Understanding Time Complexity

We want to understand how the time needed to solve the 0 1 Knapsack problem grows as the input size changes.

Specifically, how does the number of items and the knapsack capacity affect the work done?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int Knapsack(int[] weights, int[] values, int n, int capacity) {
    int[,] dp = new int[n + 1, capacity + 1];
    for (int i = 0; i <= n; i++) {
        for (int w = 0; w <= capacity; w++) {
            if (i == 0 || w == 0) dp[i, w] = 0;
            else 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];
        }
    }
    return dp[n, capacity];
}
    

This code solves the 0 1 Knapsack problem using a bottom-up dynamic programming approach.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops over items and capacities filling the dp table.
• How many times: Outer loop runs n+1 times, inner loop runs capacity+1 times, so roughly n * capacity times.

How Execution Grows With Input

As the number of items (n) or the capacity grows, the work grows proportionally to their product.

Input Size (n, capacity)	Approx. Operations
10 items, capacity 10	~100 operations
100 items, capacity 100	~10,000 operations
1000 items, capacity 1000	~1,000,000 operations

Pattern observation: Doubling either items or capacity roughly doubles the work; doubling both multiplies work by four.

Final Time Complexity

Time Complexity: O(n * capacity)

This means the time needed grows proportionally to the number of items times the knapsack capacity.

Common Mistake

[X] Wrong: "The time depends only on the number of items, so it is O(n)."

[OK] Correct: The capacity also affects the number of steps because the algorithm checks all capacities up to the limit for each item.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming improves over naive methods and shows your grasp of problem scaling.

Self-Check

"What if we used a recursive solution without memoization? How would the time complexity change?"

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