算法设计与分析 课件 6.2-贪心法-基本原理

信息工程大学算法设计与分析贪心法—基本原理国家级实验教学示范中心计算机学科组规划教材算法设计与分析Python案例详解微课视频版求解最优化问题的过程包含一系列步骤每一步都有多种选择贪心法做出在当前看来最好的选择希望通过局部最优选择达到全局最优

贪心算法总是做出当前最好的选择，不是从整体上考虑问题的最优性，它所做出的选择只是在某种意义上的局部最优选择，所以有时贪心算法的解不一定是整体最优解。对于一个给定的问题，通常有多种贪心选择策略，但不是每种策略都可以得到最优解。因此，选择能产生问题最优解的贪心选择策略是使用贪心法的核心问题。有些问题的贪心选择策略比较直观，有些问题则需要深入分析。适合用贪心法求解的问题一般具有两个重要性质：贪心选择性质（Greedy-choiceproperty）每步所做的贪心选择最终可求得问题的最优解最优子结构性质（Optimalsubstructure）问题的最优解包含子问题的最优解1.证明所求解的问题具有最优子结构性质。2.证明所求解的问题具有贪心选择性质（证明每一步所做的贪心选择最终导致问题的整体最优解）。反之，只需要举出一个反例，就可以说明贪心法不正确。贪心算法和动态规划算法都要求问题具有最优子结构性质，这是它们的共同点。

但对于具有最优子结构的问题：选用贪心法还是动态规划求解?能用动态规划求解的问题是否也能用贪心法求解?

给定n个物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?物品i要么全部装入要么不装。0-1背包问题：与0-1背包问题不同的是，在选择物品i装入背包时，可以选择物品i的一部分xi，不一定要全部装入背包，0≤xi≤1。部分背包问题：选择题。你觉得以下哪种贪心选择策略可以得到部分背包问题的最优解？A.重量轻的物品优先装入B.价值大的物品优先装入C.单位重量价值大的物品优先装入D.以上都不对部分背包问题的贪心选择策略有：1.重量轻优先2.价值大优先3.单位重量价值大优先反例：n=2，c=5，w=(2,5)，v=(2,10)，优先装入物品1，再装入物品2的一部分，得到价值总和为8；而把物品2全部装入背包得到价值10是最优解。反例：n=2，c=5，w=(2,5)，v=(6,10)，优先装入物品2，得到价值10；而先全部装入物品1再装入物品2的一部分，得到价值12是最优解。错误错误该策略综合考虑到物品重量和价值两个因素，可以得到最优解。正确对物品按单位重量价值vi/wi从大到小排序；根据贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包；若背包内的物品总重量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包；依此策略进行下去，直到背包装满为止。贪心法求解部分背包问题的步骤：贪心法求解部分背包问题的代码：voidKnapsack(intn,floatc,float*v,float*w,float*x){knap_sort(n,v,w);/*按单位重量价值从大到小排序*/for(i=1;i<=n;i++)x[i]=0;floatleft=c;/*逐一判断每件物品*/for(i=1;i<=n;i++){if(w[i]>left)break;x[i]=1;left-=w[i];}if(i<=n)x[i]=left/w[i];/*可能有部分装入的物品*/}时间复杂度为O(nlogn)例：c=7,(w1,w2,w3)=(3,4,5),(v1,v2,v3)=(5,6,10)。贪心法得到的最大价值为10，装入物品3。实际最大价值为11，装入物品1和2。贪心法不能正确求解0-1背包问题。原因：无法保证最终能将背包装满，部分闲置的背包空间使背包的单位空间的价值降低。在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再做出最好的选择。由此就出现许多互相重叠的子问题。0-1背包问题可用动态规划求解。贪心法不能正确求解0-1背包问题。动态规划贪心共同点最优子结构性质不同点重叠子问题贪心选择性质求解思路对所有选择比较后决定最优的只考虑一种选择，因而更高效解题过程通常采取自底而上，从小问题推出大问题从大问题逐步求解，不断减少问题规模，直至结束代码结构