找零货币问题

在美国,就像在大多数国家一样,给任何总数的零钱最好的方法是使用一个贪婪的策略——找到面额最大但少于总数的硬币,给其中一个,然后重复。例如,在美国,支付给一个人 97 美分的现金,照此策略 会得出找零 50*1 + 25*1 + 5*2 + 1*2 的方法给出的硬币总数最少

然而,也有可能出现这种贪婪策略并不总是适用的硬币系统。例如,在一个奇怪的国家里,居民们出于某种奇怪的原因,决定使用 1、12、14、63 的面值。假设你需要返还 24 美分。最好的方法是返还 2 枚 12 美分的硬币。然而,在贪心策略下,总是选择面额小于总数的最大硬币,你会选择一个 14 美分的硬币和 10 个 1 美分的硬币,总共 15 个硬币。

我有个疑问:在货币面值满足哪些条件的时候,贪心法总是能得到硬币数量最少的一种方案?充分或必要条件都行。

1、4、5、10 付 8 , 5 1 1 1 或 4 4

我的假设是在最大(但小于要付)的面值大于要付的钱数的一半时,如果有较小面值与要付的钱数不互质,就会发生这种情况

似乎是正确的,但是怎么证明呢?而且这个假设似乎只在存在面值为 1 的硬币的情况下成立

变成子问题? 5 付 8 到 1 付 3 。4 付 8 到 4 付 4 。这种性质具有传递性,18 会导致 10 付 18 到 1、4、5 付
8