0/1 Knapsack: Recursion to Single-Array Space-Optimized Approach

1. Why Do We Need This? (Problem Statement & Status Quo)

Imagine a thief entering a house to steal items. There are $N$ items available, and each item has a specific weight and a specific financial value. The thief carries a knapsack (bag) that has a strict weight capacity limit, say $W$. The thief cannot carry everything; the total weight of the selected items must not exceed the bag's weight capacity.

The goal of the 0/1 Knapsack problem is to choose a subset of items such that:

1. The total weight of the chosen items is $\le W$.
2. The total value of the chosen items is maximized.

Concrete Example Setup

• Items ($N = 3$):
  • Item 0: $\text{Weight} = 3, \text{Value} = 30$
  • Item 1: $\text{Weight} = 4, \text{Value} = 50$
  • Item 2: $\text{Weight} = 5, \text{Value} = 60$
• Bag Capacity ($W$): $8$

If the thief picks Item 0 (weight 3, value 30) and Item 2 (weight 5, value 60):

• Total Weight: $3 + 5 = 8$ (fits the capacity of 8)
• Total Value: $30 + 60 = 90$

Can we pick Item 1 and Item 2?

• Total Weight: $4 + 5 = 9$ (exceeds bag capacity 8, so invalid).

2. Core Mental Model & Why Greedy Fails

Real-Life Analogy: The Uneducated Thief

A common initial instinct is to use a Greedy Approach: sort items by value-to-weight ratio or pick the most expensive item first, then take the next most expensive, and so on, until the bag is full.

However, Greedy fails here because of a lack of uniformity.

Counter-Example:
Bag Capacity (W) = 6
Item 0: Weight = 5, Value = 60  (Most expensive)
Item 1: Weight = 3, Value = 40
Item 2: Weight = 2, Value = 30

• Greedy Choice: The thief greedily picks Item 0 (Value = 60). The remaining bag capacity becomes $6 - 5 = 1$. The thief cannot fit any other items. Total value = 60.
• Optimal Dynamic Programming Choice: The thief picks Item 1 (Value = 40, Weight = 3) and Item 2 (Value = 30, Weight = 2). Total weight = $3 + 2 = 5$ ($\le 6$). Total value = $40 + 30 = \mathbf{70}$.

Because future combinations can yield a higher cumulative value, greedy strategies collapse. We must try all combinations to find the maximal value, which leads us to Recursion and Dynamic Programming.

3. Step 1: Recursive Formulation (Try All Combinations)

To design our recursive function f(index, w), we follow standard dynamic programming on subsequences rules:

1. Express in terms of indices and parameters:

   • index: The current item we are considering (ranging from $n-1$ down to $0$).
   • w: The remaining weight capacity of the bag.
   • Meaning of f(index, w): The maximum value you can achieve considering items from index $0$ to index with a remaining bag weight of w.

2. Explore all possibilities (Pick & Non-Pick):

   • Not Take (Exclude): Do not include the current item. Move to index - 1 with the same bag weight w. Value added = 0.
   • Take (Include): You can only take an item if its weight is less than or equal to the remaining bag weight (wt[index] <= w). If valid, you add val[index] and move to index - 1 with a reduced bag weight: w - wt[index].

3. Take the Maximum: Return the maximum value between taking and not taking.

Base Cases for Recursion

When we reach index == 0 (only one item left):

• If the remaining bag weight w is greater than or equal to wt[0], we can steal it and return val[0].
• Otherwise, we cannot fit it, so we return 0.

4. Step 2: Memoization (Top-Down DP)

Because recursion recomputes overlapping subproblems, time complexity explodes to $\mathcal{O}(2^n)$. We eliminate redundant work by caching states in a 2D DP table of size [n][max_weight + 1] initialized to -1.

Memoized Code Structure (C++)

int f(int index, int w, vector<int>& wt, vector<int>& val, vector<vector<int>>& dp) {
    if (index == 0) {
        if (wt[0] <= w) return val[0];
        return 0;
    }
    
    if (dp[index][w] != -1) return dp[index][w];
    
    int notTake = 0 + f(index - 1, w, wt, val, dp);
    int take = INT_MIN;
    if (wt[index] <= w) {
        take = val[index] + f(index - 1, w - wt[index], wt, val, dp);
    }
    
    return dp[index][w] = max(notTake, take);
}

• Time Complexity: $\mathcal{O}(N \times W)$
• Space Complexity: $\mathcal{O}(N \times W)$ (DP Table) + $\mathcal{O}(N)$ (Recursive Stack Space)

5. Step 3: Tabulation (Bottom-Up DP)

We convert top-down memoization into bottom-up tabulation to eliminate recursion stack space.

