Motivation
In zero-one knapsack, items have weights and profits, and a solution chooses each item at most once while staying within a capacity. A dynamic program indexed by capacity is exact but may take time proportional to a large binary-encoded number. We can instead index by profit and deliberately merge nearby profits. This trades a controlled loss for a state space polynomial in the input length and the reciprocal of an accuracy parameter.
A tempting but unsafe shortcut is to scale by the largest profit among all items. If that item is heavier than the capacity, its profit may be arbitrarily larger than every feasible solution. The rounding error would then be measured against a number unrelated to the optimum. The first step is therefore to discard infeasible items before choosing the scale.
Definitions and setup
Input consists of items with nonnegative integer weights and profits , and a nonnegative integer capacity , all encoded in binary. A subset is feasible when ; its profit is . Let be the maximum feasible profit. We seek a feasible subset of profit at least for rational .
Discard items with . They cannot occur in any feasible subset because weights are nonnegative. Discarding zero-profit items is also safe for maximizing profit; including them cannot improve the objective. If no remaining item has positive profit, return the empty subset. Otherwise there are remaining items and each is individually feasible with positive profit. Let be their largest profit. Then .
Theorems
Theorem 4.5.1
(Profit scaling gives an FPTAS)
For every such instance and every rational , the algorithm below returns a feasible subset with profit at least . Its bit running time and space are polynomial in the binary input length and .
Theorem 4.5.2
(Minimum weight for an exact scaled profit)
For nonnegative integer scaled profits , define as the minimum weight of a subset of the first items whose total scaled profit is exactly , and when none exists. Then
where entries with negative indices are , and initially , for .
Proofs
Algorithm and dynamic-programming proof
Set and let . The dynamic program computes the recurrence for and every from zero to . At each entry retain a predecessor choice attaining the minimum. Pick the largest with , and follow predecessor choices to obtain the corresponding subset.
Proof
(Correctness of the recurrence)
The recurrence is an exhaustive partition of subsets: a subset either omits item , or includes it and has an earlier part of scaled profit . Conversely, adding item to any earlier witness yields a valid distinct-index subset. Induction on proves every finite table value is the stated minimum and has a witness. An entry with is handled normally: the include and omit candidates both refer to row , so a zero-scaled item is never reused within a row.
For implementation, a weight exceeding can be represented by the sentinel , and addition is capped at this value. Nonnegative weights ensure that a partial subset whose weight already exceeds can never become feasible later. A sentinel entry does not have to represent a real subset of weight exactly ; it means only that no feasible-weight witness has been stored. All entries at most retain valid witnesses.
Proof of the approximation guarantee
Proof
(Approximation guarantee)
Let be an optimal feasible subset, and let be the returned subset. Since is feasible, its scaled total is represented by an entry of weight at most . The algorithm maximizes feasible scaled total, so
For every item, . Therefore
In the positive-profit branch an individually feasible positive-profit item guarantees that is nonempty, so summing the strict per-item inequalities is justified. The returned subset is feasible by the selected table entry, so its true profit cannot exceed . When all feasible profits are zero, the separate empty-subset branch is exactly optimal.
Proof X-ray
A lower bound on the true optimum pays for rounding
Where each hypothesis enters: nonnegative weights justify discarding items with , so every remaining item is individually feasible and . Optimality of the table is used once, to compare the returned scaled total with that of a fixed optimum . The key move is the two-sided rounding sandwich : the lower side gives , and the upper side costs less than for each item of , which has at most items. The proof closes because , which is where the choice of scale and the bound meet. Scaling by the profit of an item that cannot be packed would break that last inequality.
State and bit complexity
For each remaining item, , hence . Consequently . The table has rows and at most columns, and each entry needs a constant number of additions and comparisons. Thus the number of table operations is , bounded by .
Write with positive integers . Compute
using exact integer multiplication and division. These integers have polynomially many bits in the input encoding. The capped weights have at most the bit length of , and the index needs bits. Standard integer arithmetic therefore gives polynomial bit time as well as a polynomial number of table operations. Storing all rows and predecessor choices uses polynomial space; two rows suffice for the value alone, but a witness then needs additional reconstruction machinery.
Concept lensAlgorithmic
The table as a shortest-path computation
Take nodes for . Give each node a free edge to and an edge of length to . Then is the length of a shortest path from to , and each path records which items were taken. The recurrence is the shortest-path update on this layered graph.
Worked examples
Worked example 4.5.3
(A small table)
Take weights , profits , capacity and . Both items are individually feasible, , , and . Their scaled profits are . The table gives , , , and . The largest feasible scaled total is two, achieved by the second item with true profit four, which is also optimal.
Worked example 4.5.4
(Rounding changes the selected subset)
Take three items of weight one, profits , capacity and . Now , , , and the scaled profits are . The minimum-weight witness for scaled total three selects only the third item and has true profit four. Selecting all three is feasible and has true profit six. The table still satisfies its guarantee: it maximizes scaled profit and has returned a feasible subset, although it has discarded positive original profit through rounding.
Worked example 4.5.5
(Why infeasible items are removed first)
Let and consider a feasible item of weight one and profit two, plus an item of weight two and profit . The heavy item cannot appear in a feasible subset. Scaling using its profit could make the feasible item's rounded profit zero for a coarse accuracy parameter. Removing it makes , an actual lower bound on the optimum, and the approximation proof applies.
Worked example 4.5.6
(Zero weight and zero optimum)
With capacity zero, a zero-weight item of profit seven is still individually feasible and must not be discarded. The dynamic program may include it once. If all individually feasible items instead have zero profit, the empty subset has the optimal profit zero. The algorithm does not divide by in that branch.
Common mistakes
Counterexample mode
Updating in place in the wrong direction
A one-item instance with weight one, profit one and capacity two permits profit one. If an in-place recurrence immediately reuses an entry just updated for that same item, it can manufacture profit two. Separate previous and current rows, or prove an ordering that prevents reuse; the two-row recurrence makes the zero-one constraint explicit.
Common mistake
(Maximizing scaled profit is not maximizing true profit)
Maximizing the scaled profit is not the same as maximizing true profit exactly. The scheme proves a lower bound on the latter using the comparison with an optimal solution. In particular, choosing a lower-weight witness for each fixed scaled value is safe because it preserves feasibility of that value; choosing a heavier witness arbitrarily could make a reachable scaled value appear infeasible.
Common mistake
(Reading the FPTAS as an exact polynomial algorithm)
The dependence on is part of the claim. It is not a polynomial in the bit length of alone. Selecting an exponentially small error tolerance may take exponentially long in the compact encoding, so the existence of an FPTAS does not imply an exact polynomial-time algorithm for binary-encoded knapsack.
Reading the two dynamic-programming axes
The familiar capacity-indexed table asks for the greatest profit attainable at each allowed weight. This table reverses the question: for each exact scaled profit, what is the least possible weight? A minimum is the right summary because all future item weights are nonnegative. Among two partial subsets with the same scaled profit, the lighter one leaves at least as much capacity for every continuation. Their true profits can differ, but the global rounding inequality accounts for this discrepancy.
The index represents exact scaled profit, not a threshold of at least . This convention makes the recurrence and its initialization unambiguous. Values that cannot be formed remain unreachable; one must not initialize every to zero. The final scan over all exact values finds the best reachable index whose minimum weight fits. A table with threshold semantics can also work, but requires a different recurrence and proof.
The bound is the bridge between numerical scaling and a relative guarantee. By contrast, supplies the finite range of scaled indices: no remaining single profit exceeds . Both inequalities use preprocessing. They serve different purposes and neither follows merely from the definition of a maximum over the original, unfiltered input.
Verifying the output in the original instance
The predecessor path gives an auditable list of original item indices. To check the result independently, add their original weights and profits using integer arithmetic, verify that no index is repeated, and compare the weight with the original capacity. Items discarded as individually infeasible or zero-profit are absent from the witness, which is safe for the objective under the stated nonnegative-weight model. The approximation proof concerns this original profit, not the scaled total reported by the table.
For example, a scaled value of ten alone does not determine a unique true profit. Each selected item can contribute a different rounding remainder, and the number of selected items matters. This is why the proof first relates the scaled optimum to the scaled profit of a fixed true optimum, then converts the result back using a worst-case bound on all of its remainders. It never assumes that rounding preserves the order of all subset profits.
If the rational accuracy parameter is one, the lower bound is zero and is formally weak, even though the computation can return a much better solution. For smaller parameters the table grows as the inverse accuracy grows. The preprocessing case with no feasible positive-profit item avoids a meaningless scale of zero and returns an exact answer without any approximation arithmetic.
Summary
Remove individually infeasible and zero-profit items, then scale the remaining profits by . A minimum-weight dynamic program finds the best feasible scaled total and reconstructs a subset. At most rounding losses, each below , cost at most an fraction of the optimum. The number and bit lengths of table states are polynomial in the input and .
Exercises
Quick check
(Let and items have . For , calculate and the scaled profits, then identify an optimal scaled solution.)
Compute first, then .
Solution · Answer
Both items are feasible, so , and . The scaled profits are one and two. Both together exceed capacity; the second item alone has the larger scaled profit and true profit eight.
Quick check
(Why can an item of weight zero and positive profit not be discarded when ? What does a correct zero-one table do with it?)
Is the item individually feasible?
Solution · Answer
Its weight fits and it improves profit. The recurrence may include it once from the previous row, regardless of the zero capacity; it cannot repeatedly include it in the same row.
Quick check
(Suppose a feasible instance has , largest remaining profit , and . What is and the maximum total rounding loss in the proof?)
Use and the loss bound .
Solution · Answer
. At most five selected items each lose less than one, so the total loss is less than five, equal to as an upper bound.
Quick check
(If , , item has weight two and scaled profit two, compute .)
Compare the omit and include candidates in the recurrence.
Solution · Answer
The omit candidate is eight and the include candidate is . Therefore .