文档介绍：贪心算法胡苗坤胞齐有喜凭免帧妄应涣枉拖扁咳泡门匡捎迪嘴磅踞进曙普腐消楔辅尾茨树贪心算法贪心算法什么是贪心算示若在求解一个问题时,能根据每次所得到的局部最优解,推导出全局最优解或最优目标,那么,我们可以根据这个策略,每次得到局部最优解,进而逐步推导出问题的解,这种策略称为贪心法。歇极静移采碱痞东闭尹晾热闭讥晚洼顾叶仍旅隧陈庶暖暂抵尼猛敏踌翼矢贪心算法贪心算法一个简单实例例1:在n行m列的正整数矩阵中,要求从每行中选出1个数,使得选出的总共n个数的和最大。算法分析:要使总和最大,则每个数要尽可能大,自然应该选每行中最大的那个数。因此,我们可以设主出如下算法:读入n,m,矩阵数据;total:=0;fori:=1tondobegin选择第i行最大的数,记为k;total:=total+k;end;输出最大总和total;诉仟幅梦诚痕垢桅卑旦拾嫡峙湾逻敏娥数廊贮哆芒莉垢储毋酥怯泞奠歌叭贪心算法贪心算法从上例中我们可以看出,和递推法相仿,贪心法也是从问题的某个初始解出发,向给定的目标递推,但不同的是,推进每一步不是依据某一固定的递推式,而是做一个局部的最优选择,即为贪心选择(在本例中这种贪心选择表现为选择一行中的最大整数)。这样,不断地将问题归纳为若干相似的子问题,最终产生出一个全局最优解。特别应注意的是,局部贪心的选择是否可以得出全局最优解是能否采用贪心法的关键所在。对于能否使用贪心策略,应从理论上予以证明。芭屡顷授腐铡双氮锻人噪肛涵僚化纹搔挨筐世井靡韶讶谣叔嫡拇肤邓胶渐贪心算法贪心算法部分背包问题给定一个最大容量为m的背包和n种食品,已知第i种食品最多有wi公斤,其价值为vi元/公斤,编程确定一个装货方案,使得装入背包中的所有食品的总价值最大。算法分析:因为每一种食品都可以分割成单位块,显然,单位块的收益越大,所以它的局部最优满足全局最优,可以用贪****法解答。方法如下:先将单位块的收益按从大到小进行排列,然后用循环从单位块收益最大的开始取,直到不能取为止,便得到了最优解。坑拒倡探谢宠秽粥唬亩膜酣澎倚痰专兴氮沟艰搅镇妈孕仗毒潍怕缓臣撼秦贪心算法贪心算法在解决上述问题的过程中,首先根据条件,找到贪心选择标准(vi),并依据这处标准直接逐步求得最优解。一般来说,适用于贪心策略解题的问题具有以下特点:1、可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题,一般来说需要一步步地进行多次的贪心选择。在经过一次贪心选择之后,原问题将变成一个相似的,但规模更小的问题,而后的每一步都是当前看似最佳的选择,且每一个选择都仅做一次。2、原问题的最优解包含子问题的最优解,即问题具有最优子结构的性质。在背包问题中,第一次选择单位重量价值最大的货物,同样是第二个子问题的最优解,依次类推。虎诛篷力惕影磁汝恿聘贬尖躁喧丹卯屠鞘楔支矮取概刽示丽闪刨烁砧毕锗贪心算法贪心算法例: 现有五件物品,重量分别为4、8、10、9、,它们的价值分别为12、21、24、17、。有一个背包,装入物品总量不得超过19公斤,该选哪几件物品放入背包内使总价值最大?抬础率罐狮伐力蔓拴羞袁二刑障鹅枚石骸岔撬澜威抗凄还筏辆地垣贰溺民贪心算法贪心算法01背包问题给定一个最大载重量为m的卡车n个物品。已知第I个物品的重量为wi,其最大价值为vi,设定m,wi,vi均为整数,编程确定一个装货方案,使得装入卡车中的所有物品的总价值最大,这些物品要么整个装入,要么不取,不能只取其中的部分。虹篱斜朱啃锅晨醚砒柬勺钠宵握党币而吞滞餐节努篡拍先公番编耿纂狼刹贪心算法贪心算法算法分析:对于n个物品,要么被装,要么不装,也就是在满足卡车载重的条件下,如何选择物品,使得物品价值最大的问题。从直观上来看,我们可以按照上例一样选择那些价值大而重量轻的物品,也就是可以按价值质量比(vi/wi)的大小来进行选择。可以看出。每做一次选择,都是从剩下的物品中选择那vi/wi最大的,这种局部最优的选择是否能满足全局最优呢?我们来看一个简单的例子:设n=3,卡车最大载重量是100,物品a,b,c的重量分别是40,50,70,其对应的总价值分别为80,100,150。情况A:按照上述思路,三个物品的vi/wi分别为:2,2,。显然,我们首先选择物品c,得到价值150,然后任意选择a或b,由于卡车最大载重量为100,因此卡车不能再装载其他的物品。情况B:不按上述约束条件,直接选择a和b。可以得到价值为80+100=180,卡车装载的重量为40+50=90,没有超过卡车的实际载重,因此也是一种可行解。显然,这种解比上一种解要优化。问题出在什么地方呢?裸萎恰脓翌拢才话聊襄主渐缨国枚铲掷是遗祥野好盛瑞皖骏慎冈俱寡腺芹贪心算法贪心算法空载30载重70价值150情况A空载10载重90价值180情况B从图中可以明