Divisible objects: a greedy exchange
Definition 2.9.1
(Fractional knapsack and density)
First suppose an item can be divided: choose a fraction between zero and one of each item. Its contribution is to used capacity and to value, where sizes are now strictly positive and values are nonnegative. The goal is to maximize subject to , for . Define the density . Sort items by nonincreasing density, take each completely while it fits, then take the fraction that fills the remaining capacity and stop. If all items fit, take all of them. If , take none. Equal densities can be ordered arbitrarily.
Theorem 2.9.2
(Fractional knapsack density rule)
The density-order algorithm is optimal for finite items with positive sizes and nonnegative values. Sorting takes comparisons and the subsequent scan takes arithmetic operations, under constant-time exact arithmetic and comparisons.
Proof
(Moving size toward denser items)
To prove it, fix the sorted order and let be the greedy allocation. A feasible allocation that differs from has a first position at which it takes less than : all earlier positions agree, and it cannot take more at because is either one or consumes all remaining capacity. If some later item has positive allocated amount, move a small positive amount of size from to , choosing small enough that neither fraction leaves . Capacity remains unchanged and value changes by . Repeating this exchange, or moving as much as possible at each step, yields an optimum agreeing with one more greedy position. If no later item has positive allocation, adding the missing amount at is feasible and does not decrease value. Since an optimum exists on the compact feasible region, induction over the finite list transforms one into the greedy allocation without decreasing value.
Worked example 2.9.3
(A divisible choice)
With capacity , sizes and values , , have densities . Take all of the first and of either second item, giving . This fractional allocation is not a legal zero-one solution: each selected fraction there must be either zero or one. The best zero-one choice takes both size-five items for value .
The exchange works because a divisible amount of later material can be replaced by the same size of earlier material. With indivisible items, that replacement may not fit or may leave unusable space. This is why the next algorithm preserves alternatives rather than assuming the same greedy rule is safe.
A choice that must be remembered
A traveler has a limited carrying capacity and several objects, each with a size and a value. Taking the most valuable object first can block a better combination; taking the highest value per unit of size can fail too. The useful decision is not just which object looks best now, but what capacity remains after a selection. Dynamic programming makes this remaining capacity part of the state.
Definition 2.9.4
(Zero-one knapsack)
There are individually labeled items. Item has integer size and integer value ; the integer capacity is . Select a subset of the items whose total size is at most , maximizing the sum of its values. Each item may be selected at most once, even when two items have the same size and value. The empty subset is feasible. Assume exact, constant-time arithmetic and comparisons for the stated operation counts; large integer values require their own bit-cost analysis.
Definition 2.9.5
(A prefix and a capacity)
For and , let be the largest value obtainable using only items with total size at most . This is an at-most capacity state: unused capacity is allowed, and for every .
The item prefix is as important as the capacity. It records which items remain available. A state indexed by capacity alone cannot, without more information, distinguish an item that has already been taken from one that is still available.
Recurrence and algorithm
For each , if , set . Otherwise set
Initialize row zero to zero. Process in order and, for each , calculate all capacities from the preceding row. Return . For a witness, save a decision bit for every state: mark take only when the second term is strictly larger, and mark skip otherwise, including ties and the case . Starting at , if the bit says take, output and replace by ; in either case decrement . Stop at .
Common mistake
(Initializing the capacity-zero column to zero)
The scan includes capacity zero. This matters when a zero-size item has positive value: it can be selected once without consuming capacity. In particular, the frequently quoted initialization is valid only when all sizes are positive, or when zero-size items cannot improve the value. For the single item and capacity , the correct entry is , but initializing the column to zero would give .
Concept lensStructural
The table as a longest path through layers
For each state draw a vertex. For , draw an edge from to of length (skip) and, when , an edge from to of length (take). A path from down to row zero decides take or skip for each item exactly once while staying within capacity, and its length is the total value of the taken items, so is the longest path from to row zero. The recurrence is the longest-path recurrence in a layered graph with one layer per item. This explains why each item is used at most once, since every edge goes down one layer, and why reconstruction is simply reading off the path.
Theorem 2.9.6
(Correctness and cost)
The algorithm returns an optimal value and a feasible subset attaining it. Its value table and decision bits use space. Filling them takes unit-cost operations, and reconstruction takes . A value-only implementation can use space.
Why the recurrence is exhaustive
Proof
(Partitioning subsets by the last item)
Consider an optimal subset for . It either excludes item , in which case its value is at most , or includes it. In the second case , and removing item leaves a subset of the preceding items with size at most and value at most . These are upper bounds on the two cases.
When , only the skip case is feasible. Otherwise, an optimum for either preceding state exists because the set of subsets is finite. The first is feasible without item ; for the second, adding item is feasible and cannot repeat it, because the preceding state uses only smaller indices. Thus both displayed alternatives are attainable. Their maximum is exactly . The base row is correct because no item is available. Induction on proves every entry, including and .
The reconstruction follows the very alternative used to obtain each entry. A take decision reduces the remaining capacity by the item's size and then moves to the previous row; a skip moves directly to the previous row. Hence each item is considered once and the chosen sizes fit in the original capacity. Induction backwards through the chosen decisions shows that their values sum to . In a tie, skipping is safe because the first alternative attains the same optimum; a different consistent tie rule can produce another optimal subset.
Proof X-ray
Where the one-use rule is enforced
The key move is to delete item from an optimal subset and land in a state with prefix index . Because the prefix index shrinks, item cannot be chosen again, so the one-use rule is enforced by the shape of the recurrence and not by an extra check. The capacity is only bounded, not matched: the remainder has size at most , which is exactly what an at-most state accepts. Both directions are needed: the upper bounds say the optimum is no larger than the maximum of the two alternatives, and attainability says it is no smaller. Induction on closes the argument from the empty-prefix row, and zero sizes cause no trouble because always decreases. Ties between the two alternatives affect only which subset is reconstructed.
A complete table
Worked example 2.9.7
(Three competing items)
Let be , , and , with . Capacities label the columns. For instance, the last entry of row two compares skipping item two, worth , with taking it and adding , worth .
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 3 | 3 | 3 | 3 |
| 2 | 0 | 0 | 3 | 4 | 4 | 7 |
| 3 | 0 | 0 | 3 | 4 | 5 | 7 |
At , skip item three because . At , take item two, leaving capacity two; at , take item one. The returned subset has size and value . Choosing the single most valuable item gives only .
Counterexample mode
Value density is not a certificate in the zero-one problem
Claim: taking items in order of value-to-size ratio is also optimal when items cannot be split. At capacity , take items , and , written as (size, value). Their ratios are . The rule takes the first item, after which neither other item fits, giving , while the two size-five items together give . The fractional exchange argument needs a divisible amount of later material to replace earlier material, which is not available here. The repair is the table , which keeps the alternatives.
Worked example 2.9.8
(A tie and a zero-size selection)
Let the items be , and , with capacity . At both skipping and taking item three give value , so the stated tie rule skips it. At the take branch gives , exceeding the skip value ; take item two and move to . There the zero-size item improves to , so take it and move to . The result has size and value . Although taking item one leaves capacity unchanged, the row index decreases and reconstruction stops. Taking item three instead of item two would be another optimum.
Compressing the value table
Keep an array , initially all zero. For each item , visit capacities in descending order from to , assigning
Theorem 2.9.9
(One-array update order)
Starting from the zero row, after the pass for item the array equals row of the table , provided the capacities are visited once each in descending order and capacities below are left unchanged.
Proof
(Descending order reads only old values)
At a positive size, has not yet been updated for the current item, so it still holds the preceding-row value. If , the right-hand side reads the old value of the same cell before the single assignment; that cell is updated exactly once for this item. Thus the compressed array ends each item pass equal to the corresponding full row. Capacities below remain unchanged. The argument requires each cell to be visited once per item, not repeatedly until it stops changing.
Proof X-ray
The invariant protects availability
The two-row recurrence reads only the previous item prefix. Descending iteration simulates that separation in one array: smaller capacities are still old when needed. The recurrence and its loop order together enforce the one-use rule. A correct formula evaluated in an incompatible order can solve a different problem.
A single compressed final row does not retain enough decisions to run the reconstruction above; retain the full decision table or supply a separate reconstruction proof. Do not use a mutable predecessor pointer per capacity without proving it still describes the old row.
Counterexample mode
Ascending capacity order reuses an item
Claim: the one-array update gives the same answer when the capacities are visited in ascending order. With the single item and capacity , ascending order first sets , then reads that new value when updating and returns . The item has been used twice, while the zero-one optimum is . The repair is descending order, which reads only old values.
The explorer below replays the compressed updates in both capacity orders and compares the stored value with preserved witnesses, naive mutable pointers and full-table backtracking.
Capacity versus input length
Common mistake
(Reading a pseudopolynomial bound as polynomial time)
There are states, not merely states. The algorithm is polynomial in the numeric value of , but if is given in binary, its encoding takes only bits. For example, increasing from to adds only 20 binary digits while multiplying the capacity dimension by roughly a million. The table is therefore pseudopolynomial; the operation bound does not establish polynomial time in the binary input length. Nor does it count the bit cost of adding arbitrarily large values.
Common mistake
(Initializing impossible exact sizes to zero)
The at-most state also differs from an exact-fill state. If exact total size is required, impossible states must be represented as impossible, not initialized to zero. For a single item of size two, exact size one cannot be filled, even though the at-most-capacity-one optimum is zero.
Building an exact-fill table
Suppose the requirement changes to total size exactly . Define as the greatest value of a subset of the first items whose size is exactly , and use to denote an impossible state. The only reachable size with no items is zero: and for . For , use the same-looking choice
with ; when , copy . The proof again partitions subsets by whether they contain item , but now removing that item leaves exactly . The sentinel is not a value earned by a subset: in an implementation, guard an impossible predecessor before adding its value. A zero-size item still uses the preceding row, so it can be taken only once.
Worked example 2.9.10
(Exact size can be unreachable)
For items and , the rows for capacities zero through five are
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | |||||
| 1 | 0 | 5 | ||||
| 2 | 0 | 5 | 4 | 9 |
In particular, is impossible: skipping the second item requires the impossible state , and taking it requires the impossible state . By contrast, the at-most answer takes the size-two item and leaves two units unused. At exact size five both items fit and give value nine. For an at-most question one may take the maximum of the reachable exact-fill entries for sizes ; an impossible exact entry must not be mistaken for a zero-value solution.
Practice with solutions
Quick check
(With items , and capacity , find the optimum and an optimal subset.)
List the feasible subsets.
Solution · Answer
The feasible nonempty subsets are the individual items; together they have size five. Choose the second, for value .
Quick check
(With items , , and capacity , find . Why does reconstruction terminate?)
Zero-size items fit at capacity zero.
Solution · Answer
Both zero-size items fit, giving ; the last item cannot fit. The row index decreases on every reconstruction step even when the capacity does not change.
Quick check
(With one item and capacity , what does an ascending one-array update return? What is the zero-one optimum?)
Trace the two updates in order.
Solution · Answer
The ascending loop assigns and then . It has reused the item; the correct optimum is .
Quick check
(With one item and capacity , distinguish the at-most optimum from the exact-fill answer.)
An exact-fill state needs a sentinel.
Solution · Answer
The at-most optimum is , leaving one unit unused. Exact size three is impossible, so its state must be marked impossible rather than assigned zero or five.
Quick check
(If and every item has positive size, what does the algorithm return? Explain without assuming .)
Consider which subsets are feasible when .
Solution · Answer
It returns zero: only the empty subset is feasible. This includes the empty item list, for which the initialized base row is the entire computation.
The recurrence is a model for a broader habit: define the state precisely, partition feasible solutions into exhaustive choices, and make the implementation preserve the dependency that the proof needs.