设计一个贪婪算法,使得找的钱币张数最少
时间: 2023-06-01 11:04:41 浏览: 127
贪婪算法设计
3星 · 编辑精心推荐
假设有一组钱币面值为{1, 5, 10, 50, 100},要找零100元。可以按照以下贪心策略:
1. 优先选择面值最大的钱币,即先选100元,如果不够再选50元,以此类推。
2. 如果选择了某种面值的钱币,且还有剩余,继续选择该面值的钱币,直到剩余金额无法再选择该面值的钱币为止。
按照这个贪心策略,找零100元的最少钱币数为2张50元。如果没有50元的钱币,则需要找5张20元或者10张10元,钱币张数更多。
阅读全文