什么是贪心
- 贪心的本质是选择每一阶段的局部最优，从而达到全局最优；
- 举一个例子：有一堆钞票，可以拿走十张，如果想达到最大的金额，要怎么拿？
- 每次拿最大的，最终结果就是拿走最大数额的钱；
- 每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优；
- 再举一个例子：有一堆盒子，有一个背包体积为 n ，如何把背包尽可能装满？
- 如果还是每次选最大的盒子，就不行了；
- 这时候就需要动态规划，动态规划的问题请看 算法基础🔮 动态规划基础；
什么时候用贪心
贪心并没有固定的套路，唯一的难点就是如何通过局部最优，推出整体最优；
没有固定策略或者套路可以直接判断出用贪心；
最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧；
贪心一般解题步骤
将问题分解为若干个子问题；
找出适合的贪心策略；
求解每一个子问题的最优解；
将局部最优解堆叠成全局最优解；
参考资料
打赏作者
您的打赏是我前进的动力
微信
支付宝
非比较排序🔮 桶排序
上一篇
评论
