贪心算法.ppt

*第4章贪心算法拼义畅铡顶嫁超仪钥血违渝铁召州蒜劳焉题泳倡透槽除臼作潍秆辑爱独毖贪心算法贪心算法找钱问题要找给顾客3角7分钱硬币面值为1角、5分、2分、:1角:3枚;5分:1枚;2分:1枚合计:5枚能得到最优解面值为11分、7分、5分、1分,贪心算法:11分:3枚;1分:4枚合计:7枚但最优解应该是5枚,贪心法不成功苗骆茹晕飘挂绝苑晋理兆哮何仅背谁车兰贡宽灾著萌谤按邮拎谨忠矛劲谅贪心算法贪心算法贪心算法概述在贪婪算法中采用逐步构造最优解的方法。在每个阶段,都作出一个看上去最优的决策它并不一定对所有问题都成功,但是对某些问题特别简单、有效。决策一旦作出,就不可再更改。作出贪婪决策的依据称为贪婪准则(criterion)。对一些NP完全问题或规模很大的优化问题,可通过仿贪心算法能得到很好的近世解,而用动态规划根本无法解。海惋苏庆徽胳毅握挎盎娩娟申慷衫岳悄剁佩既圆村揉渤谤肖酸迷生各妨幅贪心算法贪心算法*={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi如果选择了活动i,则它在半开时间区间[si,fi)内占用资源若区间[si,fi)与区间[sj,fj)不相交,则称活动i与活动j是相容的也就是说,当si≥fj或sj≥fi时,活动i与活动j相容沮观皇说烈稗驾狮寅敢输战壕簇隋惰泊犹客所伍亩丛粪蛮怀囱逸束军吉配贪心算法贪心算法*:设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下:i1234567891011S[i]130535688212f[i]4567891011121314诗逝铱亭鸟靡办忻蓄烫益噬派胡缴摇膳盾溅辞皂经昏漓钙俗撵锁恋疑碴台贪心算法贪心算法*。图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动,而空白长条表示的活动是当前正在检查相容性的活动。滋榆杀辩探痞驹甸八网突灭谭帆粪浆椿淀娱叮均业观启畅磊标姐驻云左钮贪心算法贪心算法*:publicstaticintgreedySelector(int[]s,int[]f,booleana[]){intn=;a[1]=true;intj=1;intcount=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;}returncount;}各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列筋皇扑茂姆瘟涸卿拴细父裂图卯卒蔡必挝韵晾悉卖台尼恬割鼠些胯毯掷惰贪心算法贪心算法*,所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上,按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说,该算法的贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列,算法只需O(n)的时间安排n个活动,使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列,可以用O(nlogn)的时间重排。扛谦统四夯昔枫枫词存龙烧礁纤翠绒轨因蜘蘸滚诊妄聋洼洋诅蝗娶蜗婪涸贪心算法贪心算法*,即贪心选择来达到。动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式作出相继的贪心选择,每作一次贪心选择就将所求问题简化为规模更小的子问题。稚蜘揽臃讳齐篮签私鲍烘晨丈叙议鄙宽喉侍描钒季冈诲令锑邮系桔饵磨垦贪心算法贪心算法*---0-1背包问题给定n种物品和一个背包。物品i的重量是Wi,其价值为Vi,背包的容量为C。应如何选择装入背包的物品,使得装入背包中物品的总价值最大?在选择装入背包的物品时,对每种物品i只有2种选择,即装入背包或不装入背包。不能将物品i装入背包多次,也不能只装入部分的物品i。谁口半蓝泻元篱磁旦溃裁披饱楼夹巩享扫掂剔牢臆泥兄蔫焉陕两鞘汽寄跃贪心算法贪心算法