Home/Questions/Q 3523
Next
In Process

RTSALL Latest Articles

Abhishek
Begginer
Asked: 2026-09-11T09:51:58-05:00 In: ,

0/1 Knapsack: Why does reverse iteration turn O(N*W) space into O(W) space?

In standard textbook explanations of the 0/1 Knapsack problem, the solution uses a 2D table dp[n][W] where each cell represents the max value using a subset of items under capacity W.

Then instructors show an optimization: ‘Just replace the 2D array with a 1D array of size W, but you MUST iterate backwards from W down to weight[i].’ If you iterate forward, the whole thing breaks. Why does iterating backwards prevent duplicate item selection, while forward iteration works for Coin Change (Unbounded Knapsack)?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Anonymous
    Begginer

    Here is the modern C++20 implementation of the 0/1 Knapsack with 1D Backward Sweep. By reserving contiguous memory and sweeping from capacity down to weight[i], we eliminate all intermediate row allocations.

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>
#include <vector>
#include <algorithm>

int knapsack01(const std::vector<int>& weights, const std::vector<int>& values, int capacity) {
    std::vector<int> dp(capacity + 1, 0);

    for (size_t i = 0; i < weights.size(); ++i) {
        // Must sweep backwards from capacity down to weights[i]!
        for (int w = capacity; w >= weights[i]; --w) {
            dp[w] = std::max(dp[w], dp[w - weights[i]] + values[i]);
        }
    }
    return dp[capacity];
}

int main() {
    std::vector<int> weights = {2, 3, 4, 5};
    std::vector<int> values  = {3, 4, 5, 6};
    int capacity = 5;

    std::cout << "Max Knapsack Value: " << knapsack01(weights, values, capacity) << "n";
    return 0;
}

    Complexity: O(N * W) time, but auxiliary space drops from O(N * W) to just O(W).

    • 0
  2. Anonymous
    Begginer

    This is one of the most fundamental ‘aha!’ moments in dynamic programming. Let’s walk through the memory mechanics so you never forget it.

    1. The 2D State Transition

    In the classic 0/1 Knapsack, the formula is:

    dp[i][w] = max(
    dp[i-1][w],                         // Option A: Skip item i (take answer from previous row)
    dp[i-1][w - weight[i]] + value[i]   // Option B: Take item i (add its value to PREVIOUS row at smaller weight)
)

    Notice the critical detail: in Option B, dp[i-1][w - weight[i]] comes from row i-1 (before item i was even considered). That is what guarantees you only take item i at most once.

    2. Compressing to a 1D Array

    Notice that to compute row i, you only ever look at row i-1. You don’t need rows i-2, i-3, etc. So we can just reuse a single 1D array: dp[w].

    What happens if you iterate FORWARD (w = weight[i] to W)?

    Suppose item 1 has weight = 2, value = 10 and capacity is 6.

    • At w = 2: dp[2] = dp[0] + 10 = 10.
    • At w = 4: dp[4] = dp[4 - 2] + 10 = dp[2] + 10 = 10 + 10 = 20! (Wait, you just reused item 1 twice!)
    • At w = 6: dp[6] = dp[4] + 10 = 30! (You used item 1 three times!)

    Because you updated smaller weights first, larger weights read the already updated values from the current item. That turns it into Unbounded Knapsack (infinite items)!

    What happens if you iterate BACKWARD (w = W down to weight[i])?

    • At w = 6: reads dp[4] (which is still 0 from the previous item!). dp[6] = 0 + 10 = 10.
    • At w = 4: reads dp[2] (which is still 0!). dp[4] = 0 + 10 = 10.
    • At w = 2: reads dp[0] (which is 0!). dp[2] = 0 + 10 = 10.

    By sweeping backwards, whenever you query w - weight[i], that smaller index has not yet been touched for the current item. It still holds the pristine value from item i-1!

    Production Python 3.12 Implementation

    def knapsack_01(weights: list[int], values: list[int], capacity: int) -> int:
    """Solves 0/1 Knapsack with O(W) auxiliary memory."""
    dp = [0] * (capacity + 1)

    for w_i, v_i in zip(weights, values):
        # Sweep backwards from capacity down to the item's weight
        for w in range(capacity, w_i - 1, -1):
            dp[w] = max(dp[w], dp[w - w_i] + v_i)

    return dp[capacity]

    Summary Rule of Thumb

    • 0/1 Knapsack (items used at most once) → Iterate Backward (W → weight).
    • Unbounded Knapsack / Coin Change (items can be reused infinitely) → Iterate Forward (weight → W).
    • 0