修改最小硬币变化

Question

假设你有一张K美元的账单.给出4个有价值的硬币{1,4,6,9}找到硬币的最小数量,其总和为K,当K用二进制表示时,表示输入的长度为log(K)

我尝试过动态编程,但我没弄明白.有没有人知道如何开始解决这个问题？这与背包问题有关,但我无法弄明白.

谢谢.

Answer 1

如何检查硬币数量与K%9的函数关系？然后你可以将它翻译成log(K)的功能.

令K%9 = r,即存在整数n,使得K = 9n + r,并且r在0和8之间,包括0和8.

• r = 0:我们需要n个值为9的硬币,
• r = 1:我们需要n个硬币值9 + 1硬币值1 = n + 1个硬币
• r = 2:我们需要n个硬币值9 + 2个硬币值1 = n + 2个硬币
• r = 3:我们需要(n-1)个值为9的硬币+ 2个值为6的硬币= n + 1个硬币,或者如果K = 3则需要3个值为1的硬币
• 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:我们需要n个硬币值9 + 2个硬币值4 = 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.因此,为了获得K,我们需要值为1或4的(2 + 3j)硬币.现在我们需要证明,如果我们使用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来获得它.瞧!