Every cell of the knapsack grid reads only the row above it, so the rows below that one are dead weight and the table can be one row updated in place. Then the direction that row is swept in stops being a detail: backward, an item is taken at most once and the answer is 17; forward, the same three lines of code take items repeatedly and the answer is 19. Both are correct algorithms for different problems.
Core ideas
The hard idea is that the loop direction encodes which row you are reading from, and the code never says which row it means.
V(i, w) reads V(i−1, w) and V(i−1, w − weight(i)), both in the row immediately above. Nothing ever reads two rows up. So the whole table can be one array of W + 1 numbers, overwritten once per item, and the space falls from Θ(nW) to Θ(W) with the same Θ(nW) time.
Going from W down to the item's weight, the cell at w reads w − weight(i), which is to its left and has not been touched yet in this pass. So it still holds the value from before this item was considered, which is exactly V(i−1, ·). The item can therefore be used at most once, and the single row reproduces the grid exactly.
Going upward, the cell at w reads w − weight(i), which this same pass has already updated. That value may already include one copy of the current item, so adding another gives two, and the pass can stack as many copies as fit. The result is the unbounded knapsack, correctly solved — by code that differs from the 0/1 version only in which way the loop counts.
The material
Why one row suffices, what each direction reads, the proof that backward is 0/1, and what the space saving costs.
Look again at the recurrence. V(i, w) is the larger of V(i−1, w) and value(i) + V(i−1, w − weight(i)). Both terms are in row i−1. Row i−2 is never mentioned, and once row i is complete row i−1 is never read again. A table whose rows are used once and discarded does not need to be stored.
Keep an array row[0..W], initialised to zero. For each item in turn, update row[w] = max(row[w], row[w − weight(i)] + value(i)) for every w from weight(i) to W. The order in which those w are visited is not specified by the recurrence and is the subject of this lesson.
If the inner loop runs w from W downward, the array after item i equals row i of the 0/1 grid. If it runs w upward, the array after item i holds the best value obtainable from the first i items with each usable any number of times.
Downward: when w is updated, the cell at w − weight(i) is strictly to the left and, because the loop is descending, has not yet been visited in this pass. It therefore still holds the value it had before item i was considered, which by induction is V(i−1, w − weight(i)). So the update computes exactly max(V(i−1, w), value(i) + V(i−1, w − weight(i))), which is the grid's recurrence, and the array after the pass is row i.
Upward: the cell at w − weight(i) has already been visited this pass, so it holds the best value using items 1..i with item i allowed. Adding one more copy of item i therefore extends a solution that may already contain it, and by induction on w the array holds the unbounded optimum over the first i items. Both statements are exact; neither direction is an approximation of the other.
□
The items are 2/3, 3/5 and 5/9. Swept backward the array ends 0 0 3 5 5 9 9 12 14 14 17 17, so the answer is 17, which is all three items at a total weight of 10. Swept forward it ends 0 0 3 5 6 9 10 12 14 15 18 19, so the answer is 19, which is two copies of 3/5 and one of 5/9 at a total weight of exactly 11. The grid, filled in full, also says 17, and every one of the eight subsets says 17.
The clearest place to see it is after the first pass. Backward, item 2/3 leaves the array 0 0 3 3 3 3 3 3 3 3 3 3: one copy of a weight-2 item is all that any capacity can hold, because the item appears once. Forward, the same item leaves 0 0 3 3 6 6 9 9 12 12 15 15: at capacity 4 it has been taken twice, at capacity 6 three times, and the pass built each of those on the value it had just written two columns earlier.
The reconstruction. The grid records, for each cell, which cell it came from, and the walk back through those pointers is what produced the item set on the previous page. One row has nowhere to keep them: by the time the answer is known, every intermediate value has been overwritten. So the one-row form answers what the optimum is and not what it consists of, and the panel's one-row figures sit beside the grid's rather than replacing them.
That is the trade in one sentence: Θ(W) space instead of Θ(nW), at the cost of the object. Recovering the object from one row means either keeping the rows after all, or running the whole thing again with a divide-and-conquer trick that this course does not develop. Knowing which of the two questions you are answering is the point.
The measured figures are 17 and 19 on three items at capacity 11, with the grid and the enumeration of all eight subsets both confirming 17. The proved statement is that time is Θ(nW) in both forms and space falls from Θ(nW) to Θ(W) — 48 cells against 12 numbers here, which at this size is a saving of thirty-six words and no wall-clock time at all. The space bound is what makes the collapse worth knowing; this instance is far too small to show it, and saying so is more useful than a ratio measured on twelve numbers.
Interactive
0/1 against every subset, and the one loop direction that makes it unbounded
Method
Three checks, and the first of them is the one that decides whether the collapse is available at all.
If it is one, the table collapses to a single row. If cells read two rows back — some sequence recurrences do — keep two. If they read arbitrarily far back, as the chain recurrence does, the table does not collapse at all and trying it will produce exactly the silent failure of the fill-order lesson.
You need the previous row's value at w − weight(i). Sweep away from the direction the reads come from, so that the cells you read are the ones you have not yet overwritten. For reads to the left, that means descending.
The wrong direction does not fail; it solves a different problem, correctly. The only cheap way to know which one you have written is to keep the full grid around on a small instance and compare, which is what the panel does.
One row cannot be walked back. If the answer has to be a set of items rather than a number, the rows are not dead weight and the space saving is not available at this price.
The array holds one number per capacity from 0 to 11 and starts as all zeros. Each line below is the whole array after one item has been processed. The items are A = 2/3, B = 3/5 and C = 5/9, written weight over value.
The first backward line is the tell. After item A the array is 3 at every capacity from 2 upward, because one copy of a weight-2 item is the most that can be in the answer. The first forward line climbs in steps of 3 every two columns, because each cell was built from a cell two to its left that this same pass had already improved.
Both algorithms are correct. Neither is a bug in the other. If the problem says an item exists once, the backward sweep is the algorithm and the forward one silently answers a question nobody asked; if items are available in unlimited quantity, it is the other way round. The failure this page is about is not an incorrect answer but a correct answer to the wrong question, which is the hardest kind to notice in a number.
For a faded rehearsal, keep the items and drop the capacity to 5 before running it. The supplied first move: at capacity 5 the backward answer must be one of 2/3 + 3/5, 5/9 alone, or less, so it is 9 or less. Work out both sweeps by hand for the five columns, then check them — and note that the two agree at some capacities and not at others, which is why spot-checking one column proves nothing.
You should be able to find the furthest row a recurrence reads, derive the direction that keeps the reads on un-overwritten cells, recognise the other direction as a correct algorithm for a different problem, and name what one row cannot do.
Something to change about this lesson? Write it down, tick it off when it is handled, and export the list when you want to act on it. Kept in this browser only: nothing is sent anywhere, and nobody is notified.
No recommendations yet for this lesson.