问修正的最小硬币变化

EN

检查硬币的数量作为K%9的函数如何？然后你可以把它转换成log(K)的函数。

设K%9 = r，即存在一个整数n，使得K= 9n + r，r介于0和8之间。

• r=0:我们需要价值9的n硬币，
• r=1:我们需要价值9+1的n枚硬币= n+1硬币
• r=2:我们需要价值9+2的9+2硬币= n+2硬币
• r=3:我们需要(n-1)价值9+2的硬币6= n+1硬币，或价值1的3枚硬币，如果是K=3的话。
• r=4:我们需要n枚价值9+1的硬币，价值4=，n+1，硬币，
• r=5:我们需要n枚价值9+1的硬币，价值4+1的硬币=1= n+2硬币
• r=6:我们需要n枚价值9+1的硬币，价值6= n+1硬币
• r=7:我们需要n枚价值9+1的硬币，价值6+1的硬币=1= n+2硬币
• r=8:我们需要价值9+2的9+2硬币= n+2硬币

证据:对于这个案子，r=0：我们知道我们可以用n个硬币来做。如果我们使用m个硬币，m< n，大于最大值m* 9，9是硬币的最大值。但是9m比K=9n小，所以我们不能用m个硬币来得到K。

对于有r=1，r=3，r=4和r=6的情况，我们知道n个硬币就足够了(9n < K，K是9n +r)，并且我们知道如何使用n+1硬币。

r=2、r=5和r=8的总金额为K，K%3=(9n+r)%3=r%3=2；对于硬币的值，6%3=0和9%3=0，但1%3=1和4%3=1，因此，我们需要在(2+3j)值为1或4的硬币上得到K。现在我们需要证明，如果我们使用n+1硬币，并且至少有2个硬币的值为1或4，我们不能得到K。事实上，n+1硬币的最大值是9*(n-1) + 2*4 = 9n-1，这比K=9n+r小。

最后，对于r=7：假设我们使用n+1硬币。他们都是9，我们得到9*(n+1)，这不是我们想要的。如果其中至少有一个不是9，总价值最多为9n + 6，6是第二最有价值的硬币，这是不够的。因此，n+1是不够的。我们知道怎么用n+2得到它。瞧！

这个问题的典型动态程序把j从0循环到K，每次计算出硬币的最小数量来改变一张j美元纸币。当j=0时，零硬币是最优的。对于另一个j，答案是一个硬币加上j- 1，j- 4，j- 6或j-9的最小值(当这些量是非负的)。对于其他面额，适当地替换1，4，6，9。

要像Yulia V那样导出一个表，就可以证明，对于每一组面额，当K足够大时，最优的变化包括一个最大面额的硬币。循环j从0上升，寻找异常，其中异常是当制作j-9美元所需的硬币比j多时(或j-9为负)。在连续9个非异常之后，不可能有更多的异常。(对于其他面额，以最大面额代替上述案文中的9)。

对K 36使用动态规划，其余部分使用9s，其中36 = lcm(1，4，6，9)。