A greedy change-making algorithm is one that makes change by choosing the highest denomination of coin available until it reaches the amount of change it is trying to make. Surprisingly, this algorithm actually works for making change in the most efficient manner for US and Euro coin denominations!
However, the greedy algorithm can sometimes fail for making change. Suppose we have the denominations [25,15,1] and are trying to make 31 cents. The greedy algorithm would pick 25,1,1,1,1,1,1 (7 coins) while 31 cents can actually be made as 15,15,1 (3 coins).
What I'm wondering is if there's a way to make the greedy algorithm fail for a SUBSET of Euro coins (the list of Euro coins is 1,2,5,10,20,50,100,200) that includes the denomination 1. While I can make the greedy algorithm fail subsets with other values, I can't seem to make it fail for a subset of the Euro coins.
Some resources say that the greedy algorithm will fail whenever the highest element plus the lowest element is less than twice the second highest element (so in the example from above, 25 + 1 < 15 + 15), but there is no way to make this possible with a subset of Euro coins.
Try to make 60 with 1, 20, 50.