A discrete allocation decision
Suppose each project can be chosen at most once, has a positive integer resource requirement and a nonnegative value , and the available integer capacity is . We seek a subset of projects of total weight at most and maximum total value. Choosing by value per unit of resource is not generally optimal when projects cannot be split.
We assume finite inputs, integer weights and capacity, and exact arithmetic. Values may be real in the mathematical recurrence; the bit-complexity discussion below assumes nonnegative integer values encoded in binary.
Definition 3.2.1
(0–1 knapsack instance and capacity table)
An instance consists of items with integer weights and values , and an integer capacity . A subset is feasible when . The output is the maximum of over feasible , together with one feasible subset attaining it (a witness).
For and integers , let
The maximum is over a finite nonempty family, because the empty set is always allowed. The optimal value of the instance is .
The state remembers what remains available
The index records which items may still be used, and records how much capacity remains. The empty set is feasible, so .
Theorem 3.2.2
(The capacity recurrence)
For every integer , , and for ,
Proof
(Split the feasible subsets by item )
Fix and . Every subset of weight at most belongs to exactly one of two classes. If , then has weight at most , so its value is at most . If , then , and has weight at most ; hence the value of is at most . Thus is at most the right-hand side.
Conversely, a subset attaining is feasible for . When , adding item to a subset attaining gives a subset of of weight at most and value . So the right-hand side is attained, and equality holds. Induction on from the base row proves the recurrence for every table entry, including when some values are zero or several subsets tie.
Proof X-ray
Why the previous row enforces 0–1 choice
When item is included, the remaining subproblem is , not . The previous row cannot use item again. Reusing the current row instead permits repeated copies and solves a different, unbounded model. If using a single array, update capacities downward so the entry at still belongs to the previous item stage; ascending updates have the same reuse hazard.
The two capacity conventions in use must not be confused.
Common mistake
(Mixing “at most” and “exactly” capacity)
With the base row for every , the entry is the best value of weight at most . It is not the best value of weight exactly . In the table below, although no subset of the three items, not even the empty one, has weight exactly one. A table for exact weights needs the base row and for , with the same recurrence; the knapsack optimum is then , not .
A table and a witness
Worked example 3.2.3
(A three-item table and its witness)
For weights , values and , the rows for capacities are
At , excluding item 3 gives seven, while including it gives , so exclude it. At , inclusion gives , so take item 2 and continue at . Take item 1. The witness has weight and value . At equality either branch can reconstruct an optimum; with zero values, do not infer a unique subset merely from a table value.
Worked example 3.2.4
(Items that never fit or add nothing)
Append to the previous instance item 4 with and item 5 with , keeping . Since for every , only the first case of the recurrence occurs, and entry by entry. The largest value in the instance is unreachable.
For item 5, for . Every row is nondecreasing in , because a larger capacity admits more subsets, so . The optimum is still seven. At both branches give zero: excluding item 5 gives and including it gives . Both and are optimal witnesses at capacity one, which is why a tie rule must be fixed before a reconstruction is called unique.
Worked example 3.2.5
(A descending one-array pass)
Keep one array , start from , and for each item update for . Entries with are not touched, which is the first case of the recurrence.
- Item 1, : capacities each read , so .
- Item 2, : gives ; gives ; gives . Now .
- Item 3, : gives ; gives . Now .
After each item the array equals the corresponding table row. At for item 2 the scan read before could be changed by item 2, so the entry still belonged to the previous stage.
Counterexample mode
A density-greedy choice can fail
Take capacity four and three distinct items . The first has density , greater than for either smaller item. Density-greedy takes it and has insufficient capacity for another item, giving value five. The two smaller items together have weight four and value six. The two smaller items are distinct 0–1 choices.
Cost of the algorithm
Proposition 3.2.6
(Size of the table computation)
The full table can be filled with arithmetic operations and stored values. A descending one-array implementation computes with operations and stored values.
The full table contains entries and each update uses a constant number of arithmetic operations and comparisons, which proves both bounds. A one-array implementation keeps only the current row; to reconstruct a subset, retain suitable choices or recompute stages. With binary integer values, a table entry is at most the sum of the input values, so its bit length is polynomial in the input length; arithmetic operations are not automatically constant-time bit operations.
Common mistake
(Calling an bound polynomial time)
The bound counts operations in terms of the numeric value . The input writes with about bits, so a capacity of costs only bits but produces a table with columns. Doubling the number of bits of can square the running time of the table method. The bound is therefore pseudo-polynomial: polynomial in and the value of , not in the length of the input.
Exercises
Quick check
(Recompute and explain which item it selects.)
Solution · Answer
Excluding item 3 gives ; including it gives . Item 3 alone is selected.
Quick check
(For a single item of weight two and value three, explain why an ascending one-array update would incorrectly obtain value six at capacity four.)
Solution · Answer
After updating capacity two to three, an ascending scan can read that updated value at capacity four and add item one again, producing six. Descending order reads the previous stage's zero instead.
Quick check
(If under our positive-weight assumption, what is the optimal value?)
Solution · Answer
No positive-weight item fits. The empty set has value zero and is optimal.
Quick check
(Give two different optimal subsets when two distinct items both have weight one and value one and .)
Solution · Answer
Either singleton is feasible and worth one. Both together exceed capacity, so each singleton is optimal; a tie rule returns one, not necessarily both.