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

Time Complexity: 0 1 Knapsack Problem

O(n * W)

Understanding Time Complexity

We want to understand how the time needed to solve the 0 1 Knapsack problem changes as we add more items or increase the knapsack capacity.

The question is: how does the work grow when the input size grows?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

int knapsack(int W, int wt[], int val[], int n) {
  int dp[n+1][W+1];
  for (int i = 0; i <= n; i++) {
    for (int w = 0; w <= W; w++) {
      if (i == 0 || w == 0) dp[i][w] = 0;
      else if (wt[i-1] <= w)
        dp[i][w] = std::max(val[i-1] + dp[i-1][w - wt[i-1]], dp[i-1][w]);
      else
        dp[i][w] = dp[i-1][w];
    }
  }
  return dp[n][W];
}
    

This code solves the 0 1 Knapsack problem using dynamic programming by filling a table of size (number of items + 1) by (capacity + 1).

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 W+1 times, so about n * W times.

How Execution Grows With Input

As the number of items (n) or capacity (W) grows, the work grows roughly by multiplying these two.

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

Pattern observation: Doubling items and capacity roughly quadruples the work, showing a multiplication growth.

Final Time Complexity

Time Complexity: O(n * W)

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

Common Mistake

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

[OK] Correct: The capacity also affects the number of operations because the algorithm fills a table for each capacity value up to W, so both n and W matter.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming improves over naive methods and shows your grasp of how input size affects performance.

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 total weight of items without exceeding the value limit

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

C. The number of items selected regardless of weight

D. The minimum weight of items selected

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: Identify the constraint

   The total weight of selected items must not exceed the given weight limit.

3. Final Answer:

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

4. Quick Check:

   Maximize value with weight limit = A [OK]

Hint: Maximize value, keep total weight ≤ capacity [OK]

Common Mistakes:

• Confusing weight limit with value limit
• Trying to maximize weight instead of value
• Ignoring the weight constraint

2. Which of the following is the correct way to declare the DP table for the 0 1 Knapsack Problem in C++ if n is number of items and W is max weight?

easy

A. int dp[n+1][W+1];

B. int dp[W+1][n+1];

C. int dp[n][W];

D. int dp[W][n];

Solution

1. Step 1: Understand DP table dimensions

   The DP table stores solutions for items 0 to n and weights 0 to W, so size is (n+1) x (W+1).

2. Step 2: Match correct declaration

   int dp[n+1][W+1]; declares dp with dimensions [n+1][W+1], matching the problem requirements.

3. Final Answer:

   int dp[n+1][W+1]; -> Option A

4. Quick Check:

   DP table size = (n+1) x (W+1) [OK]

Hint: DP table size = items+1 by weight+1 [OK]

Common Mistakes:

• Using dp[n][W] misses base case row/column
• Swapping dimensions incorrectly
• Declaring smaller arrays causing out-of-bound errors

3. What is the output of the following C++ code snippet for 0 1 Knapsack Problem?

int values[] = {60, 100, 120};
int weights[] = {10, 20, 30};
int W = 50;
int n = 3;

int dp[4][51] = {0};

for (int i = 1; i <= n; i++) {
    for (int w = 1; w <= W; w++) {
        if (weights[i-1] <= w) {
            dp[i][w] = std::max(dp[i-1][w], dp[i-1][w - weights[i-1]] + values[i-1]);
        } else {
            dp[i][w] = dp[i-1][w];
        }
    }
}

std::cout << dp[n][W] << std::endl;

medium

A. 160

B. 180

C. 220

D. 250

Solution

1. Step 1: Understand the DP logic

   The code fills dp table to find max value for weight limit 50 with items of given weights and values.

2. Step 2: Calculate max value manually

   Items: (10,60), (20,100), (30,120). Max value for weight 50 is choosing items 2 and 3: 100 + 120 = 220.

3. Final Answer:

   220 -> Option C

4. Quick Check:

   Max value for W=50 = 220 [OK]

Hint: Pick items with max value under weight limit [OK]

Common Mistakes:

• Adding weights instead of values
• Choosing items exceeding weight limit
• Misindexing arrays causing wrong dp values

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

for (int i = 1; i <= n; i++) {
    for (int w = 1; w <= W; w++) {
        if (weights[i] <= w) {
            dp[i][w] = std::max(dp[i-1][w], dp[i-1][w - weights[i]] + values[i]);
        } else {
            dp[i][w] = dp[i-1][w];
        }
    }
}

medium

A. Indexing weights and values with i instead of i-1

B. Loop ranges should start from 0 instead of 1

C. Using std::max instead of a custom max function

D. Not initializing dp array to zero

Solution

1. Step 1: Check array indexing

   Arrays weights and values are zero-indexed, but code uses i which starts at 1, causing out-of-bound or wrong access.

2. Step 2: Correct indexing

   Use weights[i-1] and values[i-1] to access correct elements.

3. Final Answer:

   Indexing weights and values with i instead of i-1 -> Option A

4. Quick Check:

   Zero-based arrays need i-1 index [OK]

Hint: Use i-1 for zero-based arrays in loops starting at 1 [OK]

Common Mistakes:

• Accessing arrays with wrong index causing runtime errors
• Starting loops at 0 but using i-1 indexing
• Ignoring dp initialization

5. Given items with values {20, 5, 10, 40, 15, 25} and weights {1, 2, 3, 8, 7, 4}, and max weight 10, what is the maximum value achievable using 0 1 Knapsack?

hard

A. 75

B. 65

C. 70

D. 60

Solution

1. Step 1: Analyze items and weight limit

   Items: values = {20,5,10,40,15,25}, weights = {1,2,3,8,7,4}, max weight = 10.

2. Step 2: Find best combination under weight 10

   Choose items with weights 1,3,4 (values 20,10,25) total weight 8, value 55; or items 1,2,6 (weights 1,2,4) value 20+5+25=50; best is items 1,4 (weights 1+8=9) value 20+40=60; or items 4 and 6 (8+4=12 >10) invalid; items 1,5,6 (1+7+4=12 >10) invalid; items 1,3,5 (1+3+7=11 >10) invalid; items 2,3,6 (2+3+4=9) value 5+10+25=40; items 1,2,3,6 (1+2+3+4=10) value 20+5+10+25=60; items 1,2,3,5 (1+2+3+7=13 >10) invalid; items 1,2,3,4 (1+2+3+8=14 >10) invalid; items 1,2,6,5 (1+2+4+7=14 >10) invalid; items 1,3,6 (1+3+4=8) value 20+10+25=55; items 1,2,3,6 total value 60 and weight 10 fits exactly.

3. Final Answer:

   60 -> Option D

4. Quick Check:

   Max value with weight 10 = 60 [OK]

Hint: Try combinations fitting weight limit, sum max values [OK]

Common Mistakes:

• Ignoring weight limit when summing values
• Missing best combination with multiple items
• Assuming greedy choice works always