理解贪心算法
从前有一只鹅，一天可以下两个金蛋，但是直接杀了他可以拿到二十个金蛋。
问在21天内拿到尽量多的金蛋？
动态规划。。前20天不杀，最后一天杀。40个
贪心。。第一天下蛋，得到一个金蛋
第一天杀，得到20个金蛋 选择第一天杀
得到20个金蛋。
在同样的条件，同样的选择下，贪心更偏爱局部最优，动态规划则按照某种规律寻找全局最优。主要表现在同样的选择。
而把题目改成1天
那么动态规划也会选择第一天杀。
所以在某些情况下贪心算法也可以得到最优解，而在解决现实问题中，往往很难找到最优解，所以贪心也算是一种对现实的妥协。只要结果暂时可以接受，那也是可以用的。毕竟事物都是慢慢发展的。。。。。
赞 (0)