【贪心算法】简介
1.贪心算法
贪心策略：解决问题的策略，局部最优----》全局最优
（1）把解决问题的过程分成若干步
（2）解决每一步的时候，都选择当前看起来的“最优”的算法
（3）“希望”得到全局最优解
例一：找零问题
只有一张50元，买了4元，如何找零？（店家有[20,10,5,1]）
解答：50-4=46，来凑46
首先找最大的20元，46-20=26
再找最大的20元，26-6=6
再找20元太多了，再找10元太多了，再找5元，6-5=1
再找5元太多了，再找1元，1-1=0
例二：最小路径和
例三：背包问题
背包最大容量：8
| 1 | 2 | 3 | ||
| 体积 | v | 5 | 4 | 1 |
| 价值 | w | 10 | 7 | 1 |
从体积考虑：一直选体积最小的1，选了8个3号物品
从价值考虑：一直选当前可选的价值最高的，1号物品，3个3号物品
按性价比考虑：w/v：2，1.75，1一直选择性价比最高的，1号物品，3个3号物品
2.贪心算法的特点
（1）贪心策略的提出是没有标准和模板的
（2）可能每一道题的贪心策略都是不相同的
3.贪心策略的正确性
因为有可能“贪心策略”是一个错误的方法
正确的贪心策略需要“证明”（数学中的证明方法都可以）
证明：找零问题的正确性
[20,10,5,1]
假设最优解为：A,B,C,D
根据题目可知，能用面额大的尽量用
则B<=1,C<=1,D<=4
假设贪心解为：[a,b,c,d]
最优解为：[A,B,C,D]
因此有：
（1）a>=A
（2）a>A不可能，因为B<=1,C<=1,D<=4，加在一起10+5+1*4=19无法到达20
（3）a=A
（4）b>=B
（5）b>B不可能，因为C<=1,D<=4，加在一起5+1*4=9无法到达10
（6）b=B