第三讲贪心法

第三讲贪心法1.贪心法的基本思想贪心法是从问题的某一个初始解出发,向给定的目标推进。但不同的是,推进的每一步不是依据某一固定的递推式，而是做出一个在当前看来是最佳的贪心选择,不断地将问题实例归纳为更小的相似的子问题,并期望通过所做的局部最优选择产生出一个全局最优解。2.使用贪心法求解问题时要具备的条件(1)所求解的问题应当具有贪心选择性质。即所求解的问题的整体最优解可以通过一系列的局部最优解得到。所以局部最优解是指在当前的状态下做出的最好选择。(2)所求解的问题应当具有最优子结构性质。当一个问题的最优解包含着它的子问题的最优解时，称此问题具有最优子结构。3.使用贪心法的注意事项(1)要判断一个问题是否可以通过贪心算法得到最优解，是一件比较困难的的事情。这需要比较复杂而严格的数学证明。(2)贪心算法不是对所有问题都能得到整体的最优解，但是实际应用中的许多问题都可以使用贪心算算得到最优解。(3)即使使用贪心算法不能得到问题的最优解，但是最终结果也是最优解的很好的近似解。因此，在解决一般性问题时，使用贪心算法是一种不错的选择。4.贪心法的优点与不足优点：算法思想简单，易于实现，效率高。不足：使用贪心算法之前必须对问题本身进行深入而透彻地分析和证明，以保证使用贪心法得到最优解，而对问题进行分析与证明是比较困难的。5.贪心法在经典算法中的体现(1)哈夫曼(Huffman)编码问题：编码最短(2)求解最小生成树的克鲁斯卡尔(Kruskal)算法和普里姆(Prim)算法：代价最小(3)求解图的最短路径的迪克斯特拉(Dijkstra)算法：路径最短6.举例例1：找零钱问题。假设有3种硬币，面值分别为1元、五角、1角。这3种硬币各自的数量不限，现在要找给顾客2元7角钱，请问怎样找钱才能使得找给顾客的硬币数量最少呢？分析：为了找给顾客的硬币数量最少，在选择硬币的面值时，当然是尽可地选择面值大的硬币。因此要找给顾客2元7角钱，且使得硬币数量最少，应该按照以下步骤：(1)首先找出一个面值不超过2元7角的最大硬币，即1元硬币。(2)然后从2元7角中减去1元，得到1元7角，再找出一个面值不超过1元7角的最大硬币，即1元硬币。(3)然后从1元7角中减去1元，得到7角，再找出一个面值不超过2角的最大硬币，即5角硬币。(4)然后从7角中减去5角，得到2角，再找出一个面值不超过2角的最大硬币，即1角硬币。(5)最后从2角中减去一角，得到1角，再找出一个面值不超过1角的最大硬币，即1角硬币。(6)找零钱过程结束。根据以上分析，我们知道在求解的每一步所作出的选择是从当前看来最优的选择，即硬币面值最大。该问题具有贪心选择性质与最优子结构性质，因此可以使用贪心算法。例2：从键盘输入一件物品的价格（范围在0.10-5.00元），假设用户支付了一张5元纸币，请列出一种找零的方案，使得纸币及硬币的个数最少。假设纸币的面值分别为2元、1元，硬币的面值分别为5角、2角、1角、5分、2分、1分。若物品价格为1.32元，则应找3.68元，输出为2元1张，1元1张，5角1个，1角1个，5分1个，2分1个，1分1个。若物品价格为0.01元，则应找4.99元，输出为2元2张，5角1个，2角2个，5分1个，2分2个。分析：该问题同样可以用贪心法求解。例3：活动安排问题。活动安排问题是可以用贪心算法有效求解的一个很好的例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。设有n个活动集合e={1，2，…，n}，其中每个活动都要求使用同一资源，如演讲会场，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且sifi。如果选择了活动i，则它在半开时间区间[si，fi)内占用资源。若区间[si，fi)与区间[sj，fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。在下面所给出的解活动安排问题的贪心算法select中，各活动的起始时间和结束时间存储于数组s和f中，且按结束时间的非减序：f1≤f2≤…≤fn排列。如果所给出的活动未按此序排列，我们可以用O(nlogn)的时间将它重排。例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011s[i]130535688212f[i]4567891011121314算法片段：算法select中用集合a来存储所选择的活动。活动i在集合a中，当且仅当a[i]的值为true。变量j用以记录最近一次加入到a中的活动。由于输入的活动是按其结束时间的非减序排列的，fj总是当前集合a中所有活动的最大结束时间。a[1]=true;intj=1;for(inti=2;i=n;i++){if(s[i]=f[j]){a[i]=true;j=i;}elsea[i]=false;}贪心算法select一开始选择活动1，并将j初始化为1。然后依次检查活动i是否与当前已选择的所有活动相容。若相容则将活动i加人到已选择活动的集合a中，否则不选择活动i，而继续检查下一活动与集合a中活动的相容性。由于fi总是当前集合a中所有活动的最大结束时间，故活动i与当前集合a中所有活动相容的充分且必要的条件是其开始时间s不早于最近加入集合a中的活动j的结束时间fj，si≥fj。若活动i与之相容，则i成为最近加人集合a中的活动，因而取代活动j的位置。由于输入的活动是以其完成时间的非减序排列的，所以算法select每次总是选择具有最早完成时间的相容活动加入集合a中。直观上按这种方法选择相容活动就为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法select的效率极高。当输入的活动已按结束时间的非减序排列，算法只需g(n)的时间来安排n个活动，使最多的活动能相容地使用公共资源。算法select的计算过程如图所示。i1234567891011s[i]130535688212f[i]4567891011121314总结：贪心算法与动态规划算法的差异贪心算法和动态规划算法都要求问题具有最优子结构性质，这是两类算法的一个共同点。但是，对于一个具有最优子结构的问题应该选用贪心算法还是动态规划算法来求解?是不是能用动态规划算法求解的问题也能用贪心算法来求解?两个经典的组合优化问题：背包问题&0-1背包问题，说明了贪心算法与动态规划算法的主要差别。虽然这两个问题极为相似，但背包问题可以用贪心算法求解，而0-1背包问题却不能用贪心算法求解。用贪心算法解背包问题的基本步骤是，首先计算每种物品单位重量的价值vj／wi然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过c，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直进行下去直到背包装满为止。具体算法可描述如下：voidknapsack(intn,floatm,floatv[],floatw[],floatx[]){sort(n,v,w);//按单位重量价值高到低排序inti;for(i=1;i=n;i++)x[i]=0;floatc=m;for(i=1;i=n;i++){if(w[i]c)break;x[i]=1;c-=w[i];}if(i=n)x[i]=c/w[i];}算法knapsack的主要计算时间在于将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为o(nlogn)。当然。对于0—1背包问题，贪心选择之所以不能得到最优解是因为它无法保证最终能将背包装满，部分背包空间的闲置使每千克背包空间所具有的价值降低了。事实上，在考虑0—1背包问题的物品选择时，应比较选择该物品和不选择该物品所导致的最终结果，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。动态规划算法的确可以有效地解0—1背包问题。例4：背包问题。有一个背包，背包容量是M=150。有7个物品，物品不可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。物品ABCDEFG重量(W)35306050401025价值（P）10403050354030附：本题是个NP问题，用贪心法并不一定可以求得最优解，但可以利用动态规划算法求解。分析：（注：以下是分析说明该问题不能用贪心法求得最优解。）目标函数：∑pi最大约束条件是装入的物品总重量不超过背包容量：∑wi=M(M=150)(1)根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？(2)每次挑选所占重量最小的物品装入是否能得到最优解？(3)每次选取单位重量价值最大的物品，成为解本题的策略。值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。可惜的是，它需要证明后才能真正运用到题目的算法中。一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：（1）贪心策略：选取价值最大者。反例：W=30物品：ABC重量：281212价值：302020根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。反例：W=30物品：ABC重量：281020价值：20810根据策略，首先选取物品B，然后再选C，就无法再选取了，可选取A则更好。（3）贪心策略：选取单位重量价值最大的物品。反例：W=30物品：ABC重量：282010价值：282010根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。【注意：如果物品可以分割为任意大小，那么策略3可得最优解】对于选取单位重量价值最大的物品这个策略，可以再加一条优化的规则：对于单位重量价值一样的，则优先选择重量小的！这样，上面的反例就解决了。但是，如果题目是如下所示，这个策略就也不行了。W=40物品：ABC重量：252015价值：252015练习题：1.有一批集装箱要装入一个载重量为C的货船中，每个集装箱的质量由用户自己输入指定，在货船的装载体积不限的前提下，如何装载集装箱才能尽可能多地将集装箱装入货船中。假设C=13，有5个集装箱，重量分别为{5,7,6,3,2}.分析：该问题可形式化描述为：niix1maxnixcxwiniii1},1,0{|1其中变量xi=0表示不装入集装箱i，xi=1表示装入集装箱i。该问题可以用贪心算法求得最优解，只要每次装船时，选重量最轻的集装箱先装船的策略。在实现时先要按照集装箱的重量从小到大排序，然后从最小的开始选取，直到货船已达到最大载重量C或者集装箱全部装完。2.其他练习请参考文件“贪心法例题.pdf”