Change-making problem

The change-making problem is a family of combinatorial optimization problems concerning the representation of a monetary amount by coins or notes drawn from specified denominations. In its standard optimization form, the input consists of positive integer denominations (C={c_1,\ldots,c_n}) and a target amount (T). The objective is to determine nonnegative integers (x_1,\ldots,x_n) satisfying

[ \sum_{i=1}^{n} c_i x_i=T ]

while minimizing the total number of monetary units,

[ \sum_{i=1}^{n} x_i. ]

The problem is closely related to the integer knapsack problem, integer programming, and the study of numerical semigroups. Its mathematical behavior depends substantially on whether denominations may be used without limit, whether the available inventory is bounded, and whether the objective is optimization, feasibility, or enumeration.

Mathematical formulation

For unlimited inventories, each variable (x_i) may assume any nonnegative integer value. A target is feasible precisely when it belongs to the additive semigroup generated by the denominations. If (g=\gcd(c_1,\ldots,c_n)), divisibility of (T) by (g) is necessary for feasibility. When the normalized denominations have greatest common divisor one, every sufficiently large integer is representable, although smaller amounts may remain unattainable. The largest unattainable amount is the Frobenius number of the denomination set.

The bounded version associates each denomination (c_i) with an inventory limit (b_i), producing the additional constraints

[ 0\leq x_i\leq b_i. ]

This formulation models a cash drawer, vending mechanism, or other finite stock of monetary units. Unlike the unlimited case, divisibility and sufficiently large target size do not establish feasibility because the aggregate value and composition of the inventory impose independent restrictions.

A decision form asks whether an exact representation exists using at most (k) units. The counting form asks for the number of distinct denomination-count vectors representing (T). These formulations share the same basic equation but have different computational properties. Counting combinations also differs from counting ordered sequences, since permutations of the same multiset are identified in the former interpretation and distinguished in the latter.

Dynamic programming formulation

The usual dynamic programming formulation for the unlimited optimization problem defines (M(t)) as the minimum number of units required to represent an amount (t). With (M(0)=0) and infeasible states assigned value (+\infty), the recurrence is

[ M(t)=1+\min_{\substack{1\leq i\leq n\c_i\leq t}}M(t-c_i). ]

The values for amounts below (T) form a directed acyclic dependency structure because each transition decreases the represented amount. Evaluation of all states through (T) requires (O(nT)) arithmetic comparisons and (O(T)) storage in the standard implementation. The dependence on the numeric value of (T), rather than on the length of its binary encoding, makes this a pseudopolynomial-time algorithm.

Richard Bellman’s development of dynamic programming supplied the general mathematical framework in which this recurrence became a standard optimization model. Later treatments identified the same recurrence with a shortest-path problem: each amount is a vertex, and an edge of unit cost connects (t) to (t+c_i) whenever the resulting amount does not exceed the target.

For bounded inventories, the state may incorporate both the represented amount and the denomination layer under consideration. In 1977, You Watanabe expressed the finite-inventory formulation as a layered acyclic graph whose transitions encode the permitted multiplicity of each denomination. The graph formulation separates the existence of exact change from the secondary minimization of the number of units, with infeasible inventories corresponding to the absence of a path terminating at the target state.

Inventory multiplicities can also be encoded through groups whose sizes are powers of two. This representation reduces a bounded integer variable to a logarithmic number of binary choices and connects bounded change-making with the zero-one knapsack problem. The resulting state-space method remains pseudopolynomial because the amount dimension is indexed explicitly.

Greedy change-making

A greedy algorithm repeatedly selects the largest denomination not exceeding the unpaid remainder. This method produces an exact representation whenever the smallest denomination is one, but it does not necessarily minimize the number of units. For denominations ({1,3,4}) and target (6), the greedy representation is (4+1+1), whereas the optimum is (3+3).

A denomination system is called canonical when the greedy representation is optimal for every target amount. Canonicality is a property of the complete ordered denomination set rather than of an individual target. Positional systems in which each denomination is an integral multiple of the preceding denomination are canonical, because exchanging enough lower-valued units for one higher-valued unit never increases the number used. Canonical systems also exist without this divisibility structure.

