The [change-making problem](http://en.wikipedia.org/wiki/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?



When does the greedy change-making 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> .


