# 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.

Non-trivial being, say, removing 1 dollar coins causes $1 to be impossible to represent, but this is considered trivial. I cannot find a counterexample. Is this true? Can we design a currency that would cause the greedy algorithm to completely fail to find a solution without backtracking, yet can represent (almost) all integer amounts of money? • I don't understand. Feb 12, 2014 at 3:38 • The simplest case is just$\{2,3\}$. The greedy algorithm fails for all amounts of the form$3k+1$, but only$1$is not representable as a sum of$2$'s and$3$'s. Feb 12, 2014 at 3:48 ## 2 Answers How about$25,8,3,2$and trying to make$34$? The greedy algorithm gets stuck after$25+8$, but all amounts except$1\$ are solvable.

Well, if $$1 < c_1 < c_2 < .. < c_n$$ are any coin denominations, the greedy would simply fail for $$c_n + 1$$.