Motivation
A decision can be locally attractive and still leave a poor remainder. With coins of denominations one, three and four, repeatedly taking the largest coin at most the remainder makes six as four plus one plus one. Two threes use fewer coins. The greedy choice is feasible, but feasibility alone is not optimality.
Dynamic programming replaces such a choice with a family of precisely defined subproblems. We will write the alternatives, prove that they cover every solution, and evaluate them in an order in which their dependencies are already known. The table does more than give a number: if we retain suitable choices, it reconstructs an actual solution.
A finite 0–1 selection problem
There are distinct items. Item has positive integer weight and integer value ; it may be selected at most once. A nonnegative integer capacity bounds the total weight. The empty selection is allowed, and the goal is to maximize total value subject to weight at most . Values may be negative: the empty selection then ensures the optimum is at least zero. Items are distinguished by index even when their weights or values coincide.
Definition 3.6.1
(Prefix–capacity state )
For and , is the maximum value obtainable using only the first items with capacity at most . This is a different state for each prefix and capacity. In particular for every , and because weights are positive, .
Theorem 3.6.2
(The 0–1 recurrence)
For , if then . Otherwise
Filling rows in increasing item order computes the optimum . A full table supports recovery of an optimal subset, even when several subsets tie.
Derive the state transition
Proof
(Case split on the last item, then induction on rows)
Every feasible subset of the first items either omits item or contains it. In the first case its value is bounded by , and an optimal old subset attains that bound. In the second case, possible only if , removing item leaves a subset of the first items with capacity at most . Its value is therefore at most the second candidate. Conversely, append item to an optimum realizing that candidate; no item is reused. The better candidate is both attainable and at least the value of every feasible subset.
The base row has only the empty subset. Inductively each row is correct once the preceding row is correct. Within a row, capacities may be visited in any order if the full preceding row remains unchanged. The state is an at-most capacity: it need not be filled exactly. Replacing its base row by impossible values except at capacity zero would define a different, exact-weight problem.
To reconstruct, start at . If the current entry equals the entry immediately above, omit that item and move to the preceding row. Otherwise the item must have fit and the second candidate attained the maximum: include it, decrease the capacity by its weight, and move to the preceding row. In a tie, omitting is a valid choice. The row index decreases at every step, so after at most steps the selected items are distinct and their total value is the final table entry. Keeping only the numerical optimum without choices or old rows is not, by itself, a reconstruction procedure.
Proof X-ray
Where each hypothesis enters the knapsack proof
The one idea is the partition by the last item: “omit item ” and “use item ” cover every feasible subset and never overlap, so the maximum over the two cases is the maximum over all subsets. Each case is proved by two inequalities, an upper bound for every subset in the case and an attaining subset built from an optimum of a smaller state. The second candidate reads row , not row ; that index is what makes the appended subset use item once. Reading instead would allow a second copy and prove the recurrence of a different, unlimited-copy problem.
Positivity of the weights is used twice: it gives , and it makes strictly smaller, which the compressed pass below needs. The induction is on the row index, so the evaluation order only has to finish row before row . Reconstruction closes for the same structural reason: each step moves to row , and in a tie the entry above is itself attained by a subset of the first items, so omitting never loses value.
Compressing the table without reusing an item
A one-dimensional array initially contains zero at every capacity. For each item, visit capacities from down to and replace the current entry by the maximum of itself and the entry at plus . Since , the smaller capacity has not yet been visited in this item's downward pass. It still contains the preceding row's value. The update therefore computes exactly the recurrence above. If , this item makes no update.
In the opposite, increasing direction the smaller-capacity entry may already include the same item, so the array no longer stores row when it is read. One row gives the optimal value in stored entries, but direct reconstruction by the earlier method requires the old rows or additional justified information.
Counterexample mode
A correct recurrence with the wrong update order
Claim: the in-place pass may visit capacities in either direction. Take one item of weight two and value three, capacity four, and the array indexed by capacities . An increasing pass sets capacity two to and capacity three to . At capacity four it reads the entry at two, already rewritten, and stores . The only feasible subsets are the empty set and the single item, of values zero and three, so the true optimum is three: the pass has used the item twice. The downward pass computes capacity four first, from the untouched zero at capacity two, and returns three. The repaired statement: for the 0–1 problem the pass must run from down to ; the increasing pass is the recurrence for unlimited copies.
A different state: minimum coins for an exact amount
Now let be positive integer denominations with unlimited copies, and let be the target amount. We seek the fewest coins totaling exactly ; a target may be impossible.
Definition 3.6.3
(Exact minimum-coin state )
For , is the minimum number of coins totaling exactly , and when no representation exists. The base is .
Theorem 3.6.4
(Exact minimum-coin recurrence)
For ,
where the minimum of an empty set is and . Evaluate ; then is the minimum count or the correct impossibility report.
Proof
(Remove the last coin)
Every representation of positive amount has a last coin, say . Removing it gives a representation of , so its count is at least the corresponding candidate. Conversely, when that smaller state is finite, adding the chosen coin attains one more than its count. If no smaller state is finite, no representation exists. The two inequalities and induction on establish the recurrence. Positivity is essential: it makes every dependency strictly smaller and prevents the reconstruction from remaining at the same amount.
Store one denomination attaining a finite minimum at each positive reachable amount. Starting at , repeatedly output the stored coin and subtract its denomination. The remaining amount strictly decreases and reaches zero; its recorded predecessor counts decrease by one each time. The resulting list has exactly coins. For return the empty list, and if report no representation instead of trying to backtrack.
The order of coins does not affect the minimum count, so calling one of them “last” is a proof device. If the task were to count representations, ordered sequences and unordered multisets would require different states or loop conventions; the minimum recurrence alone does not decide that counting question.
Concept lensStructural
Both tables as paths in an acyclic graph
Put a vertex at each amount and an edge of length one from to whenever . A sequence of coins with total is exactly a directed path from to , its length being the number of coins. Hence is the shortest-path distance from to , and means that is unreachable. Every edge decreases the amount, so the graph has no cycle, and the order lists each vertex after all vertices it points to.
The knapsack table has the same shape. From draw an edge of weight zero to and, when , an edge of weight to . A path from to row zero chooses each item at most once and keeps the used weight at most , and every feasible subset gives such a path. Thus is the largest path weight to row zero, and reconstruction is the recovery of one optimal path.
Costs and the meaning of the input
Proposition 3.6.5
(Table sizes and operation counts)
The full knapsack table has entries and is built with exact operations; reconstruction from it takes at most steps. The descending one-row value computation uses entries. The coin-change table uses exact operations and entries, including one stored predecessor per amount.
Each knapsack entry is computed using constant many comparisons and additions, and each coin-change entry compares at most candidates, which gives the counts after initialization is included. Outputting a coin list also costs time proportional to its length.
These bounds are pseudopolynomial: they depend on the numeric capacity or target, which can be exponentially larger than its binary encoding length. For integer item values of absolute value at most , every finite knapsack entry has magnitude at most , so arithmetic bit lengths are . Finite coin counts are at most , because every coin has value at least one. Treat infinity as a separate flag. Comparisons, additions, indices and input storage must be charged according to the representation; a table-entry count alone is not a constant-time guarantee for unbounded integers.
Why an optimum exists without a greedy rule
For the 0–1 problem there are only finitely many subsets, so the maximum exists even when some values are negative. For coin change, any representation of amount has at most coins because each denomination is at least one; there are finitely many possible sequences of that bounded length. If any representation exists, a minimum count is therefore attained. The recurrence depends on these extrema and a complete case split, not on a claim that a locally best first choice can be extended to a global optimum.
Worked examples
Worked example 3.6.6
(A 0–1 optimum and its witness)
Take weights , values and capacity six. Items one and three fit exactly and have total value eleven. Items one and two have value nine; items two and three exceed capacity, as does the triple. No singleton does better, so the optimum is eleven. Tracing the full table can return indices one and three.
Worked example 3.6.7
(Largest coin first can lose)
With denominations one, three and four and target six, the largest-coin rule takes four, one, one: three coins. The table gives and hence using two threes. One coin cannot have value six because six is not a denomination, so . This counterexample does not say that greedy fails for every denomination system.
Worked example 3.6.8
(A divisible target can still be unreachable)
With denominations four and six, the greatest common divisor is two, but target two cannot be formed by nonnegative copies. The table has and . Divisibility by the gcd is necessary for a representation but is not sufficient for a particular small nonnegative target.
Common mistakes and scope
Common mistake
(An at-most capacity is not an exact target)
allows unused capacity. With one item of weight two and value five and capacity three, . If the base row is set to impossible except at capacity zero, the table instead asks for weight exactly three, which this item cannot meet. Choose the base row that matches the problem being solved.
Common mistake
(A sentinel is not a coin count)
Representing impossibility by a large finite number turns into , which can be compared, overflow, or be printed as if it were a count. Test for impossibility before adding one, keep infinity as a separate flag, and report no representation instead of backtracking from it.
Common mistake
(An optimal value is not a witness)
The number does not name a subset, and several subsets may tie. A recovered answer must list the chosen items or coins and must check that their total is the table entry; with only one compressed row, that requires stored choices.
We have proved exact discrete optimization for the two stated models. No general greedy theorem, polynomial bound in binary input length, floating-point error guarantee, or formula for the number of optimal solutions follows. Zero or negative denominations and zero-weight items require separately specified models and are excluded here.
Summary
A dynamic program starts with a state whose meaning includes all relevant restrictions. The case split yields a recurrence; an induction and a dependency-respecting order prove that the table realizes it. Stored predecessor information then turns an optimal value into a verifiable selection or coin list, while the numeric range explains the pseudopolynomial cost.
Exercises
Quick check
(Items have weights and values . For capacity five, find the optimal value and a subset attaining it. Why does capacity zero have value zero?)
Solution · Answer
Items one and two have total weight five and value nine. Item three alone has value seven; the other pairs and the triple exceed capacity. Thus nine is optimal, witnessed by indices one and two. At capacity zero every positive-weight item is excluded, so the empty subset gives value zero.
Quick check
(A single 0–1 item has weight two and value three. At capacity four, what do downward and upward in-place passes return, and which is correct for the stated model?)
Solution · Answer
The downward pass returns three: when it computes capacity four, the old capacity-two entry is still zero. The upward pass writes three at capacity two first and incorrectly uses it again to produce six at capacity four. Three is the correct 0–1 optimum; six uses the same item twice.
Quick check
(Use denominations four and six. Find , and , and recover a minimum representation when one exists.)
Solution · Answer
The empty list gives . Neither denomination fits target two, so . Two four-coins form eight, and no one coin does, hence with witness four plus four.
Quick check
(If the capacity is , why does a table with one entry per capacity not yield a polynomial bound in the bit length ? What additional data does full-table backtracking use?)
Solution · Answer
The capacity requires only binary digits, while the table has capacity positions. Its length is exponential in , so this bound is not polynomial in the binary input size. Full-table backtracking compares the current entry with the preceding row and, when necessary, records inclusion and moves to the smaller-capacity preceding-row state.