贪心算法详细讲解（沉淀中）
文章目录
- 1. 什么是贪心算法？（贪婪+鼠目寸光）
- 经典例题
- 1.1.1 找零问题
- 1.1.2最小路径和
- 1.1.3 背包问题
- 2.贪心算法的特点
- 2.1 证明例1
- 3.学习贪心的方向
- 心得体会
1. 什么是贪心算法？（贪婪+鼠目寸光）
贪心策略：解决问题的策略局部优先 -> 全局优先。
贪心策略：
1.把解决问题的过程分为若干步；
2.解决每一步的时候，都选择当前看起来“最优的”解法；
3.“希望”得到全局最优解。
经典例题
1.1.1 找零问题
1.1.2最小路径和
1.1.3 背包问题
2.贪心算法的特点
（1）贪心策略到的提出
1.贪心策略的提出是没有标准及模板的。
2.可能每一道题的贪心策略都是不同的
（2）贪心策略的正确性
因为有可能“贪心策略”是一个错误的方法；
正确的贪心策略，我们是需要“证明的”。
常用的证明方法：数学中见过的所有证明方法。
eg:
1.错误的比较好证明，在例2,3中：
例2：
绿色路径和：1+3+1+1+1=7，比10小，所以这里的贪心策略是错误的。
例三:
这里用2个2号，价值是14 ，比13 大，所以这里的贪心策略是错误的。
2.1 证明例1
3.学习贪心的方向
遇到不会的题放平心态。
1.前期学习的时候，把重点放在贪心的策略上，把这个策略当成经验吸收。
2.如何去证明？
心得体会
以上内容就是贪心算法的重点内容，如果想深入学习，那就多做练习，学习不同的关于贪心算法的习题，提升自己。喜欢博主的，可以一键三连，支持博主！！！！