【贪心】----找零钱问题
一、找零钱问题
例题1:
有 1 元,5元,10元,20元,100元,200元的钞票无穷多张。现在使用这些钞票支付X元,最少需要多少张钞票。
X = 628
最佳支付方法:
3张200块的,1张20块的,1张5块的,3张1块的
共需3+1+1+3 = 8张
直觉告诉我们:尽可能多的使用面值较大的钞票!
贪心法: 遵循某种规律,不断贪心的选取当前最优策略的算法设计方法。
分析:面额为1元、5元、10元、20元、100元、200元,任意面额是比自己小的面额的倍数关系。 所以当使用一张较大面额钞票时,若用较小面额钞票替换,一定需要更多的其他面额的钞票!
代码实现:
为何这么做一定是对的?
面额为 1元,5元,10元,20元,100元,200元,任意面额是比自己小的面额的倍数关系。
所以当使用一张较大面额钞票时,若使用较小面额钞票替换,一定需要更多的其他面额的钞票。
例如:
5=1+1+1+1+1
10=5+5
20=10+10
100=20+20+20+20+20
200=100+100
故:当前最优解即为全局最优解,贪心成立。
例题2:
有1元,5元,6元的纸币,现在用这些钞票支付K元,至少多少张纸币?
经我们分析,这种情况是不适合用贪心算法的,因为我们上面提供的贪心策略不是最优解。比如,要支付10元的话,按照上面的算法,至少需要1张6元的,4张1元的,而实际上最优的应该是2张5元的。
例题3:假设1元、2元、5元、10元、20元、50元、100元的纸币分别有a,b,c,d,e,f,g张。现在要用这些钱来支付m元,至少要用多少张纸币?如果能支付输出最少支付的张数,如果不能支付,输出-1。
考虑一下,如果不同面值的钞票数量有限制,能不能直接用贪心算法。
扫描二维码推送至手机访问。
版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。