The density rule that solved the fractional problem in Greedy Algorithms and Matroids gives 8 on the lab's four items where the optimum is 9. What replaces it is a grid indexed by which items are on offer and how much room is left, where each cell asks one yes-or-no question and reads exactly two cells in the row above. The items it hands back are then re-weighed against the capacity, because a wrong reconstruction returns a perfectly plausible list.
Core ideas
The hard idea is the choice of state: two axes, one of which is a number from the input rather than a count of anything, and that is where the bound stops being what it looks like.
V(i, w) is the best value obtainable from the first i items within capacity w. Item i is either in the answer or not. If it is not, the value is V(i−1, w). If it is, the value is its own value plus V(i−1, w − weight(i)), which is only available if the item fits. The cell takes the larger, and that is the entire recurrence: two cells in the row above, no search.
The rows count items, so there are n + 1 of them and that is a count of the input's parts. The columns are capacities from 0 to W, so there are W + 1 of them and that is a value from the input, not a count of anything. The grid is (n+1)(W+1) cells — 40 here — and doubling the capacity doubles the work while adding one digit to the input.
An item was taken exactly where the walk's row drops by one and its column moves. Follow those and you get a set of items; the set is well-formed whether or not the walk was right. So the panel re-weighs it against the capacity and re-values it against the number the table reported, and prints both — a list that fits and adds to the claimed value is a checked answer, and a list that merely exists is not.
The material
Why the greedy rule fails here, what the cell reads, how the items come back, and what pseudo-polynomial means.
Given n items with integer weights and values and an integer capacity W, choose a subset whose total weight is at most W and whose total value is as large as possible. Each item is taken whole or not at all — that is the 0/1 — and it is the whole difference from the fractional problem.
Greedy Algorithms and Matroids solves the fractional version by value density: sort by value over weight, take greedily, and cut the last item to fit. The exchange argument works because the last item can be cut. Remove that and the argument has nothing to exchange with, and the rule stops being optimal.
The items are 1/1, 3/4, 4/5 and 5/7, written weight over value, with densities 1, 1.33, 1.25 and 1.4. Densest first takes 5/7, leaving room for 2, which admits only 1/1: total weight 6, value 8. Heaviest first takes the same two. The table reports 9, taking 3/4 and 4/5 for a total weight of exactly 7, and the panel re-weighs that pair and confirms both numbers.
Let V(i, w) be the greatest value obtainable from the first i items with capacity w, with V(0, w) = 0 for every w. Then for i ≥ 1, V(i, w) = V(i−1, w) when weight(i) > w, and otherwise V(i, w) = max( V(i−1, w), value(i) + V(i−1, w − weight(i)) ).
Consider an optimal subset S of the first i items within capacity w. Either item i is in S or it is not. If it is not, S is a subset of the first i−1 items within capacity w, and it must be an optimal one, so its value is V(i−1, w).
If item i is in S, then S without it is a subset of the first i−1 items within capacity w − weight(i), and again it must be optimal there — a better subset could be substituted in, keeping item i, and would beat S. So its value is value(i) + V(i−1, w − weight(i)). The optimum is the larger of the two cases, which is the recurrence.
□
Move the two range controls and the lab paints the chosen cell in one colour and the cells it read in another. For the cell at row 3, column 7 those are (2, 7) and (2, 3) — skip the third item, or take it and look back four columns. That list is not a description of the recurrence written out beside it. It is collected by the reads the recurrence itself performed while the cell was being computed, so it records what the code did rather than what its author believed.
Every cell here reads exactly two, which is what makes the grid Θ(nW) work rather than Θ(nW) cells times something. Compare with the chain table, where a cell reads two per split point and the total is Θ(n³); the number of reads per cell is a property of the recurrence and is worth reading off the painting rather than assumed.
An algorithm is pseudo-polynomial when its running time is polynomial in the numeric value of the input rather than in the length of the input's encoding. The knapsack table is Θ(nW), which is polynomial in W; but W written down takes about log W digits, so the table is exponential in the input's size.
This matters and it is easy to miss, because Θ(nW) reads like a polynomial bound and behaves like one on the instances a lab can show you. Forty cells for four items at a capacity of seven; five hundred for the same four items at a capacity of ninety-nine; five hundred thousand at a capacity of ninety-nine thousand nine hundred and ninety-nine. Three more digits in the input, a thousand times the work. Intractability and Approximation returns to this as the definition of weak NP-hardness, and the table on this page is the reason that distinction exists.
The measured figures here are 40 cells and 51 reads on four items at capacity seven, with every one of the 16 subsets enumerated as a check. The proved statement is Θ(nW) cells with O(1) work each, against Θ(2ⁿ) for the enumeration. On this instance the enumeration walks 16 subsets where the table fills 40 cells, so the exponential route is again ahead — and it stays ahead until the item count and the capacity are both large enough for nW to fall below 2ⁿ, which on the lab's own presets never happens.
Interactive
0/1 against every subset, and the one loop direction that makes it unbounded
Method
The grid is easy; the two things worth doing carefully are choosing the state and checking the walk.
Here: the best value from the first i items within capacity w. If the sentence needs an and and a but, the state is probably wrong, and a wrong state produces a table that fills cleanly and answers a different question.
Every 0/1 recurrence on this course has this shape. The two branches are V(i−1, w) and value(i) + V(i−1, w − weight(i)), and the second exists only when the item fits. Write the fit condition down; forgetting it is how a negative column index becomes a silent zero.
An item was taken where the row drops and the column moves; the row dropping alone means the item was skipped. Those two conditions are the whole reconstruction, and confusing them returns a set that is the right size and the wrong contents.
Add the weights and compare with the capacity; add the values and compare with the table's number. Both, not one — a set can fit and be worth less, or be worth the right amount and not fit, and the panel prints a red verdict for either.
If the answer is a magnitude, the table is pseudo-polynomial and doubling the capacity doubles the work for one extra digit of input. That is a fact about the state you chose, and it is worth knowing before the instance arrives rather than after.
Rows are item prefixes, columns are capacities from 0 to 7. Item A is 1/1, B is 3/4, C is 4/5, D is 5/7, each written weight over value.
The last row is where the greedy instinct is refuted in one line. Item D has the highest density and the largest value, and the corner cell declines it, because taking it leaves capacity 2 and the best thing that fits in 2 is worth 1. Density is a rate and the capacity is finite; the rule that works when the last item can be cut does not survive the item being indivisible.
The walk back reads the row and the column together. From (D, 7) the pointer goes to (C, 7) — row drops, column stays, so D was skipped. From (C, 7) it goes to (B, 3) — row drops and column moves by 4, which is C's weight, so C was taken. Two more steps and the set is B, C, which the panel re-weighs to 7 and re-values to 9.
For a faded rehearsal, switch to the three items 2/3, 2/3, 3/4 at capacity 4 before running it. The supplied first move: the first two items together weigh exactly 4 and are worth 6, and the third alone is worth 4. Decide what the table reports, decide which set the walk returns, and check both — and notice that the two equal items give the same value at capacities 2 and 3, where the tie-break picks one of them with no reason to prefer it.
You should be able to write the in-or-out recurrence with its fit condition, read the dependency painting as a record rather than a diagram, re-weigh and re-value a reconstruction, and say why a bound mixing a count with a magnitude is not polynomial in the input.
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.