0 1 Knapsack Problem in DSA C#

Mental Model

We want to pick items with values and weights to maximize value without exceeding weight limit. Each item can be chosen only once.

Analogy: Imagine packing a backpack for a trip. You have limited space and many items. You want to pack the most valuable things without overloading the bag.

Knapsack capacity: 5
Items:
[Weight: 2, Value: 3]
[Weight: 3, Value: 4]
[Weight: 4, Value: 5]

Backpack capacity -> |-----|
Items to choose -> [ ] [ ] [ ]

Dry Run Walkthrough

Input: items: [(weight=2, value=3), (weight=3, value=4), (weight=4, value=5)], capacity=5

Goal: Find the maximum total value of items that fit in the knapsack without exceeding capacity 5

Step 1: Start with no items and capacity 0 to 5, initialize DP table with zeros

DP table rows: items 0 to 3, columns: capacity 0 to 5 all zero

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Why: We build solutions bottom-up, starting with no items and increasing capacity

Step 2: Consider item 1 (weight=2, value=3), update DP for capacities 2 to 5

DP after item 1:
0 0 3 3 3 3
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Why: If capacity >= 2, we can take item 1 and get value 3

Step 3: Consider item 2 (weight=3, value=4), update DP for capacities 3 to 5

DP after item 2:
0 0 3 4 4 7
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Why: At capacity 5, taking item 2 plus item 1 (capacity 2) gives value 7

Step 4: Consider item 3 (weight=4, value=5), update DP for capacities 4 to 5

DP after item 3:
0 0 3 4 5 7
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Why: At capacity 4, item 3 alone is better than previous; at 5, previous max 7 remains

Result:

Maximum value = 7 at capacity 5
DP table final row: 0 0 3 4 5 7

Annotated Code

DSA C#

using System;

class Item
{
    public int Weight { get; set; }
    public int Value { get; set; }
    public Item(int weight, int value)
    {
        Weight = weight;
        Value = value;
    }
}

class Knapsack01
{
    public static int Solve(Item[] items, int capacity)
    {
        int n = items.Length;
        int[,] dp = new int[n + 1, capacity + 1];

        for (int i = 1; i <= n; i++)
        {
            for (int w = 0; w <= capacity; w++)
            {
                if (items[i - 1].Weight <= w)
                {
                    dp[i, w] = Math.Max(dp[i - 1, w], dp[i - 1, w - items[i - 1].Weight] + items[i - 1].Value);
                }
                else
                {
                    dp[i, w] = dp[i - 1, w];
                }
            }
        }
        return dp[n, capacity];
    }

    static void Main()
    {
        Item[] items = new Item[]
        {
            new Item(2, 3),
            new Item(3, 4),
            new Item(4, 5)
        };
        int capacity = 5;
        int maxValue = Solve(items, capacity);
        Console.WriteLine(maxValue);
    }
}

for (int i = 1; i <= n; i++)

iterate over items to build solutions including each item

for (int w = 0; w <= capacity; w++)

iterate over all capacities from 0 to max capacity

if (items[i - 1].Weight <= w)

check if current item fits in current capacity

dp[i, w] = Math.Max(dp[i - 1, w], dp[i - 1, w - items[i - 1].Weight] + items[i - 1].Value);

choose max between not taking or taking current item

dp[i, w] = dp[i - 1, w];

if item doesn't fit, keep previous max value

Output

7

Complexity Analysis

Time: O(n * capacity) because we fill a table with n items and capacity columns

Space: O(n * capacity) because we store results for each item and capacity combination

vs Alternative: Compared to brute force checking all subsets (O(2^n)), this DP approach is much faster and practical

Edge Cases

Empty items array

Returns 0 because no items to choose

DSA C#

for (int i = 1; i <= n; i++)

Capacity zero

Returns 0 because no capacity to hold items

DSA C#

for (int w = 0; w <= capacity; w++)

Items heavier than capacity

Items are skipped, result is 0 or max value of lighter items

DSA C#

if (items[i - 1].Weight <= w)

When to Use This Pattern

When you need to maximize value with limited capacity and each item can be chosen once, use 0 1 Knapsack DP to efficiently find the best combination.

Common Mistakes

Mistake: Using capacity index incorrectly by not subtracting item weight when taking item
Fix: Use dp[i - 1, w - items[i - 1].Weight] + items[i - 1].Value to add value of current item correctly

Mistake: Not initializing dp table with zeros or wrong dimensions
Fix: Initialize dp with size (n+1) x (capacity+1) and zeros to handle base cases

Summary

Finds the maximum value of items fitting in a knapsack without exceeding capacity, choosing each item at most once.

Use it when you have a set of items with weights and values and a limited capacity to maximize value.

The key insight is building solutions bottom-up by deciding for each item and capacity whether to include the item or not.

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