给定一个硬币面额列表,我需要找到获得给定值所需的最小硬币数量。
我的方法使用贪婪算法,
将值除以最大面额,取余数,再除以第二次最大面额,以此类推,直到得到所需值
但是这种方法在某些情况下失败了。
I want to know
- 适用于所有情况的方法
- 为什么贪婪方法失败?
方法失败的例子
硬币面额 (1,3,4,5)
值要求 7
使用贪心方法
(7/5)=1和+2,因为3和4不能使用,所以我们需要使用21的价值硬币。所以总共有3枚硬币。
但是最优值是4+3(2个金币)
对于你所描述的问题有一个经典的解决方案——一种背包问题。可采用动态规划方法求解。要获得清晰的解释,您可以遵循本教程
假设你想得到价值为"2,10€"的硬币,而你得到了价值为2,1,0.50,3 × 0.20的硬币。
贪心总是先取最大的硬币,所以它会选择价值为2的硬币。现在不可能达到2,10,因为你没有价值0.10的硬币,即使你选择1,0.50和3个0.20硬币是可能的。
在这种情况下(就像在大多数情况下一样),我建议您使用回溯,在这种情况下不会失败