skip to content

In a compressed 1D 0/1 knapsack, why must the inner capacity loop run downward?

level: seniorimportance: should knowfreq 55%

answer

  1. the flat array is two rows folded together
  2. which row should the lower cell hold
  3. left-hand cells are read after being written
  4. one item, capacity twice its weight
  5. downward keeps the left side stale

basics

~20 s

Downward iteration keeps the lower-index cell holding its value from before the current item was offered, so each item is used at most once. Upward iteration reads a cell this item already updated, silently letting one item be counted repeatedly.

solid answer

~40 s

The one-dimensional array is the two-row table folded flat: `dp[w]` after processing item `i` should mean row `i`, while `dp[w - weight[i]]` on the right-hand side must still mean row `i-1`. Iterating capacity downward guarantees exactly that, because every index below `w` is untouched in this pass. Iterating upward destroys it — by the time you reach `w`, the cell at `w - weight[i]` already includes item `i`, so the item is charged and credited again, without limit. The failure is silent: no crash, no exception, just answers that are too large. The smallest input that exposes it is one item of weight 1 and value 1 with capacity 2: downward returns 1, upward returns 2. In review I would reject the upward loop and require that minimal case as a regression test.

code

pseudocode · 5 lines
pseudocode
dp[0..W] = 0
for i in 0..n-1
    for w in weight[i]..W          // upward
        dp[w] = max(dp[w], dp[w - weight[i]] + value[i])
return dp[W]

go deeper

for a junior

Know that the flattened one-array version is the two-row table folded together, and that its loop direction is part of the algorithm rather than a formatting preference.

for a middle

Explain the dependency out loud: the update reads a lower capacity index, and that cell must still hold the state from before the current item was offered.

for a senior

In review, name the failure precisely — the answer is silently too large, never a crash — and produce both the minimal input that proves it and the regression test that pins it.

for a principal

Decide how the team prevents silent-wrong-answer bugs as a class: a slow reference implementation kept for differential tests, or a rule that the compressed form ships only alongside one.

## What the compressed form is The two-dimensional recurrence is `dp[i][w] = max(dp[i-1][w], value[i] + dp[i-1][w - weight[i]])`. Row `i` depends only on row `i-1`, so the whole table is never needed at once — two rows suffice, and with care, one. The flattened array `dp[0..W]` is that single row, rewritten in place as each item is offered. In-place rewriting is only safe if the reads still see what they are supposed to see. There are two reads per cell: - `dp[w]` — the leave branch, which must be row `i-1` at column `w`. - `dp[w - weight[i]]` — the take branch, which must **also** be row `i-1`, at a strictly smaller column (weights are positive). So every read is at an index less than or equal to the index being written, and every read must be stale. ## Why downward works Process `w` from `W` down to `weight[i]`. When you write `dp[w]`, no index below `w` has been touched during this item's pass, so both reads land on untouched — that is, row `i-1` — data. The invariant is: *at the moment `dp[w]` is written, cells `0..w-1` still hold row `i-1`, and cells `w..W` hold row `i`.* The pass sweeps that boundary leftwards until the whole array is row `i`. The loop can stop at `weight[i]` rather than 0, because below that the item cannot fit and the leave branch is a no-op — which also removes any need for a negative-index guard. ## Why upward is wrong, precisely Process `w` upward and the invariant flips: cells below `w` have already been rewritten to row `i`. The take branch then reads `dp[w - weight[i]]` *including item i*, so the update effectively becomes "take item `i`, then solve the remainder with item `i` still available". One item can be selected as many times as it fits. For a drone that owns exactly one spectrometer, the planner now reports a payload with three of them. This is not a slowdown and not a crash. Indices stay in range, the loop terminates, the returned number is merely **too large** — the worst failure shape there is, because it looks like a working feature until someone weighs the actual load. The same requirement applies verbatim to the boolean reachability variant: a single item of amount 3, swept upward, marks 6 and 9 as reachable, and an estate split that is arithmetically impossible is reported as feasible. ## The minimal witness One item, `weight = 1`, `value = 1`, capacity `2`. - Downward: `w = 2` reads `dp[1] = 0`, writes 1; `w = 1` reads `dp[0] = 0`, writes 1. Result 1. Correct. - Upward: `w = 1` reads `dp[0] = 0`, writes 1; `w = 2` reads `dp[1] = 1` (just written), writes 2. Result 2. Wrong. The general rule for a witness: you need capacity at least twice some item's weight. Randomised tests built from heavy items and a tight capacity can pass forever without ever satisfying that, which is why this bug survives test suites and has to be caught in review — or by a test written deliberately. ## How to defend against it beyond review - **Differential testing.** Keep the two-dimensional version, or an exhaustive subset enumeration, as a slow reference and compare on small random inputs. It costs a few lines and catches every variant of this mistake, not just the direction. - **Pin the minimal case.** A single named test with one item and double capacity documents the intent better than any comment. - **Treat the direction as load-bearing.** A comment saying "downward: keeps the previous row visible" belongs on that loop, because the next reader will otherwise see an arbitrary style choice and normalise it. ## The two-dimensional version needs none of this With separate rows there is nothing to overwrite: row `i-1` stays intact while row `i` is filled, so column order is free. That is the real cost of the space optimisation — it trades O(nW) memory for a correctness condition that lives entirely in a loop's direction.

  • What is the smallest input that distinguishes the two loop directions?
    One item with weight 1 and value 1, and a capacity of 2. Downward returns 1, which is correct because there is only one copy of the item. Upward returns 2, because the write at capacity 1 is read back at capacity 2. The general rule is that the witness needs a capacity of at least twice some item's weight — anything tighter cannot expose the reuse.
  • Does the boolean subset-sum compression need the same loop direction?
    Yes, identically. The update reads a lower index that must predate the current item, so an upward sweep marks sums built from several copies of one amount. A single item of amount 3 would mark 6 and 9 as reachable, and a split that is arithmetically impossible would be reported as feasible. Cheaper cells, same dependency, same required direction.
  • Why does the two-dimensional version not care about column order?
    Because it never overwrites what it reads. Row `i-1` sits in its own storage and stays intact while row `i` is filled, so the two reads are always looking at the previous row regardless of the order columns are visited. The one thing that still matters there is the row index on the take branch: it must be `i-1`, not `i`.
  • How would you catch this class of bug with tests rather than review?
    Differential testing. Keep the uncompressed table or an exhaustive subset enumeration as a slow oracle and compare both on small random inputs, deliberately including capacities that are large relative to the item weights. Add one pinned regression test with a single item and double capacity. Random tests alone routinely miss it, because heavy items under a tight capacity never trigger the reuse.

Sweeping capacity upward is like restocking a shelf you are still counting: the new stock lands in front of you and gets counted again as though it had been there all along.

saying these in an interview costs you the question

  • Calls the loop direction a style or micro-optimisation choice
  • Claims upward iteration only wastes time
  • Thinks the bug crashes or under-reports the answer
  • Assumes ordinary random tests would have caught it
  • Cannot name an input that separates the two directions

context

resolving links…