# Greedy algorithm to make change “getting stuck”

I am thinking of the greedy algorithm for making change: basically take the largest denomination until you get within one largest denomination, take next denomination etc.

This algorithm works for most currencies to simplify making change. Of course, not all currencies conceivable yield optimal solutions with the greedy algorithm: for example if we have coins of denomination 25, 9, 4, 1, then the optimal solution for 37 dollars is 25,4,4,4 rather than the greedy 25,9,1,1,1.

However, in this case the greedy algorithm still works in the sense that it does find a viable solution. If we remove the 1-dollar coin, then 37 dollars would go 25,9, and then get stuck.

But in this case, we can't represent 2 dollars, and many other integers. So my conjecture is:

If there is a case where the greedy algorithm for making change fails to produce a solution, then there are non-trivial cases where no solution exists.

-