【贪心算法】简介

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