怎么确定什么时候可以用贪心
请教，一个问题满足什么样的条件才能保证贪心算法可以得出最优解？
在看书的时候遇到一个“找零钱”问题：目标是找67分，面值有25、10、5、2、1，目标是所用硬币数量最少。此问题用贪心可得最优解，即每次拿出不会导致总面值超过目标面值的最大面值：25+25+10+5+2=67。
但是，如果换成目标面值10分，面值种类有7、5、1，那么贪心法就不好用了，因为7+1+1+1=5+5。
想到这里，就想请教大家，一个问题满足什么样的条件才能保证贪心算法可以得出最优解？#笔试题目#
在看书的时候遇到一个“找零钱”问题：目标是找67分，面值有25、10、5、2、1，目标是所用硬币数量最少。此问题用贪心可得最优解，即每次拿出不会导致总面值超过目标面值的最大面值：25+25+10+5+2=67。
但是，如果换成目标面值10分，面值种类有7、5、1，那么贪心法就不好用了，因为7+1+1+1=5+5。
想到这里，就想请教大家，一个问题满足什么样的条件才能保证贪心算法可以得出最优解？#笔试题目#
投递旷视等公司10个岗位 >
查看5道真题和解析
