In 1D unbounded knapsack, why must the capacity loop ascend and reuse cells updated in the same pass?

## What the compressed table means A ticket kiosk sells several products, each with a price and a rider-value, each stockable without limit, and you have a fixed spend budget. Unbounded knapsack asks for the greatest total value you can buy within that budget. The two-dimensional formulation keeps a row per item and a column per capacity. The one-dimensional formulation keeps a single array `dp` of length `budget + 1`, where `dp[w]` is the best value achievable with capacity exactly `w` available, using the items processed so far. Compressing to one row is possible because the recurrence only ever looks left — at a strictly smaller capacity — and, crucially for this variant, at the **current** item row rather than the previous one. ## The recurrence, and where it reads from The two-dimensional recurrence for the unlimited-copies variant is: ``` dp[i][w] = max( dp[i-1][w] , dp[i][w - weight[i]] + value[i] ) ``` Read the second term carefully: it is `dp[i]`, not `dp[i-1]`. It says "after taking one copy of item `i`, I am allowed to take item `i` again", because the sub-state it consults is the one where item `i` is still on the table. That single index is the entire difference from the take-it-or-leave-it variant, whose second term consults the previous row and therefore permits one copy only. Now compress. With a single array processed by ascending capacity, `dp[w - weight[i]]` has already been overwritten during this item's pass, so it *is* the current-row value. Ascending order reproduces `dp[i][w - weight[i]]` exactly. Descending order would leave that cell untouched by this item, so it would still be `dp[i-1][w - weight[i]]` — a different recurrence and a different problem. ## Direction is semantics, not performance This is worth saying out loud in an interview, because the wrong framing is so tempting. A reviewer used to buffer code sees a loop that reads a cell it wrote a moment ago and calls it a bug — a read-after-write hazard, a stale-versus-fresh mix-up. It is not. The freshness *is* the algorithm. Both directions run in the same time, touch the same cells, and produce the same table shape; they compute different quantities. That is what makes a flipped direction such a nasty defect: the code compiles, the table fills, the numbers look plausible, and the total is merely wrong. The defence is a test whose expected answer requires taking one item twice — for example a budget of 6 with a single product priced at 3. The unlimited version buys two of them; the capped version buys one and leaves half the budget unspent. One assertion separates the two variants forever. ## Why the inner loop starts at the item's weight The fragment starts the capacity loop at `weight[i]`, not at 0. That is not an optimization either; it is the guard that keeps `w - weight[i]` from going negative. Capacities below the item's weight cannot hold even one copy, so their cells simply keep whatever value the previous items left there. Writing the loop from 0 with an `if w >= weight[i]` test inside is equivalent and just as correct. ## Does item order matter? For the maximizing objective, no. Every capacity's cell ends up as a maximum over all reachable combinations, and permuting the outer item loop reaches the same set of combinations, so the optimum is identical. This is a genuinely useful thing to know, and it is also a trap: the order-independence holds for `max` (and for `min`, and for boolean reachability), and it does **not** hold when the aggregator counts selections — there, the nesting of the two loops decides whether you are counting unordered selections or ordered sequences, which is a separate question entirely. ## Complexity Filling the compressed table is O(n * budget) time and O(budget) space, for `n` item types. The compression saves a factor of `n` in memory over the two-dimensional table and, in practice, buys a great deal of locality: a single array scanned forward is exactly the access pattern hardware prefetchers are built for. But note again what you give up — the compressed table cannot be walked backwards to reconstruct which items were chosen, because the intermediate rows no longer exist. If the kiosk has to print the basket and not just the total, keep the rows, or keep a parallel array recording, per capacity, the item that produced its current best. ## The one-sentence version Ascending capacity lets an item see itself; descending hides an item from itself. Everything else about the two loops is identical.