找到可以进行1到99美分的零钱的最少数量的硬币
最近，我要求我的同事编写一种算法来解决此问题：
找到可以进行1到99美分的零钱的最少数量的硬币。硬币只能是几美分（1），镍币（5），角钱（10）和四分之一（25），并且您必须能够使用这些硬币将1到99的每个值（以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]因此for的最小集[x,y+1]应包括for
的最小集[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]，我不确定如何快速检查新集所覆盖的范围，否则实际上效率更高。
以上是 找到可以进行1到99美分的零钱的最少数量的硬币 的全部内容， 来源链接： utcz.com/qa/403538.html
