performance - 找到可以从 1 到 99 美分的任何零钱所需的最少硬币数

Question

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

Find the least number of coins required that can make any change from 1 to 99 cents. The coins can only be pennies (1), nickels (5), dimes (10), and quarters (25), and you must be able to make every value from 1 to 99 (in 1-cent increments) using those coins.

但是，我意识到如果不检查所有可能的硬币组合，我自己实际上并不知道如何做到这一点。必须有更好的方法来解决这个问题，但我不知道这种算法的通用名称是什么，除了查看每个解决方案之外，我想不出一种方法来简化它。

我想知道是否有人可以为我指明正确的方向，或者提供一种更高效的算法。

Answer 1

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

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

您的算法需要采用 2 个参数:

• 可能的硬币值(value)列表，这里是 [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] 时，我不确定如何快速检查新集合覆盖的范围，否则实际上会更有效率。