Tabulation Logic

• Base Case Translation: For index = 0, any bag weight $w \ge wt[0]$ can store the item, yielding a value of val[0]. All other weights yield 0.
• Nested Loops:
  • Outer loop index from 1 to n - 1.
  • Inner loop w from 0 to max_weight.
• Recurrence Copy: Directly copy the pick/non-pick logic into the table.

Tabulation Code (C++)

int knapsack(vector<int>& wt, vector<int>& val, int n, int maxWeight) {
    vector<vector<int>> dp(n, vector<int>(maxWeight + 1, 0));
    
    // Base case: for index 0
    for (int w = wt[0]; w <= maxWeight; w++) {
        dp[0][w] = val[0];
    }
    
    for (int index = 1; index < n; index++) {
        for (int w = 0; w <= maxWeight; w++) {
            int notTake = dp[index - 1][w];
            int take = INT_MIN;
            if (wt[index] <= w) {
                take = val[index] + dp[index - 1][w - wt[index]];
            }
            dp[index][w] = max(notTake, take);
        }
    }
    
    return dp[n - 1][maxWeight];
}

6. Step 4: Two-Row Space Optimization

Notice that to compute any row index, we only ever require values from the immediate previous row (index - 1). We do not need the entire history of all previous rows.

Thus, we can reduce our space complexity from $\mathcal{O}(N \times W)$ down to $\mathcal{O}(2 \times W)$ by maintaining just two rows: prev and curr.

int knapsackTwoRow(vector<int>& wt, vector<int>& val, int n, int maxWeight) {
    vector<int> prev(maxWeight + 1, 0), curr(maxWeight + 1, 0);
    
    for (int w = wt[0]; w <= maxWeight; w++) {
        prev[w] = val[0];
    }
    
    for (int index = 1; index < n; index++) {
        for (int w = 0; w <= maxWeight; w++) {
            int notTake = prev[w];
            int take = INT_MIN;
            if (wt[index] <= w) {
                take = val[index] + prev[w - wt[index]];
            }
            curr[w] = max(notTake, take);
        }
        prev = curr;
    }
    
    return prev[maxWeight];
}

7. Step 5: Masterclass — Single-Array Space Optimization ($\mathcal{O}(W)$)

Can we optimize this further from two rows down to just a single array ($\mathcal{O}(W)$ space)?

The Problem with Left-to-Right Iteration

If we try to use a single array and iterate bag weight $w$ from 0 up to maxWeight:

• When calculating curr[w], we need prev[w - wt[index]] (a value from the left side of the array).
• If we overwrite our single array from left to right, we destroy the older values of the previous row that our current calculations depend on.

The Right-to-Left Traversal Insight

To safely update a single array in place without losing necessary state from the "previous row", we must iterate the inner weight loop backwards from maxWeight down to 0.

Why does this work? When we compute values moving from right to left, any lookup to w - wt[index] refers to an element on the left side. Since we haven't modified the left side yet in the current row iteration, that left-side value still holds the exact data from the previous row!

Single-Array Space-Optimized Code (C++)

int knapsackSingleArray(vector<int>& wt, vector<int>& val, int n, int maxWeight) {
    vector<int> prev(maxWeight + 1, 0);
    
    // Base case: for index 0
    for (int w = wt[0]; w <= maxWeight; w++) {
        prev[w] = val[0];
    }
    
    for (int index = 1; index < n; index++) {
        // Iterate backwards from maxWeight down to 0
        for (int w = maxWeight; w >= 0; w--) {
            int notTake = prev[w];
            int take = INT_MIN;
            if (wt[index] <= w) {
                take = val[index] + prev[w - wt[index]];
            }
            prev[w] = max(notTake, take);
        }
    }
    
    return prev[maxWeight];
}

8. Summary & Comparison Table

Summary and Key Takeaways

• Greedy Fails: Greedy strategies fail in 0/1 Knapsack due to a lack of value-to-weight uniformity, requiring exhaustive combination checks via Dynamic Programming.
• Subsequence Pattern: The problem models naturally as DP on subsequences using binary choices: Take or Not Take.
• State Representation: Defined by two parameters: index (current item being evaluated) and w (remaining bag weight capacity).
• Base Case Design: Evaluated cleanly at the boundary (index == 0) by checking if the single remaining item fits within the remaining weight capacity.
• Space Reduction Journey: Space complexity evolves effortlessly from $\mathcal{O}(N \times W)$ down to $\mathcal{O}(2 \times W)$ by keeping two rows.
• The Single-Array Trick: By reversing the inner weight loop direction from maxWeight down to 0, we eliminate the second row entirely and achieve optimal $\mathcal{O}(W)$ space complexity without corrupting dependency states.