A Polynomial-time Algorithm for the
Change-Making Problem
David Pearson
TR 94-1433
June 1994
Department of Computer Science
Cornell University
Ithaca, NY 14853-7501
A Polynomial-time Algoritlim
for the Change-Making Problem
David Pearson
Computer Science Department
Cornell University
Ithaca, New York 14853, USA
pearson?cs . cornell . edu
June 14,1994
Abstract
The change-makin? problem is the problem of representing a given value with the
fewest coins possible from a given set of coin denominations. To solve this problem
for arbitrary coin systems is NP-hard [L]. We investigate the problem of determining
whether the greedy algorithm always produces the optimal result for a given coin
system. Chang and Gill [CGj show that this can be solved in time polynomial in the
size of the largest coin and in the number of coins. Kozen and Zaks [KZj give a more
efficient algorithm, and pose as an open problem whether there is an algorithm to solve
this problem which is polynomial in the size of the input.
In this paper, we will derive such an algorithm. We first obtain a characterization
of the smallest counterexarnple (if there is one) for which the greedy algorithm is not
optimal. We then derive a set of 0(n2) possible values (where n is the number of
coins) which must contaln the smallest counterexample. Each can be tested with 0(n)
arithmetic operations, giving us an 0(n3) algorithm.
1 Introduction
In the change-making problem, we are given a finite set of coin denominations and an un-
limited supply of coins in each denomination. We want to represent a given value with the
fewest coins possible. The problem of determining the optimal representation in general is
NP-hard [GJ, KZ]. However, in almost all coin systems in use in the world, the problem
can be efficiently solved by the greedy algorithm. This algorithm repeatedly takes the largest
coin whose value is no larger than the remaining amount. For general systems, the greedy
algorithrn is not always optimal. With the coin system 1,3,4, for example, the value 6 will
be represented by the greedy algorithm as 4+ltl, but the optimal representation, 3+3, uses
one coin fewer.
The English system in use before 1971 (when decimal currency was introduced) was an
example of a "natural" coin system for which the greedy algorithm was not optimal. The
coin denominations were (in units of a penny) ?21, 1, 3, 6, 12 (shilling), 24 (fiorin), 30 (half-
crown), 60 (crown), and 240 (pound). 48 pence would be represented as 30+12+6 by the
greedy algorithm, while the minimal representation is 24+24 (two fiorins). The picture was
further complicated by an obsolete coin, the Guinea, with a value of 21 shillings.
In this paper, we will investigate the problem of determining, for a given coin system,
whether the greedy algorithm always yields the optimal representation.
Definition 1 A coin system is a finite set of positive integers, ci > c2 > ... > c?. We
will assume that the smallest COin, C?, has value 1, since otherwise not all values would be
representable. Let C be the n-vector (c1,c2,... , Cn?1, cn). A representation in C of a non-
negative integer x is an n-vector V of non-negative integers such that V C = x, where V C
denotes the inner product of V with C, ?,?--Hi Vj4. The size V of a representation V is the
number of coins in it, i.e. V (1,1,.,1).
Note that we write the n-vectors with the higher coin denominations first. The leading
terms of the representation vectors are then the most significant terms, as they are in po-
sitional number systems, or car odometers. The greedy algorithm has a particularly simple
relationship with the lexicographic ordering on the representation vectors.
Definition 2 Forn-vectorsU = (u1,u2,...,u?) andV = (V1,V2,...,Vn), write U <V if U
lexicographically precedes V, i.e. if for some i: 1 < i < n, u? < Vj and for all j: 1 < j < i,
Vj = v?. The greedy representation of x, denoted by G(x), is the lexicographically greatest
of all the representations of x.
Notice that if x <y, then U = G(x) + (0,?.... , 0, y --H x) is a representation for y. Clearly
C(x) <U. By the definition of G(y), we know that U < G(y), so G(x) <G(y). The greedy
representation, in other words, has the nice property of preserving order.
For a given value x, there may be several representations with the same size, including
the minimum size. We would like to choose a unique representative of all the minimum-size
representations.
Definition 3 The minimal representation of x, denoted by M(x), is the lexicographically
greatest of all the representations of x of minimum size. We call the coin system C canonical
if G(x) = M(x) for all x.
It is not immediately clear whether there is a finite process to show that a coin system
is canonical, since there are infinitely many values x to test. However, Chang and Gill [CG]
show that if no counterexample exists for which G(x) # M(x) in a certain finite set, then
no counterexample exists. The size of this set is polynomial in the value of the largest coin
c1, in the worst case 0(c13). Kozen and Zaks [KZ] show that the smallest counterexample
w (if there is one) must lie in the range Cn?2 < w < c1 + c2. This gives a set of candidates
whose size is linear in c1, and they give an O(nci) algorithm for testing whether the system is
canonical. This time bound is still potentially exponential in the size of the input, however.
2
They give another algorithm which takes time polynomial in log(ci) for any fixed number
of coins, but exponential in the number of coins. They leave it as an open problem whether
an algorithm exists which is polynomial in the size of the input.
It is NP-hard to decide, for an arbitrary coin system, whether the greedy algorithm is
optimal for a specific value x [KZ]. Answering the same question for all x seems intuitively
harder, but is actually easier. The smallest counterexample is much easier to test than an
arbitrary one, and it has a particular structure which will make it easy to find.
In this paper, we obtain a set of possible counterexamples which is polynomial in the
number of coins in the system and independent of the sizes of the coins. This will lead to a
true polynomial-time algorithm.
2 A Polynomial-time algorithm
In this section, we will characterize the smallest counterexample, if there is one, and derive
a small (0(n2)) set of candidates that must include the smallest. As a preliminary, we first
need to establish some facts about minimal and greedy representations.
For two vectors U and V, we will say that U C v if each element flj of U is less than or
equal to the corresponding element Vj of V. Equivalently, v = U + D for some vector D of
non-negative integers. If V is a representation of x, then U is a representation of the number
x --H D C <x. It is a surprising fact that if v is a greedy or minimal representation, then
U is also.
Lemma 1 Call U greedy if U = G(U C), and minimal if U = M(U C). Then
(a) if U C V and V is greedy, then U is greedy
(b) if U C V and V is minimal, then U is minimal
Proof. For (a), note that vector addition preserves lexicographic order:
A < B? A+D <B+D
Let U' be any representation of U C. Then
- c
c
U'.c			U
(V - U+U') C = V
V-U+U' < V
Ul < U
by linearity
since V greedy (and V --H U non-negative)
since addition is order-preserving
Thus U is greedy, since it is the lexicographically greatest representation of U
For (b), define A E B if IA > IBI or (IA = IBI and A < B). Then the minimal
representation is the greatest under E. Addition is again order-preserving with respect to
E. The above proof is valid if we substitute E for <. [Zi
3
Now suppose that C is not canonical. Let w be the smallest counterexample, i.e. the
smallest element such that G(w) $ M(w). We will characterize w, and show that it must
be one of 0(n2) candidates. The fact that w is the smallest counterexample makes it easy
to compute M(w), giving us a polynomial-time test.
One important fact about w is that the sets of nonzero entries in G(w) and M(w) are
disjoint. If this were not true, if both were nonzero in position k, for example, then we could
subtract 1 from the kth position in both G(w) and M(w) to get two new vectors, which
would be the greedy and minimal representations of w --H Ck, by Lemma 1, contradicting the
minimality of w.
Let M(w) = (m1,m2,... , m?), and let i and j denote the first and last nonzero entries
in M(w) respectively, i.e. m? $ 0 and mj $ 0, and mk = 0 for 1 <k < i and j <k < n.
Note that M(w) < G(w) by the definition of G, but since they do not share any nonzero
entries, G(w) must have a zero in position i and be nonzero in some earlier position. This
means in particular that i> 1.
We can now characterize M(w) in a precise way. The following theorem shows a close
similarity between M(w) and G(c??i --H 1).
Theorem 1 M(w) agrees with G(c??i --H 1) in entries 1 through j --H 1, and is one greater in
entry j. The remaining entries mj+i,... , m? are all zero.
Proof. Recall that G(w) must have a zero in position i and a nonzero entry in some
earlier position. This means that w > c??1. On the other hand, subtracting one from the
jth entry in M(w) results in a valid minimal representation for w --H c? (by Lemma 1) which
must also be the greedy representation, since there are no smaller counterexamples. This
representation has no coin larger than c?, so w --H c? <c??1. Thus we get the following bounds:
W --H < Cj?1 < W			(1)
Let V = (vi,v2,. .. ,Vn) = G(c1?i --H 1). Since Cj?1 --H 1 > Cj, Vj $ 0. This means we can
reduce both Vj and m? by one to get new valid greedy representations &(4-i --H 1 --H ci) and
G(w --H ci). We know from (1) that c??i --H 1 --H Cj < W --H c?, so G(c??i --H 1 --H c?) < G(w --H ci).
Adding back the one in position i won't change their lexicographic ordering, so
V < M(w)			(2)
On the other hand, if we decrease m? by one, we will get a valid greedy representation
G(w --H cj). Since W --H Cj < c??1 --H 1 by (1), we have G(w --H ci) < V. Combining this with (2),
G(w --H ci) < V < M(w). Notice that G(w --H ci) and M(w) differ only in entry j, so if V
differed from them in any position before j, it could not lie between them.
V and M(w) therefore agree in positions 1,2,... ,j --H 1, but V < M(w), so we must have
Vk < mk for some k > j. But since m1+1, m1+2,... , m? are all zero, this could only be true
for entry j: v1 <m1. But G(w --H ci) < V, so m1 --H 1 < v>. The only possible value for m1 is
thus v? t 1. 0
In a fixed coin system, if we know i and j, Theorem 1 allows us to determine w exactly.
There are only 0(n2) possible values of i and j to test, so we have obtained our polynomial-
sized sample set.
4
Notice that Theorem 1 gives us both the candidate w and the corresponding M(w) (which
need be valid only if w is actually the smallest counterexample). To test each candidate in
the set requires generating this potential M(w) and the true G(w), then checking whether
IM(w)I < IG(w)I. This test can be performed in 0(n) time, giving 115 an 0(n3) algorithm
overall.
3 Acknowledgements
I am very indebted to Dexter Kozen for posing this problem, and for sharing some of the
clarity of his mathematical thought. The support of a Fannie and John Hertz Foundation
Graduate Fellowship, and the National Science Foundation under grant CCR-9317320, is
gratefully acknowledged.
References
[CG] Chang, 5. K., A. Gill, "Algorithmic solution of the change-making problem," j. Assoc.
Comput. Mach. 17:1 (January 1970), pp. 113-122.
[GJj Garey, M. R., D. 5. Johnson, Computers and Intractability: a Guide to the Theory of
NP-Completeness. W. II. Freeman, 1979.
[KZj Kozen, D., 5. Zaks, "Optimal bounds for the change-making problem," Theor. Comput.
Sci. 123 (1994), pp. 377-388.
[Lj Lueker, G. 5., "Two NP-complete problems in nonnegative integer programming,"
Report No. 178, Computer Science Laboratory, Princeton University, 1975.
5