Dexter Kozen and Shmuel Zaks established finite bounds governing where a counterexample to greedy optimality must occur when one exists. David Pearson subsequently gave a polynomial-time canonicality test based on a restricted family of candidate counterexamples derived from greedy representations. These results convert the universal statement defining canonicality into a finite verification problem whose size is polynomial in the number of denominations.

The canonicality question is distinct from the computation of an optimum for one specified target. A noncanonical currency may still admit optimal greedy representations for most amounts, while a single counterexample suffices to classify the denomination system as noncanonical. The frequency and magnitude of such exceptions are therefore empirical properties separate from canonicality itself.

Computational complexity

When denominations and the target are encoded in binary, the change-making decision problem is NP-complete in its general form and is weakly NP-complete under the usual integer encoding. The dynamic programming bound (O(nT)) is compatible with this classification because (T) may be exponentially larger than the number of bits used to represent it.

The optimization version is correspondingly weakly NP-hard. Its pseudopolynomial algorithm implies that the principal source of worst-case complexity is the magnitude of the numerical input rather than an independently exponential combinatorial structure. Restrictions on the denomination set can alter this behavior. A fixed currency system, for example, removes the denominations from the variable input and permits methods based on periodicity, residue classes, and precomputed shortest paths.

The bounded problem contains additional combinatorial choices because each denomination has a finite multiplicity. Its decision version includes restricted subset-selection problems as special cases. The unlimited problem instead allows repeated use of each value and is closely associated with unbounded knapsack.

Counting exact representations belongs to the domain of counting complexity. The number of unordered representations is the coefficient of (x^T) in the generating function

[ \prod_{i=1}^{n}\frac{1}{1-x^{c_i}} ]

for unlimited inventories. Under bounds (b_i), the corresponding generating function is

[ \prod_{i=1}^{n}\left(1+x^{c_i}+x^{2c_i}+\cdots+x^{b_i c_i}\right). ]

These expressions connect change-making to partition theory and generating functions. They encode the number of feasible denomination-count vectors but do not directly minimize the number of units. A second variable can record unit count when both quantities are required.

Structural interpretations

The unlimited problem admits a residue-graph interpretation based on a selected denomination, commonly the smallest one. Vertices represent residue classes modulo that denomination, while edges represent the addition of other denominations. Shortest-path labels can encode either total value or the number of units, depending on the optimization criterion. The eventual repetition of residue behavior explains why fixed-denomination systems often exhibit periodic or quasipolynomial structure for sufficiently large targets.

From the perspective of linear programming, the continuous relaxation replaces the integer restrictions on (x_i) with nonnegativity constraints. That relaxation generally fails to describe valid change because fractional monetary units can satisfy the target equation with an unrealistically small objective value. The resulting integrality gap reflects the arithmetic structure of the denominations rather than the geometry of a high-dimensional constraint system, since the basic equality contains only one value dimension.

Change-making can also be represented as a minimum-cost flow problem on an amount-indexed network. Each edge adds one denomination and carries a unit cost, while a path from zero to (T) corresponds to an ordered sequence of selected units. Distinct paths may encode the same unordered denomination-count vector, so this network representation is exact for optimization but requires additional conventions when used for enumeration.

Monetary interpretation

Mathematical change-making abstracts away several properties of physical and institutional payment systems. Real inventories may include notes as well as coins, and two units with the same nominal value may differ in physical form without differing in the optimization model. Transaction rules can also permit overpayment followed by returned change, producing a two-sided optimization problem in which units move in both directions.

The minimum-unit objective represents one measurable cost, but it does not incorporate weight, handling time, inventory preservation, or denomination-specific preferences unless these are included as explicit edge costs or objective coefficients. Assigning a cost (w_i) to each denomination changes the objective to

[ \min \sum_{i=1}^{n} w_i x_i, ]

which yields a weighted change-making problem. The unweighted formulation is recovered when every (w_i) equals one.

In currency design, canonicality describes the mathematical interaction between denominations and greedy selection. It does not by itself determine the suitability of a currency system, because the model contains no distribution of transaction amounts and no inventory process. Analyses incorporating such data belong to stochastic optimization and operational models of cash circulation rather than to the classical change-making problem alone.