第4章 贪心算法

1第4章贪心算法4.1贪心算法的基本要素4.2活动安排问题4.3最优装载4.4单源最短路径4.5哈夫曼编码4.6多机调度问题贪心算法顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。2例：用贪心法求解付款问题。假设有面值为5元、2元、1元、5角、2角、1角的货币，需要找给顾客4元6角现金，为使付出的货币的数量最少，首先选出1张面值不超过4元6角的最大面值的货币，即2元，再选出1张面值不超过2元6角的最大面值的货币，即2元，再选出1张面值不超过6角的最大面值的货币，即5角，再选出1张面值不超过1角的最大面值的货币，即1角，总共付出4张货币。在付款问题每一步的贪心选择中，在不超过应付款金额的条件下，只选择面值最大的货币，而不去考虑在后面看来这种选择是否合理，而且它还不会改变决定：一旦选出了一张货币，就永远选定。付款问题的贪心选择策略是尽可能使付出的货币最快地满足支付要求，其目的是使付出的货币张数最慢地增加，这正体现了贪心法的设计思想。5贪心算法的设计思路贪心算法的设计思路是：总是做出在当前看来最好的选择，即贪心算法并不是从整体最优考虑，它所做的选择只是在某种意义上的局部最优选择。贪心算法框架Greedy(A,n){//A为输入集合solution=Ø;//解空间初始化为空for(i=1;i=n;i++){//对每个输入进行检测x=select(A);//选择一个输入if(feasible(solution,x))//如果可行solution=union(solution,x);//添至解空间}returnsolution;}674.1贪心算法的基本要素利用贪心算法求解最优解的两个前提条件:贪心选择性质和最优子结构性质。1.贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是利用贪心算法求解最优解的第一个基本要素，也是贪心算法与动态规划算法的主要区别。82.最优子结构性质当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。93.贪心算法与动态规划算法的差异共同点：求解的问题都具有最优子结构性质差异点：动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每做一次贪心选择就将所求问题简化为规模更小的子问题。100-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包最大承载重量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。背包问题：与0-1背包问题类似，所不同的是在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。110-1背包与背包问题都具有最优子结构已知背包最大承载重量为C，共有n个物品，每个物品的重量分别为Wi(i=1,2,...,n)，价值为Vi(i=1,2,...n)。证明：假设第k个物品是最优解中的一个物品，则从中拿出Wk对应的物品后所对应的解一定是其余n-1个物品，装入背包最大承载重量为C-Wk的最优解，否则与假设矛盾。0-1背包问题不具有贪心选择性质。原因是无法保证能够将背包装满，而所剩空间将会降低总价值。背包问题具有贪心选择性质。12130-1背包问题不具有贪心选择特性物品110公斤，价值60元物品220公斤，价值100元物品330公斤，价值120元单位价值6元单位价值5元单位价值4元背包容量：50公斤物品1物品2=￥60+100贪心算法物品2物品3=￥100+120最优解14背包问题具有贪心选择特性物品110公斤，价值60元物品220公斤，价值100元物品330公斤，价值120元单位价值6元单位价值5元单位价值4元背包容量：50公斤物品1物品2物品3=￥60+100+80贪心算法10公斤20公斤20公斤15用贪心算法解背包问题的基本步骤：1.计算每种物品单位重量的价值Vi/Wi；2.按照单位重量的价值从高到低的顺序排序；3.依据贪心选择策略，按照单位价值从高到低的顺序，依次将尽可能多的物品装入背包中。直到背包装满为止。是否可以将物品装入背包的条件是：有空间16背包问题的贪心算法voidknapsack(floatc,floatw[],floatv[],floatx[],intn){将各种物品依其单位重量的价值从高到低排序初始化x[i]=0;for(i=0;in;i++){//贪心选择if(不能放)break;放入背包中}if(背包没满&&还有物品){装满;}returnopt;}w[i]重量v[i]单位价值x[i]结果17背包问题的贪心算法floatknapsack(floatc,floatw[],floatv[],floatx[],intn){ITEMTYPEd[n];for(inti=0;in;i++)d[i]=(w[i],v[i],i);mergeSort(d);//按照单价高低排序inti;floatopt=0;for(i=0;in;i++)x[i]=0;for(i=0;in;i++){//贪心选择if(d[i].wc)break;x[d[i].i]=1;opt+=d[i].v;c-=d[i].w;}if(c0&&in){//零碎空间x[d[i].i]=c/d[i].w;opt+=x[d[i].i]*d[i].v;}returnopt;}wvi单价10601620100253012034112/3x算法knapsack的主要计算时间是将各种物品依其单位重量的价值从大到小排序。因此，算法的计算时间上界为O（nlogn）。typedefstruct{floatw,v;inti;}ITEMTYPE;D[]:184.2活动安排问题设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且sifi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。19各活动占用资源情况假设按照11个活动的结束时间的非减序排列如下：i1234567891011s[i]130535688212f[i]4567891011121314按照每个活动完成时间的顺序排列20（1）活动安排具有最优子结构性质Sij表示第i个任务结束之后，第j个任务开始之前的任务集合。假设子问题Sij的最优解集合为Aij且包含任务ak，则在最优解集合里的子问题Sik的解Aik以及子问题Skj的解Akj也一定是最优的。证明：假设子问题Sik存在一个更优的解A’ik，则|A'ik|+1+|Akj||Aik|+1+|Akj|=|Aij|与假设矛盾！21令子问题Sij≠Ø且a1为子问题Sij中具有最早完成时间的任务，则a1一定包含在子问题Sij中某个任务相互兼容的最大子集中。结论：具有贪心选择特性。（2）活动安排具有贪心选择特性‫证明：‫假设子问题Sij的最优解为Aij，其中的任务按照完成时间由小到大排列；且第一个任务为ak。如果ak=a1，成立。‫如果ak≠a1，由于a1完成时间较ak早，所以，可以将ak去掉，换成a1，仍然相容，所含任务数量一样。2223活动安排问题举例假设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314若被检查的活动i的开始时间Si小于最近选择的活动j的结束时间fi，则不选择活动i，否则选择活动i加入集合A中24图中每行相应于算法的一次迭代。阴影长条表示的活动是已选入集合A的活动，而空白长条表示的活动是当前正在检查相容性的活动。i1234567891011S[i]130535688212f[i]456789101112131425isifi1142353064575386597610881198121021311121401234567891011121314结果：选中的任务为：1、4、8、1126解活动安排问题的贪心算法intgreedySelector(ints[],intf[],booleana[],intn){a[1]=true;//初始化intj=1,count=1;for(inti=2;i=n;i++){//贪心选择if(s[i]=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;}returncount;}各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列27假设输入的活动以其完成时间的非减序排列，则算法greedySelector总选择最早完成时间的相容活动加入集合A中。该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。284.3最优装载有一批集装箱要装上一艘载重量为c的轮船。其中，集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。29最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产生最优装载问题的最优解。maxniix1niiiwxc1{,},ixin01130(1)最优子结构的性质设(x1,x2,...,xn)是最优装载问题满足贪心选择的最优解，则可知，x1=1，且(x2,...,xn)是轮船重量为c-w1,待装船集装箱为{2,3,...,n}时相应最优装载问题的最优解。利用反证法证明。31(2)贪心选择性质设集装箱依重量从小到大排序，(x1,x2,...,xn)是最优装载问题的一个最优解。设x:(0，0，1，1，1，0，0，0）k=3y:(1，0，0，1，1，0，0，0）nnniikiiiiiiiwy1111}1|{min1inixik32最优装载贪心算法floatloading(floatc,floatw[],intx[],intn){ITREMTYPEd[n];for(inti=0;in;i++)d[i]=(w[i],i);mergeSort(d);//排序O(nlogn)floatopt=0;for(inti=0;in;i++)x[i]=0;for(inti=0;in&&d[i].w=c;i++){//贪心选择x[d[i].i]=1;opt+=d[i].w;c-=d[i].w;}returnopt;}typedefstruct{floatw;inti;}ITEMTYPE;33344.4单源最短路径问题提出:给定带权有向图G=(V,E)，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路经长度。这里路径长度是指路上各边权之和。这个问题通常称为单源最短路径问题。35v0v1:无v0v2:10v0v4v3:50v0v4:30v0v4v3v5:60v0v1v2v3v4v5100603020105051036（1）Dijkstra算法Dijk