找到所需的最少数量的硬币,可以从1到99美分进行任何更改

Question

最近我挑战我的同事写一个算法来解决这个问题:

找到所需的最少数量的硬币,可以从1到99美分进行任何更改.硬币只能是硬币(1),镍币(5),硬币(10)和四分之一(25),你必须能够使用这些硬币从1到99(以1美分为增量)制作每个值.

然而,我意识到我自己并不知道如何在不检查每种可能的硬币组合的情况下自己做到这一点.必须有一种更好的方法来解决这个问题,但我不知道这种类型的算法的通用名称会被调用,除了查看每个解决方案之外,我无法找到简化它的方法.

我想知道是否有人能指出我正确的方向,或提供更有效的算法.

Answer 1

您正在寻找的是动态编程.

实际上,您不必为每个可能的值枚举所有可能的组合,因为您可以在之前的答案之上构建它.

你的算法需要带2个参数:

• 这里列出了可能的硬币值 [1, 5, 10, 25]
• 要覆盖的范围,这里 [1, 99]

目标是计算此范围所需的最小硬币集.

最简单的方法是以自下而上的方式进行:

Range     Number of coins (in the minimal set)
          1   5   10   25
[1,1]     1
[1,2]     2
[1,3]     3
[1,4]     4
[1,5]     5
[1,5]*    4   1             * two solutions here
[1,6]     4   1
[1,9]     4   1
[1,10]    5   1             * experience tells us it's not the most viable one :p
[1,10]    4   2             * not so viable either
[1,10]    4   1   1
[1,11]    4   1   1
[1,19]    4   1   1
[1,20]    5   1   1         * not viable (in the long run)
[1,20]    4   2   1         * not viable (in the long run)
[1,20]    4   1   2

这有点容易,在每一步我们都可以通过添加至多一枚硬币,我们只需要知道在哪里.这归结为这样一个事实,即范围[x,y]包含在内,[x,y+1]因此最小集合[x,y+1]应该包括最小集合[x,y].

你可能已经注意到,有时会有犹豫不决,即多组具有相同数量的硬币.在这种情况下,只能稍后决定应该丢弃哪一个.

应该可以改善它的运行时间,我注意到添加一枚硬币通常可以让你覆盖你添加硬币的范围更大的范围,我想.

例如,请注意:

 [1,5]    4*1  1*5
 [1,9]    4*1  1*5

我们添加镍来覆盖,[1,5]但这让我们[1,9]免费!

但是,在处理令人难以置信的输入集[2,3,5,10,25]时[2,99],我不确定如何快速检查新集所涵盖的范围,或者实际上更有效.

Answer 2

你可以很快找到一个上限.

说,你需要四分之三.然后你只需用其他硬币填写"空白"1-24,26-49,51-74,76-99.

平凡的是,这将适用于2角钱,1个镍币和4个便士.

因此,3 + 4 + 2 + 1应该是您的硬币数量的上限.每当您的蛮力算法超过thta时,您可以立即停止搜索更深层次.

对于动态编程的任何目的,搜索的其余部分应该足够快.

(编辑:按照Gabe的观察固定答案)

Answer 3

你需要至少4便士,因为你想要改变4,你只能用便士做到这一点.

拥有超过4便士不是最佳选择.而不是4 + x便士,你可以有4个便士和x个镍 - 它们至少跨越相同的范围.

所以你只有4便士.

您需要至少1个镍,因为您希望获得5作为变化.

含镍超过1是不理想的.而不是1 + x镍,你可以有1个镍和x硬币 - 它们至少跨越相同的范围.

所以你只有1镍.

你需要至少2角钱,因为你想获得20.

这意味着你有4便士,1镍和至少2角钱.

如果您的硬币少于10个,那么您将少于3个季度.但是,你可以使用所有硬币获得的最大可能变化是4 + 5 + 20 + 50 = 79,还不够.

这意味着你至少有10个硬币.托马斯的回答表明,事实上如果你有4便士,1个镍,2个角钱和3个季度,一切都很好.

Answer 4

我今天一直在学习动态编程,结果如下:

coins = [1,5,10,25]
d = {} # stores tuples of the form (# of coins, [coin list])

# finds the minimum # of coins needed to
# make change for some number of cents
def m(cents):
    if cents in d.keys():
        return d[cents]
    elif cents > 0:
        choices = [(m(cents - x)[0] + 1, m(cents - x)[1] + [x]) for x in coins if cents >= x]

        # given a list of tuples, python's min function
        # uses the first element of each tuple for comparison
        d[cents] = min(choices)
        return d[cents]
    else:
        d[0] = (0, [])
        return d[0]

for x in range(1, 100):
    val = m(x)
    print x, "cents requires", val[0], "coins:", val[1]

动态编程真的很神奇.