第5章-贪心算法

125.1贪心算法概述5.2贪心算法的理论基础5.3删数字问题5.4背包问题5.5覆盖问题5.6图的着色问题5.7遍历问题5.8最小生成树5.9哈夫曼编码35.1贪心算法概述5.1.1贪心算法有一艘大船准备用来装载货物。所有待装货物都装在货箱中且所有货箱的大小都一样，但货箱的重量都各不相同。设第i个货箱的重量为wi（1≤i≤n），而货船的最大载重量为c，我们的目的是在货船上装入最多的货物。这个问题可以作为最优化问题进行描述：设存在一组变量xi，其可能取值为0或1。如xi为0，则货箱i将不被装上船；如xi为1，则货箱i将被装上船。我们的目的是找到一组xi，使它满足限制条件ni=∑wixi≤c且xi∈[0,1],1≤i≤n。相应的优化函数是ni=∑wixi取极值。满足限制条件的每一组xi都是一个可行解，能使ni=∑wixi取得极大值的方案是最优解。4贪心算法（也称贪心策略）总是作出在当前看来是最好的选择。（贪心选择），将原问题规模缩小，如此反复，直至得到最终解。贪心算法并非对所有问题都能得到整体最优解。如上面的找硬币问题本身具有最优子结构性质，它可以用动态规划算法来解。但我们看到，用贪心算法更简单，更直接且解题效率更高。这利用了问题本身的一些特性。贪心算法在求解最优化问题时，从初始阶段开始，每一个阶段总是作一个使局部最优的贪心选择，不断把将问题转化为规模更小的子问题。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。这样处理，对大多数优化问题来说能得到最优解，但也并不总是这样。从求解效率来说，贪心算法比动态规划更高，且不存在空间限制的影响。另外，对一些NP完全问题或规模很大的优化问题，可通过仿贪心算法能得到很好的近似解，而用动态规划根本无法解。55.1.2.贪心算法的基本思想贪心算法的基本思想是通过一系列选择步骤来构造问题的解，每一步都是对当前部分解的一个扩展，直至获得问题的完整解。所做的每一步选择都必须满足：(1)可行的：必须满足问题的约束。(2)局部最优：当前所有可能的选择中最佳的局部选择。(3)不可取消:选择一旦做出，在后面的步骤中就无法改变了。贪心算法是通过做一系列的选择来给出某一问题的最优解，对算法的每一个决策点，做一个当时（看起来）是最佳的选择。这种启发式策略并不总是能产生出最优解。6贪心算法两个重要性质•贪心选择性质：所求问题的整体最优解可由一系列局部最优选择得到。即贪心选择来达到。采用自顶向上的方式进行。动态规划是由子问题的解得到当前问题的解；贪心算法则是由当前问题的局部最优解导出子问题；确定一个问题是否具有贪心选择性质，需要证明问题的一个整体最优解是从贪心选择开始的；•最优子结构：通过局部最优选择，原问题将被化简为类似的子问题；亦即是说，一个问题的整体最优解中包含了它的子问题的最优解；7贪心算法的基本步骤1、从问题的某个初始解出发。2、采用循环语句，当可以向求解目标前进一步时，就根据局部最优策略，得到一个部分解，缩小问题的范围或规模。3、将所有部分解综合起来，得到问题的最终解。8对给定的n位高精度正整数,去掉其中k(kn)个数字后，按原左右次序将组成一个新的正整数，使得剩下的数字组成的新数最大。操作对象是一个可以超过有效数字位数的n位高精度数,存储在数组a中。每次删除一个数字,选择一个使剩下的数最大的数字作为删除对象。之所以选择这样“贪心”的操作,是因为删k个数字的全局最优解包含了删一个数字的子问题的最优解。当k=1时,在n位整数中删除哪一个数字能达到最大的目的?从左到右每相邻的两个数字比较:若出现增,即左边小于右边,则删除左边的小数字。若不出现减,即所有数字全部升序,则删除最右边的大数字。(改为：删除最左边的小数字)5.3删数字问题9当k1(当然小于n),按上述操作一个一个删除。删除一个达到最大后,再从头即从串首开始,删除第2个,依此分解为k次完成。若删除不到k个后已无左边小于右边的增序,则停止删除操作,打印剩下串的左边n-k个数字即可(相当于删除了若干个最右边的数字)。下面我们给出采用贪心算法的删数字问题的部分c语言代码：10while(kx&&m==0){i=i+1;if(a[i-1]a[i])/*出现递增,删除递增的首数字*/{printf(%d,a[i-1]);for(j=i-1;j=n-x-2;j++)a[j]=a[j+1];x=x+1;/*x统计删除数字的个数*/i=0;/*从头开始查递增区间*/}if(i==n-x-1)/*已无递增区间,m=1脱离循环*/m=1;}printf(\n删除后所得最大数:);for(i=1;i=n-k;i++)/*打印剩下的左边n-k个数字*/printf(%d,a[i-1]);11printf(请输入整数：);scanf(%s,b);for(n=0,i=0;b[i]!='\0';i++){n++;a[i]=b[i]-48;}125.4背包问题已知n种物品和一个可容纳c重量的背包，物品i的重量为，产生的效益为。装包时物品可拆，即可只装每种物品的一部分。背包可产生的效益为多少.如何装包，使所得整体效益最大?(1)算法设计应用贪心算法求解。每一种物品装包，由可以整个装入，也可以只装一部分，也可以不装。约束条件：目标函数：要使整体效益即目标函数最大，按单位重量的效益非增次序一件件物品装包，直至某一件物品装不下时，装这种物品的一部分把包装满。解背包问题贪心算法的时间复杂度为O(n)。13算法思想：首先计算每种物品单位重量的价值Pi/Wi，然后，依贪心选择策略，将尽可能多的单位重量价值最高的物品装入背包。若将这种物品全部装入背包后，背包内的物品总重量未超过C，则选择单位重量价值次高的物品并尽可能多地装入背包。依此策略一直地进行下去，直到背包装满为止。14物品可拆背包问题C程序设计代码如下：for(i=1;i=n-1;i++)/*对n件物品按单位重量的效益从大到小排序*/for(j=i+1;j=n;j++)if(p[i]/w[i]p[j]/w[j]){h=p[i];p[i]=p[j];p[j]=h;h=w[i];w[i]=w[j];w[j]=h;}cw=c;s=0;/*cw为背包还可装的重量*/for(i=1;i=n;i++){if(w[i]cw)break;x[i]=1.0;/*若w(i)=cw,整体装入*/cw=cw-w[i];s=s+p[i];}x[i]=(float)(cw/w[i]);/*若w(i)cw,装入一部分x(i)*/s=s+p[i]*x[i];15printf(装包：);/*输出装包结果*/for(i=1;i=n;i++)if(x[i]1)break;elseprintf(\n装入重量为%5.1f的物品.,w[i]);if(x[i]0&&x[i]1)printf(\n装入重量为%5.1f的物品百分之%5.1f.,w[i],x[i]*100);printf(\n所得最大效益为：%7.1f,s);160-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。17对于0-1背包问题，贪心选择之所以不能得到最优解是因为在这种情况下，它无法保证最终能将背包装满，部分闲置的背包空间使每公斤背包空间的价值降低了。事实上，在考虑0-1背包问题时，应比较选择该物品和不选择该物品所导致的最终方案，然后再作出最好选择。由此就导出许多互相重叠的子问题。这正是该问题可用动态规划算法求解的另一重要特征。实际上也是如此，动态规划算法的确可以有效地解0-1背包问题。180-1背包问题不满足最优子结构性质，不能用贪心法来求解，而应用分治法求解。分治规则为：S(w1..n,v1..n,W)=max{S(w1..n-1,v1..n-1,W-wn)+vn,S(w1..n-1,v1..n-1,W)}19带有限期的作业排序问题的描述：带有期限的作业排序要解决的是操作系统中单机、无资源约束且每个作业可在等量的时间内完成的作业调度问题。把这个问题形式化描述为：①要在一台机器上处理n个作业，每个作业可以在单位时间内完成;②每个作业i都有一个期限值di，di0③当作业在它规定的期限值前完成，就可以获得的效益pi，pi0问题求解的目标是：问题的可行解是这n个作业的一个子集合J。J中的每个作业都能在各自的截止期限前完成后，产生一个作业效益之和。即找到一个子集J，J中的每个作业都能在各自的截止期限前完成，并且使得作业效益值的和最大。这个作业的一个子集合J就是所求的最优解。20例3.2n=4，(p1,p2,p3,p4)=(100,10,15,20)，(d1,d2,d3,d4)=(2,1,2,1)。可行解处理顺序效益值1{1}11002{2}2103{3}3154{4}4205{1，2}2，11106{1，3}1，3或3，11157{1，4}4，11208{2，3}2，3259考虑2,4？{3，4}4，33521这个问题的最优解为第7个，所允许的处理顺序是：先处理作业4，在处理作业1。在时间0开始处理作业4而在时间2完成对作业1的处理。22带有期限的作业排序贪心算法度量标准的选取：我们的目标是作业效益值的和最大，因此首先把目标函数作为度量标准。首先把作业按照它们的效益值作一个非增次序的排序。作业根据效益值排序后为作业1、4、3、2。求解时首先把作业1计入J，由于作业1的期限值是2，所以J={1}是一个可行解。接下来计入作业4。由于作业4的期限值是1而作业1的期限值是2，可以先完成作业4后再完成作业1，所以J={1,4}是一个可行的解。然后考虑作业3，但是作业3的期限值是2，计入J后就没有办法保证J中的每一个作业都在期限值内完成，因此计入作业3后不能构成一个可行解。同理计入2后也不能构成一个可行解。由分析可知，把目标函数作为度量标准能够得到问题的最优解。23procedureGREEDY-JOB(D,J,n)//作业按照p1≥p2≥…≥pn的次序输入，它们的期限值D(i)≥1,1≤i≤n,n≥1。J是在它们的截止期限前完成的作业集合。J←{1}Fori←2tondoIfJ∪{i}的所有作业都能在它们的截止期限前完成ThenJ←J∪{i}EndifRepeatEndGREEDY-JOB24在这个概略的算法中需要解决的关键是如何判断作业i并入J后仍然能够保证J中的所有作业都能够在它们的截止期限前完成。在做这个判断之前先看两个定理。定理2：算法所描述的贪心方法对于作业排序问题总是得到一个最优解。定理3：设J是k个作业的集合，б=i1i2…ik是J中作业的一种排列，它使得di1≤di2≤…≤dik。J是一个可行解，当且仅当J中的作业可以按照б的次序而又不违反任何一个期限的情况来处理。25保证J中的所有作业在它们的截止期限前完成的判断分析：可定义一个数组J，它存放纳入集合J中的作业。假设已经处理了i-1个作业，并且有k个作业已经计入数组J中，分别是J(1),J(2),…,J(k)，且有D(J(1))≤D(J(2))≤…≤D(J(k))。注意D(J(r))(1≤r≤k)表示计入数组J中的作业r（也就是J(r)表示的那个作业）的期限值。因为已经处理了i-1个作业，所以现在要考虑的是作业i是否可以并入到J中形成一个可行解。26根据定理3.3，要判断作业i是否可以并入到J中形成一个可行解，就要看能否在数组J中找到一个位置，使i插入后仍然能保证J中的所有k+1个作业都在它们的期限之前完成，而且有D(J(1))≤D(J(2))≤…≤D(J(k+1))，即在数组J中插入后，它的期限值要比在它前一个位置的那个作业