# When does the greedy change-making algorithm work?

The change-making problem asks how to make a certain sum of money using the fewest coins. With US coins {1, 5, 10, 25}, the greedy algorithm of selecting the largest coin at each step also uses the fewest coins.

With which currencies (sets of integers including 1) does the 'greedy' algorithm work?

That's a different question, Gerry.

Believe it or not, the answers are different if one is asking (a) given N and a system of denominations D, is the greedy algorithm using D optimal for N? and (b) given a system of denominations D, is the greedy algorithm using D optimal for ALL N?

I think the latter problem is the one that Zachary Vance is asking about.

In that case, it is decidable in polynomial time. See Pearson's article here: http://dl.acm.org/citation.cfm?id=2309414 .

• Oops. ${}{}{}{}$ – Gerry Myerson Oct 4 '14 at 23:44

If you look at pages 4-5 of this paper by Jeff Shallit, it says, "Suppose we are given $N$ and a system of denominations. How easy is it to determine if the greedy representation for $N$ is actually optimal? Kozen and Zaks [4] have shown that this problem is co-NP-complete if the data is provided in ordinary decimal, or binary. This strongly suggests there is no efficient algorithm for this problem."

The reference is D. Kozen and S. Zaks, Optimal bounds for the change-making problem, Theoret. Comput. Sci. 123 (1994), 377–388.