Sorting by value per unit weight and filling greedily is optimal for the knapsack when items may be cut, and the answer is an exact fraction. Refuse to cut, and the same rule has no guarantee at all: on the opening instance it returns 160 against an optimum of 220, and on another it returns two per cent of the optimum. Taking the better of it and the single most valuable item that fits is guaranteed to reach at least half the optimum — a real bound, and one that no shipped instance comes close to.
Core ideas
Three ideas: why cutting changes the problem completely, why a ratio on one instance is not a guarantee, and what a proved ratio actually promises.
In the fractional problem the densest item can always be taken as far as capacity allows, because any solution not doing so can be improved by swapping weight into it. That is an exchange argument and it is airtight. It relies entirely on weight being divisible: the moment items must be taken whole, “swap weight into the denser item” stops being a legal move and the argument has nothing left.
Density greedy returns 160 where the optimum is 220, a ratio of 8/11. On another of the lab's instances it returns 2 where the optimum is 100, a ratio of 1/50. Neither number is a guarantee, and there is no number that is: for any bound you propose, an instance exists on which plain density greedy does worse. The rule has no approximation ratio at all.
Take the better of density greedy and the single most valuable item that fits. That is at least half the optimum, on every instance. On the opening instance it returns 160 against a promised 110, which is far above the promise — and on all four shipped instances the ratio is 8/11, 3/5, 1 and 47/51, never near a half. A guarantee is a floor, and observing that the floor is loose on four instances says nothing about the fifth.
The material
The fractional problem and its exact answer, the 0/1 problem and the three rules that fail on it, and the second arm that turns a rule with no guarantee into one with a proof.
Given items with positive integer weights wᵢ and values vᵢ and a capacity W, choose amounts xᵢ maximising Σ vᵢ xᵢ subject to Σ wᵢ xᵢ ≤ W. In the fractional problem 0 ≤ xᵢ ≤ 1; in the 0/1 problem xᵢ ∈ {0, 1}. The density of an item is vᵢ / wᵢ.
The lab opens on three items — A 10/60, B 20/100, C 30/120 — with capacity 50, writing each as weight over value. The densities are 6, 5 and 4, compared as exact fractions rather than as decimals, so two items whose densities differ in the fifteenth place are ordered by their values and not by rounding.
Sorting by decreasing density, taking each item whole while it fits and the last one in whatever fraction remains, yields an optimal solution to the fractional knapsack.
Let x be an optimal solution and suppose some item i is taken only partly while a less dense item j is taken in positive amount. Move a small weight ε of capacity from j to i: the value changes by ε(vᵢ/wᵢ − vⱼ/wⱼ) ≥ 0, so the solution does not get worse, and the amounts stay within their bounds for small enough ε.
Repeating drives every such inversion out, so some optimal solution takes the items in decreasing density order, whole while they fit, with at most one cut. That is exactly greedy's answer, and the capacity is used in full unless every item is taken.
□
Densities 6, 5 and 4. Greedy takes A whole (10 of the 50), B whole (30 used), then two thirds of C, giving 60 + 100 + 80 = 240 exactly. The 0/1 optimum, over all 8 subsets, is B and C together for 220 at exactly 50 units of weight. The caption on that instance names the cut item as the cause, which is right; the arithmetic is that the difference is 20 while the two thirds of C is worth 80.
Now run the same density rule on the 0/1 problem. It takes A (10 used, value 60), takes B (30 used, value 160), then cannot fit C, which needs 30 and has 20 left. It stops at 160, with 20 units of capacity unused, against an optimum of 220. The exchange argument that made the rule exact a moment ago is gone: the move it relies on, shifting a little weight between items, is not available.
The panel offers two other orders. By value, highest first, greedy takes C then B and reaches 220 — the optimum. By weight, lightest first, it takes A and B and reaches 160. So on this instance the rule with a theorem behind it loses to the rule that sounds naive, and the reader who concludes that value-first is the better rule will be right about this instance.
And about three of the four. On 1/2, 10/10, 10/10 with capacity 20 the value rule reaches the optimum of 20 while density reaches 12; on 1/2, 50/100 with capacity 50 the value rule reaches 100 while density reaches 2; on the six-item instance both reach 47 against an optimum of 51. Value-first matches the optimum on three of the four shipped instances and density on none of them, and neither fact is a guarantee about either rule.
Let g be the value density greedy returns and s the value of the most valuable single item that fits. Then max(g, s) ≥ OPT / 2, where OPT is the 0/1 optimum, on every instance.
Run density greedy and let i be the first item it rejects, the one that did not fit. The fractional optimum is at most g + vᵢ: greedy took the densest items whole up to i, and the fractional solution can add at most the whole of i beyond that before the capacity is used.
The 0/1 optimum is at most the fractional optimum, so OPT ≤ g + vᵢ ≤ g + s, since i fits by itself and so vᵢ ≤ s. Hence 2 max(g, s) ≥ g + s ≥ OPT, which is the claim. If greedy rejects nothing it took everything and is optimal.
□
On the opening instance the two arms are 160 and 120, so the guaranteed answer is 160, and half the optimum is 110. The guarantee is met with a great deal to spare. On 1/2, 50/100 the arms are 2 and 100, the guaranteed answer is 100, and it is the optimum: density greedy takes the crumb and stops, and the single most valuable item alone does fifty times better.
That instance is labelled in the panel as greedy at almost exactly half, and it is not: density greedy reaches 1/50 of the optimum and the guaranteed arm reaches all of it. The instance's own caption gets it right — it is the one where the second arm rescues the first — and the label contradicts it. Neither string is checked by anything in the build, and the figures above them are.
None of the four shipped instances comes near the bound: the guaranteed arm reaches 8/11, 3/5, 1 and 47/51 of the optimum. A reader who inferred from that row that the true ratio is about three quarters would be reading a floor as an estimate. The bound is a floor, it is proved, and instances that approach it exist even though none of these does.
Measured on this page: fractional 240 exactly, 0/1 optimum 220 over 8 subsets, density greedy 160 at a ratio of 8/11, value-first 220, lightest-first 160, and the guaranteed arm 160 against a promise of 110. Proved on this page: density greedy is exact on the fractional problem, and max(g, s) ≥ OPT / 2 on every instance of the 0/1 problem. Not provable at all: any ratio whatever for plain density greedy on the 0/1 problem.
Interactive
Fractional as an exact fraction, 0/1 against the best of every subset
Method
Five steps. The first three produce numbers; the last two decide what the numbers license.
It is the easy one, it is exact, and it is an upper bound on the 0/1 optimum, which the half-guarantee's proof uses. On the opening instance it is 240, made of A whole, B whole and two thirds of C.
The panel adds up the picks independently and reports the weight used — 30 of 50 for density greedy on the opening instance. A rule that reported a value it could not carry would otherwise look like the winner.
Comparing a whole-item answer with a cut-item answer measures the effect of cutting, not the quality of the rule. Density greedy's shortfall against 220 is the rule's; the further gap from 220 to 240 is the problem's.
On the opening instance the naive value-first rule reaches the optimum and the principled density rule does not. On the six-item instance both fall short and lightest-first falls furthest. Three rules and four instances is twelve numbers, and no ordering of the rules survives all of them.
Write both down. The guaranteed arm reached 8/11 of the optimum here and the guarantee is 1/2. The first is what happened; the second is what will happen on an instance you have not seen, and only the second is a reason to ship the algorithm.
Items A 10/60, B 20/100, C 30/120, written weight over value, with capacity 50. Densities 60/10 = 6, 100/20 = 5, 120/30 = 4.
The twenty units of capacity density greedy leaves unused are the whole story. It spent its first ten on the densest item and then could not fit the third, while the optimum ignores density entirely and packs the capacity exactly. Nothing in the rule notices, because the rule never reconsiders A.
The by-value rule reaching 220 here is worth resisting. It reaches the optimum on three of the four shipped instances, which is a better record than density's zero, and it has no guarantee either: an instance with one enormous heavy item and many smaller ones defeats it just as easily. Three rules, four instances, and not one proved statement among them without the second arm.
For a faded rehearsal, work out all four figures for 12/24, 7/13, 11/23, 8/15, 9/16, 5/9 with capacity 26 before running it. The supplied first move is the densities: C is densest at 23/11, then A at 2, then D at 15/8. Say what the fractional optimum is as a fraction, what the 0/1 optimum is over the 64 subsets, what each of the three rules gets, and whether the guaranteed arm clears half.
You should be able to solve the fractional problem by hand as an exact fraction, run all three 0/1 rules, explain which step of the exchange argument the integrality kills, prove the half-guarantee from the fractional bound, and say why the loose ratios on the shipped instances neither strengthen nor weaken it.
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.