贪心找零算法是一种通过选择可用硬币的最高面额来进行找零的算法，直到它达到它试图做出的找零数量。令人惊讶的是，该算法实际上可以以最有效的方式对美国和欧元硬币面额进行更改！
然而，贪心算法有时会因为改变而失败。假设我们有面额 [25,15,1] 并试图赚 31 美分。贪心算法会选择 25,1,1,1,1,1,1（7 个硬币），而 31 美分实际上可以作为 15,15,1（3 个硬币）。
我想知道是否有办法使贪婪算法对包括面额 1 的欧元硬币子集（欧元硬币列表为 1,2,5,10,20,50,100,200）失败。虽然我可以使贪心算法使具有其他值的子集失败，对于欧元硬币的子集，我似乎无法使其失败。
一些资源说，只要最高元素加上最低元素小于第二高元素的两倍（因此在上面的示例中，25 + 1 < 15 + 15），贪心算法就会失败，但是没有办法做到这一点可以用欧元硬币的一个子集。