第5章 贪心法

1、第第5章章 贪心法贪心法贪心法（贪心法（Greedy algorithms）的基本思路是在对问题求）的基本思路是在对问题求解时总是做出在当前看来是最好的选择，也就是说贪心法不解时总是做出在当前看来是最好的选择，也就是说贪心法不从整体最优上加以考虑，所做出的仅是在某种意义上的局部从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。最优解。人们通常希望找到整体最优解（或全局最优解），那么人们通常希望找到整体最优解（或全局最优解），那么贪心法是不是没有价值呢？答案是否定的，这是因为某些求贪心法是不是没有价值呢？答案是否定的，这是因为某些求解问题中，当满足一定的条件时，这些局部最优解就转变成解

2、问题中，当满足一定的条件时，这些局部最优解就转变成了整体最优解，所以贪心法的困难部分就是要证明所设计的了整体最优解，所以贪心法的困难部分就是要证明所设计的算法确实是整体最优解或求解了它要解决的问题。算法确实是整体最优解或求解了它要解决的问题。 5.1.1 什么是贪心法什么是贪心法在求解问题时，通常求解问题直接给出或者可以分析在求解问题时，通常求解问题直接给出或者可以分析出某些约束条件，满足约束条件的问题解称为出某些约束条件，满足约束条件的问题解称为可行解可行解。另外，求解问题直接给出或者可以分析出衡量可行解另外，求解问题直接给出或者可以分析出衡量可行解好坏的目标函数，使目标函数取最大（或最小）

3、值的可行好坏的目标函数，使目标函数取最大（或最小）值的可行解称为解称为最优解最优解。例如，求解一个带权无向图例如，求解一个带权无向图G中从顶点中从顶点i到顶点到顶点j（ij）的）的最短路径，可以分析出这样的最短路径一定是简单路径，所以最短路径，可以分析出这样的最短路径一定是简单路径，所以约束条件约束条件为：为：i目标函数目标函数就是要使这样的路径最短，即：就是要使这样的路径最短，即：(i,i1),(i1,i2),(im,j) | pathlength=w(i,i1)+w(i1,i2)+w(im,j)， w(i,k)表示表示(i,k)的权值的权值pathlengthMIN求解的路径为求解的路径为

4、(i,i1),(i1,i2),(im,j) | (i,i1)、(i1,i2)、(im,j)均均为图为图G的边，且的边，且ik（1km）均不相同）均不相同i1i2j贪心法是求解这类问题的一种常用算法，它从问题的某贪心法是求解这类问题的一种常用算法，它从问题的某一个初始解一个初始解出发，采用逐步构造最优解的方法向给定的目出发，采用逐步构造最优解的方法向给定的目标前进，每一步决策产生标前进，每一步决策产生n-元组解（元组解（x0,x1,xn-1）的一个分）的一个分量。量。贪心法每一步上用作决策依据的选择准则被称为贪心法每一步上用作决策依据的选择准则被称为最优量最优量度标准度标准（或贪心准则），也就是

5、说，在选择解分量的过程中，（或贪心准则），也就是说，在选择解分量的过程中，添加新的解分量添加新的解分量xk后，形成的部分解（后，形成的部分解（x0,x1,xk)不违反可行不违反可行解约束条件。解约束条件。每一次贪心选择都将所求问题简化为规模更小的子问题，每一次贪心选择都将所求问题简化为规模更小的子问题，并期望通过每次所做的局部最优选择产生出一个全局最优解。并期望通过每次所做的局部最优选择产生出一个全局最优解。计算机科学中很多算法都属于贪心法。计算机科学中很多算法都属于贪心法。例如，在操作系统的磁盘管理中有一个磁盘移臂调度问例如，在操作系统的磁盘管理中有一个磁盘移臂调度问题，进程在执行会多次访问

6、磁盘，按访问的先后次序构成一题，进程在执行会多次访问磁盘，按访问的先后次序构成一个个I/O序列，序列，I/O操作的数据存放在磁盘的各个柱面上，磁盘操作的数据存放在磁盘的各个柱面上，磁盘臂通过在这些柱面之间移动磁头找到相关数据，移动磁盘臂臂通过在这些柱面之间移动磁头找到相关数据，移动磁盘臂是要花费时间的，磁盘移臂调度的目的是使平均访问时间最是要花费时间的，磁盘移臂调度的目的是使平均访问时间最小。小。很多情况下，所有局部最优解合起来不一定构成整体最优很多情况下，所有局部最优解合起来不一定构成整体最优解，所以贪心法不能保证对所有问题都得到整体最优解。因此解，所以贪心法不能保证对所有问题都得到整体最优

7、解。因此采用贪心法求解最优解问题时，必须证明该算法的每一步上作采用贪心法求解最优解问题时，必须证明该算法的每一步上作出的选择，都必然最终导致问题的一个整体最优解，对许多问出的选择，都必然最终导致问题的一个整体最优解，对许多问题，如背包问题、单源最短路径问题和最小生成树问题等，贪题，如背包问题、单源最短路径问题和最小生成树问题等，贪心法确实能产生整体最优解。心法确实能产生整体最优解。有些情况下，即使贪心法不能得到整体最优解，其最终结有些情况下，即使贪心法不能得到整体最优解，其最终结果却是最优解的很好近似。果却是最优解的很好近似。另外，贪心与递归不同的是，推进的每一步不是依据某一另外，贪心与递归不

8、同的是，推进的每一步不是依据某一固定的递归式，而是做一个当时看似最佳的固定的递归式，而是做一个当时看似最佳的贪心选择贪心选择，不断地，不断地将问题实例归纳为更小的相似子问题。将问题实例归纳为更小的相似子问题。5.1.2 贪心法求解的问题应具有的性质贪心法求解的问题应具有的性质1. 贪心选择性质贪心选择性质所谓贪心选择性质是指所求问题的整体最优解可以所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。通过一系列局部最优的选择，即贪心选择来达到。也就是说，贪心法仅在当前状态下做出最好选择，也就是说，贪心法仅在当前状态下做出最好选择，即局部最优选择，然后再去求解做

9、出这个选择后产生的即局部最优选择，然后再去求解做出这个选择后产生的相应子问题的解。相应子问题的解。 2. 最优子结构性质最优子结构性质一个问题的最优解包含其子问题的最优解，则称此问一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构性质。题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法或问题的最优子结构性质是该问题可用动态规划算法或贪心法求解的关键特征。贪心法求解的关键特征。5.1.3 贪心法的一般求解过程贪心法的一般求解过程贪心法求解问题的算法框架如下：贪心法求解问题的算法框架如下：SolutionTypeSolutionType GreedyGreedy( (S

10、TypeSType a, a,intint n) n)/假设解向量为假设解向量为( (x x0 0,x,x1 1, , ,x xn n-1-1) )，其分量为，其分量为STypeSType类型类型 SolutionTypeSolutionType solution= solution=； /初始时，不包含任何分量初始时，不包含任何分量for (for (intint i i= =0;i0;i n;in;i+)+) / /执行执行n n步操作步操作 STypeSType x=Select(a x=Select(a); /); /遵循最优度量标准选择一个分量遵循最优度量标准选择一个分量x xif

11、(if (FeasiableFeasiable( (solution,xsolution,x) ) /判断加入新分量判断加入新分量x x后部分解是否可行后部分解是否可行solution=Union(solution=Union(solution,xsolution,x););/将将x x分量与原部分解合并形成新的部分解分量与原部分解合并形成新的部分解 return solution;return solution;/返回生成的最优解返回生成的最优解 5.2.1 求解区间覆盖问题求解区间覆盖问题问题描述：问题描述：设设x1、x2、xn 是直线上的是直线上的n个点。用固个点。用固定长度的闭区间覆盖

12、这定长度的闭区间覆盖这n个点，设固定长度为个点，设固定长度为k，求解所需，求解所需要的最少固定长度的闭区间个数要的最少固定长度的闭区间个数m。如如n=7，k=3，x序列为序列为2,4,1,6,-2,5,3，求得，求得m=3。问题求解：问题求解：采用贪心法的求解过程如下：采用贪心法的求解过程如下： 将将x序列递增排序，对于给定的示例得到如图序列递增排序，对于给定的示例得到如图5.3（a）所示的结果。所示的结果。 置置m=0，tmp=x0（作为第一个覆盖闭区间的起点），（作为第一个覆盖闭区间的起点），用用i遍历遍历x中所有点（中所有点（i从从1开始循环），当开始循环），当xi与与tmp的距离大的距

13、离大于于k时，新增一个覆盖闭区间，即置时，新增一个覆盖闭区间，即置tmp=xi（xi作为新覆盖作为新覆盖闭区间的起点），闭区间的起点），m增增1。最后返回求得的覆盖闭区间个数。最后返回求得的覆盖闭区间个数m+1。对于给定的示例，求解结果如图。对于给定的示例，求解结果如图5.3（b）所示。）所示。intint minSegmentminSegment( (intint x, x,intint n,intn,int k,intk,int y) y)/求求x x的最大覆盖区间集合的最大覆盖区间集合y y intint i,mi,m= =0,tmp0,tmp; ;/m/m为为y y的下标，从的下标，从

14、0 0开始开始QuickSortQuickSort( (x,0,nx,0,n-1);-1);/调用快速排序算法对调用快速排序算法对x x序列递增排序序列递增排序tmptmp=x0;=x0;/区间的起始位置区间的起始位置y0=x0;y0=x0;for(for(i i= =1;i1;i k)k)/如果如果xxi i 与与tmptmp的距离大于的距离大于k k tmptmp=x=xi i; /开始下一个以开始下一个以xxi i 为起点的覆盖区间为起点的覆盖区间m+; ym=xm+; ym=xi i; return return m+1m+1; ; 算法证明：算法证明：在在x序列递增排序后，显然满足最

15、优子结构性序列递增排序后，显然满足最优子结构性质。下面证明算法具有贪心选择性质。质。下面证明算法具有贪心选择性质。递增排序的递增排序的n个点个点x1、x2、xn，本算法求出长度为，本算法求出长度为k的的闭区间个数为闭区间个数为m，覆盖闭区间集，覆盖闭区间集T=y1,z1,y2,z2,ym,zm，其，其中每个覆盖闭区间的长度为中每个覆盖闭区间的长度为k，Y=yi|yi属于属于x中的点中的点，每个覆，每个覆盖闭区间之间不含有任何盖闭区间之间不含有任何x中的点，现采用反证法证明中的点，现采用反证法证明T是最优是最优解。解。对于点对于点xi（1in），如果），如果xi落在落在T的某个覆盖闭区间内，的某

16、个覆盖闭区间内，T的长度没有改变，那么就不需要进一步证明了。如果的长度没有改变，那么就不需要进一步证明了。如果xi不属不属于于T的任何覆盖闭区间内，则的任何覆盖闭区间内，则xi一定属于覆盖闭区间一定属于覆盖闭区间s,t，且，且s不属于不属于Y，则，则s,t应在应在yj,zj和和yj+1,zj+1之间，与每个覆盖闭区间之间，与每个覆盖闭区间之间不含有任何之间不含有任何x中点的假设矛盾，从而证明算法的正确性。中点的假设矛盾，从而证明算法的正确性。算法分析：算法分析：快速排序的时间复杂性为快速排序的时间复杂性为O(nlog2n)，for循环循环的时间为的时间为O(n)，所以本算法的时间复杂度为，所以

17、本算法的时间复杂度为O(nlog2n)。5.2.2 求解最大不相交区间问题求解最大不相交区间问题问题描述：问题描述：给定给定n个区间个区间a1,b1),a2,b2),an,bn)，其，其中中aibi且没有两个区间是完全相同的。从中选取最多的区且没有两个区间是完全相同的。从中选取最多的区间，使得每个区间都是独立的，所谓区间独立就是一个区间，使得每个区间都是独立的，所谓区间独立就是一个区间不和其他任何区间有相交的地方。间不和其他任何区间有相交的地方。例如例如7个区间个区间2,6),1,4),3,6),3,7),6,8),2,4),3,5)的最的最优解是优解是2,4),6,8)。问题求解：问题求解：

18、采用贪心法的解题思路是：采用贪心法的解题思路是：对区间按右端点递增排序。对区间按右端点递增排序。先选取第一个区间，对于后面区间，只要它的左端点大先选取第一个区间，对于后面区间，只要它的左端点大于前一个选取区间的右端点，说明这个两个区间不相交，则于前一个选取区间的右端点，说明这个两个区间不相交，则选取该区间。选取该区间。对于对于7个区间个区间2,6),1,4),3,6),3,7),6,8),2,4),3,5)，求解过，求解过程如下（用程如下（用y保存所有选取的不相交区间）：保存所有选取的不相交区间）： 将所有将所有n个区间按右端点递增排序，如图个区间按右端点递增排序，如图5.4（a）所示。）所示

19、。 置置m=0，选取，选取x0为第一个不相交区间，为第一个不相交区间，j=0（j指向刚指向刚选取的不相交区间的下标），用选取的不相交区间的下标），用i遍历遍历x中所有点（中所有点（i从从1开始循开始循环），当环），当xi的左端点大于等于的左端点大于等于xj的右端点时，选取的右端点时，选取xi作为作为一个不相交区间（即执行一个不相交区间（即执行ym=xi，m增增1），），j=i。最后返回。最后返回求得的不相交区间个数求得的不相交区间个数m+1。求解结果如图。求解结果如图5.4（b）所示。）所示。intint maxCovermaxCover( (IntervalTypeIntervalType

20、x, x,intint n,IntervalTypen,IntervalType y) y)/求求x x（已排序）的最大不相交区间集合（已排序）的最大不相交区间集合y y intint i,mi,m=0;=0;/m/m为为y y的下标，从的下标，从0 0开始开始intint j=0; j=0;/j/j保存刚求得的最小闭区间的下标，从保存刚求得的最小闭区间的下标，从0 0开始开始y0=x0;y0=x0;for (for (i i= =1;i1;i =xj.end).start=xj.end) m+; ym=x m+; ym=xi i;j=j=i i; ; return return m+1m+1

21、; ; 算法证明：算法证明：设设X为为n个已经排序成个已经排序成b1b2b3bn的的区间集合，在算法中选第一个区间是否正确，现予以证明。区间集合，在算法中选第一个区间是否正确，现予以证明。考虑考虑a1和和a2的大小关系，只有以下两类情况：的大小关系，只有以下两类情况：情况情况1：a1a2，如图，如图5.5（a）所示，区间）所示，区间2包含区间包含区间1，这，这种情况下一定不会选区间种情况下一定不会选区间2（因为需要尽量多的独立区间，所（因为需要尽量多的独立区间，所以每个区间都尽可能的小），不仅区间以每个区间都尽可能的小），不仅区间2如此，以后所有区间如此，以后所有区间中只要有中只要有a1ai，

22、a1都不会选。因此这种情况下选区间都不会选。因此这种情况下选区间1不会影响不会影响正确性。正确性。 a1 b1 a2 b2 （a）a1a2的情况 情况情况2：a1a2a3，如图，如图5.5（b）所示，如果区间）所示，如果区间2和区间和区间1完全不相交，那么没有影响（此时一定会选区间完全不相交，那么没有影响（此时一定会选区间1）；）；如果区间如果区间2和区间和区间1相交，两者之间最多只能选一个，如果选区相交，两者之间最多只能选一个，如果选区间间1，其黑色部分不会挡住任何一个区间，其有效部分变成灰，其黑色部分不会挡住任何一个区间，其有效部分变成灰色部分，它被区间色部分，它被区间2所包含，此时一定不

23、会选区间所包含，此时一定不会选区间2。因此这种。因此这种情况下选区间情况下选区间1也不会影响正确性。也不会影响正确性。 a1 b1 a2 b2 （b）a1a2a3b1，(ai,bi)X的最优解。如若不然，假设的最优解。如若不然，假设Z是是X的最优解，则的最优解，则Z比比Y包含更多包含更多的区间，将区间的区间，将区间1加入加入Z中将产生中将产生X的一个解的一个解Y，且，且Y比比Y包含包含更多的区间，这与更多的区间，这与Y是原问题的最优解的假设相矛盾，从而证明是原问题的最优解的假设相矛盾，从而证明算法的正确性。算法的正确性。算法分析：算法分析：快速排序的时间复杂性为快速排序的时间复杂性为O(nlo

24、g2n)，for循环循环的时间为的时间为O(n)，所以本算法的时间复杂度为，所以本算法的时间复杂度为O(nlog2n)。5.2.3 求解活动安排问题求解活动安排问题问题描述：问题描述：假设有一个需要使用某一资源的假设有一个需要使用某一资源的n个活动所组成个活动所组成的集合的集合S，S=1,n。该资源一次只能被一个活动所占用，每。该资源一次只能被一个活动所占用，每一个活动一个活动i有一个开始时间有一个开始时间bi和结束时间和结束时间ei（biei）。若活动）。若活动i和和活动活动j有有biej或或bjei，则称这两个活动，则称这两个活动兼容兼容。需要选择出由互相兼容的活动所组成的最大集合。需要选

25、择出由互相兼容的活动所组成的最大集合。问题求解：问题求解：采用贪心策略如下：每一步总是选择这样一个采用贪心策略如下：每一步总是选择这样一个活动来占用资源，它能够使得余下的未调度的时间最大化，使活动来占用资源，它能够使得余下的未调度的时间最大化，使得兼容的活动尽可能多。得兼容的活动尽可能多。实际上，活动安排问题和实际上，活动安排问题和5.2.2小节介绍的最大不相交区间小节介绍的最大不相交区间问题属同类问题，一个活动问题属同类问题，一个活动i（1in）用一个区间）用一个区间bi,ei)表示，表示，当活动按结束时间（右端点）递增排序后，两个活动当活动按结束时间（右端点）递增排序后，两个活动bi,ei

26、)和和bj,ej)兼容（满足兼容（满足biej或或bjei）实际上就是指它们不相交。从）实际上就是指它们不相交。从而将求解活动安排问题转化为求解最大不相交区间问题。而将求解活动安排问题转化为求解最大不相交区间问题。由由n个活动（活动个活动（活动i的起始时间和结束时间分别存放在的起始时间和结束时间分别存放在bi和和ei中，中，0in-1）产生的最大相容活动子集（所选活动的起始时间）产生的最大相容活动子集（所选活动的起始时间和结束时间分别存放在和结束时间分别存放在Bj和和Ej中，中，0jm-1）的算法如下：）的算法如下：intint ActiveManageActiveManage( (intin

27、t b, b,intint e, e,intint n,intn,int B, B,intint E) E) intint i,mi,m=0;=0;/m/m为为B B和和E E的下标，从的下标，从0 0开始开始intint j=0; j=0;/选取的第一个活动的下标选取的第一个活动的下标B0=b0; E0=e0;B0=b0; E0=e0;/选取第一个活动选取第一个活动for (for (i i= =1;i1;i =ej)=ej) j= j=i i; ;/j/j指向当前选取的活动的下标指向当前选取的活动的下标m+; Bm=bm+; Bm=bi i; Em=e; Em=ei i;/;/选取活动选取

28、活动i i return return m+1m+1; ;/返回选取的活动个数返回选取的活动个数 例如，对于下表所示的例如，对于下表所示的11个活动（已按结束时间递增排序）个活动（已按结束时间递增排序）X，按最大不相交区间问题求解，按最大不相交区间问题求解Y的过程如下：的过程如下：i i1 12 23 34 45 56 67 78 89 910101111开始时间开始时间1 13 30 05 53 35 56 68 88 82 21212结束时间结束时间4 45 56 67 78 89 910101111121213131515X=1,4),3,5),0,6),5,7),3,8),5,9),6

29、,10),8,11),8,12),2,13),12,14)i=1：选择第一个活动，其右端点为：选择第一个活动，其右端点为4，Y=1,4)i=2：活动：活动3,5)的左端点小于的左端点小于4，不选取，不选取i=3：活动：活动0,6)的左端点小于的左端点小于4，不选取，不选取i=4：活动：活动5,7)的左端点大于的左端点大于4，选择它，其右端点为，选择它，其右端点为7，Y=1,4),5,7)i=5：活动：活动3,8)的左端点小于的左端点小于7，不选取，不选取i=6：活动：活动5,9)的左端点小于的左端点小于7 ，不选取，不选取i=7：活动：活动6,10)的左端点小于的左端点小于7，不选取，不选取i

30、=8：活动：活动8,11)的左端点大于的左端点大于7，选择它，其右端点为，选择它，其右端点为11，Y=1,4),5,7),8,11)i=9：活动：活动8,12)的左端点小于的左端点小于11，不选取，不选取i=10：活动：活动2,13)的左端点小于的左端点小于11，不选取，不选取i=11：活动：活动12,14) 的左端点大于的左端点大于11，选择它，选择它，Y=1,4),5,7),8,11),12,14)所以最后选择的最大相容活动子集为所以最后选择的最大相容活动子集为1,4,8,11。问题描述：问题描述：设有编号为设有编号为1、2、n的的n个物品，它们的个物品，它们的重量分别为重量分别为w1、w

31、2、wn，价值分别为，价值分别为v1、v2、vn，其，其中中wi、vi（1in）均为正数。）均为正数。有一个背包可以携带的最大重量不超过有一个背包可以携带的最大重量不超过W。求解目标是，。求解目标是，在不超过背包负重的前提下，使背包装入的总价值最大（即在不超过背包负重的前提下，使背包装入的总价值最大（即效益最大化），与第效益最大化），与第3章章3.2.4节介绍的节介绍的0/1背包问题的区别是，背包问题的区别是，这里的每个物品可以这里的每个物品可以取一部分取一部分装入背包。装入背包。问题求解：问题求解：这里采用贪心法求解。设这里采用贪心法求解。设xi表示物品表示物品i装入背装入背包的情况，包的情

32、况，0 xi1。根据问题的要求，有如下约束条件和目。根据问题的要求，有如下约束条件和目标函数：标函数：niiiWxw10 xi1（1in） MAXniiixw1于是问题归结为寻找一个满足上述约束条件，并使目于是问题归结为寻找一个满足上述约束条件，并使目标函数达到最大的解向量标函数达到最大的解向量X=x1,x2,xn。例如，例如，n=3， (w1,w2,w3)=(18,15,10)，(v1,v2,v3)=(25,24,15)， W=20，其中的，其中的4个可行解如下：个可行解如下： niiixw1niiixv1解编号解编号(x1,x2,x3)(1/2,1/3,1/4)16.524.25(1,2/

33、15,0)2028.2(0,2/3,1)2031(0,1,1/2)2031.5在这在这4个可行解中，第个解的效益最大，可以求出个可行解中，第个解的效益最大，可以求出它是这个背包问题的最优解。它是这个背包问题的最优解。贪心策略：贪心策略：选择单位重量价值最大的物品。选择单位重量价值最大的物品。每次从物品集合中选择单位重量价值最大的物品，如果其每次从物品集合中选择单位重量价值最大的物品，如果其重量小于背包容量，就可以把它装入，并将背包容量减去该物重量小于背包容量，就可以把它装入，并将背包容量减去该物品的重量，然后就面临了一个最优子问题品的重量，然后就面临了一个最优子问题它同样是背包问它同样是背包问

34、题，只不过背包容量减少了，物品集合减少了。题，只不过背包容量减少了，物品集合减少了。因此背包问题具有最优子结构性质。因此背包问题具有最优子结构性质。对于表对于表5.2所示一个背包问题，所示一个背包问题，n=5，设背包容量，设背包容量W=100，其求解过程如下：其求解过程如下：i12345wi1020304050vi2030664060vi/wi2.01.52.21.01.2 将价值即将价值即v/w递减排序，其结果为递减排序，其结果为66/30,20/10,30/20,60/50,40/40，物品重新按，物品重新按04编号。编号。 设背包余下装入的重量为设背包余下装入的重量为weight，其初值

35、为，其初值为W。 i=0开始，开始，w0weight成立，表明物品成立，表明物品0能够装入，将其能够装入，将其装入到背包中，置装入到背包中，置x0=1，weight=weight-w0=70，i增增1即即i=1；w1weight成立，表明物品成立，表明物品1能够装入，将其装入到背包中，能够装入，将其装入到背包中，置置x1=1，weight=weight-w1=60，i增增1即即i=2；w2weight成立，表明物品成立，表明物品2能够装入，将其装入到背包中，能够装入，将其装入到背包中，置置x2=1，weight=weight-w2=50，i增增1即即i=3；w30，表明只能将物品，表明只能将物

36、品3部分装部分装入，装入比例入，装入比例=weight/w3=50/60=80%，置，置x3=0.8。算法结束，得到算法结束，得到X=1,1,1,0.8,0。i12345wi1020304050vi2030664060vi/wi2.01.52.21.01.2double double knapknap(double (double W,doubleW,double w,double v, w,double v, intint n,doublen,double x) / x) /求解背包问题并返回总价值求解背包问题并返回总价值 intint i i; ;double V=0;double V=0

37、;/V V为总价值为总价值double weight=W;double weight=W;/背包中能装入的余下重量背包中能装入的余下重量for (for (i i= =0;i0;i n;in;i+)+)/初始化初始化x x向量向量xxi i=0;=0;i i=0;=0;while (wwhile (wi iweight)0)if (weight0)/当余下重量大于当余下重量大于0 0 x xi i=weight/w=weight/wi i;/将物品将物品i i的一部分装入的一部分装入V+=xV+=xi i * *vvi i;/累计总价值累计总价值 return V;return V;/返回总价

38、值返回总价值 算法证明算法证明：假设对于假设对于n个物品，按个物品，按vi/wi（1in）值递减排）值递减排序得到序得到1、2、n的序列，即的序列，即v1/w1v2/w2vn/wn。设。设X=x1,x2,xn是本算法找到解。是本算法找到解。如果所有的如果所有的xi都等于都等于1，这个解明显是最优解。否则，设，这个解明显是最优解。否则，设minj是满足是满足xminj1的最小下标。考虑算法的工作方式，很明显，的最小下标。考虑算法的工作方式，很明显，当当iminj时，时，xi=0，并且。设，并且。设X的价值为的价值为V(X)=。niiixv1设设Y=y1,y2,yn是该背包问题的一个最优可行解，因

39、此有是该背包问题的一个最优可行解，因此有，从而有，这个解的价值为，从而有，这个解的价值为V(Y)=。则。则niiiWyw1nininiiiiiiiiywxwyxw1110)(niiiyv1V(X)- -V(Y)=niiiiiiniiiiyxwvwyxv11)()(当当iminj时，时，xi=0，所以，所以xi-yi0，且，且vi/wivminj/wminj。当当i=minj时，时，vi/wi=vminj/wminj。则则V(X)-V(Y)=0njiiiiiijjiiiiiininjiiiiiiniiiiiiyxwvwyxwvwyxwvwyxwvw1minminmin111)()()()(nji

40、iijjijjiiijjininjiiijjiyxwvwyxwvwyxwvw1minminminminminminmin11minmin)()()(niiiijjyxwwv1minmin)(这样与这样与Y是最优解的假设矛盾，也就是说没有哪个可行是最优解的假设矛盾，也就是说没有哪个可行解的价值会大于解的价值会大于V(X)，因此解，因此解X是最优解。是最优解。算法分析：算法分析：快速排序的时间复杂性为快速排序的时间复杂性为O(nlog2n)，while循环的时间为循环的时间为O(n)，所以本算法的时间复杂度为，所以本算法的时间复杂度为O(nlog2n)。问题描述：问题描述：设有设有n个独立的作业个

41、独立的作业1,2,n，由，由m台相台相同的机器同的机器1,2, ,m进行加工处理，作业进行加工处理，作业i所需的处理时间所需的处理时间为为ti（1in），每个作业均可在任何一台机器上加工处），每个作业均可在任何一台机器上加工处理，但未完工前不允许中断，任何作业也不能拆分成更小理，但未完工前不允许中断，任何作业也不能拆分成更小的子作业。的子作业。多机调度问题要求给出一种作业调度方案，使所给的多机调度问题要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内由个作业在尽可能短的时间内由m台机器加工处理完成。台机器加工处理完成。问题求解：问题求解：贪心法求解多机调度问题的贪心策略是最长贪心法求

42、解多机调度问题的贪心策略是最长处理时间作业优先，即把处理时间最长的作业分配给最先空处理时间作业优先，即把处理时间最长的作业分配给最先空闲的机器，这样可以保证处理时间长的作业优先处理，从而闲的机器，这样可以保证处理时间长的作业优先处理，从而在整体上获得尽可能短的处理时间。在整体上获得尽可能短的处理时间。按照最长处理时间作业优先的贪心策略，当按照最长处理时间作业优先的贪心策略，当mn时，只时，只要将机器要将机器i的的0，ti)时间区间分配给作业时间区间分配给作业i即可；即可；当当mn时，首先将时，首先将n个作业依其所需的处理时间从大到小个作业依其所需的处理时间从大到小排序，然后依此顺序将作业分配给

43、空闲的处理机。排序，然后依此顺序将作业分配给空闲的处理机。例如，有例如，有7个独立的作业个独立的作业1,2,3,4,5,6,7，由，由3台机器台机器1,2,3加工处理，各作业所需的处理时间如表加工处理，各作业所需的处理时间如表5.3所示。所示。作业编号作业编号1 12 23 34 45 56 67 7作业的处理时间作业的处理时间2 214144 416166 65 53 3这里这里n=7，m=3，采用贪心法求解的过程如下：，采用贪心法求解的过程如下： 7个作业按处理时间递减排序，其结果如表个作业按处理时间递减排序，其结果如表5.4所示。所示。作业编号作业编号4 42 25 56 63 37 7

44、1 1作业的处理时间作业的处理时间161614146 65 54 43 32 2 先将排序后的前先将排序后的前3个作业分配给个作业分配给3台机器。此时机器的分配情况为台机器。此时机器的分配情况为4,2,5，对应的总处理时间为，对应的总处理时间为16,14,6。 分配余下的作业。分配余下的作业。分配作业分配作业6：3台机器中机器台机器中机器3在时间在时间6后最先空闲，将作业后最先空闲，将作业6分配给它，分配给它，此时机器的分配情况为此时机器的分配情况为4,2,5,6，对应的总处理时间为，对应的总处理时间为16,14,6+5=11。分配作业分配作业3：3台机器中机器台机器中机器3在时间在时间11后

45、最先空闲，将作业后最先空闲，将作业3分配给它，分配给它，此时机器的分配情况为此时机器的分配情况为4,2,5,6,3，对应的总处理时间为，对应的总处理时间为16,14,11+4=15。分配作业分配作业4：3台机器中机器台机器中机器2在时间在时间14后最先空闲，将作业后最先空闲，将作业7分配给它，分配给它，此时机器的分配情况为此时机器的分配情况为4,2,7,5,6,3，对应的总处理时间为，对应的总处理时间为16,14+3=17,15。分配作业分配作业1：3台机器中机器台机器中机器3在时间在时间15后最先空闲，将作业后最先空闲，将作业1分配给它，分配给它，此时机器的分配情况为此时机器的分配情况为4,

46、2,7,5,6,3,1，对应的总处理时间为，对应的总处理时间为16,17,15+2=17。void void MschedulingMscheduling(int P,int T,PlanType S,int n,int m(int P,int T,PlanType S,int n,int m) )/求调度方案求调度方案S S int i,j,k; int i,j,k;for(i=0;im;i+)for(i=0;im;i+)/将将m m个作业分配给个作业分配给m m台机器台机器 Si Si.num=Si.sumt=0;.num=Si.sumt=0;Si.seqSi.num=PiSi.seqSi

47、.num=Pi;/将作业将作业PiPi分配给机器分配给机器i iSi.sumt=Ti;Si.sumt=Ti;/累加处理时间累加处理时间Si.num+;Si.num+;/累计处理作业数累计处理作业数 for(i=m;in;i+)for(i=m;in;i+)/分配余下的作业分配余下的作业 j=0;j=0;for (k=for (k=1;k1;k m;km;k+)+) / /求所有机器中处理时间总数最小的下标求所有机器中处理时间总数最小的下标j jif (Sk.if (Sk.sumtsumtSj.wx，但它比，但它比x深，即深，即lzlx。此时。此时x和和z的带权和为的带权和为wxlx+wzlz。如

48、果交换如果交换x和和z结点的位置，其他不变，则交换后的带权结点的位置，其他不变，则交换后的带权和为和为wxlz+wzlx。则有。则有wxlz+wzlxwxlx+wzlz这是因为这是因为wxlz+wzlx-(wxlx+wzlz)=wx(lz-lx)-wz(lz-lx)=(wx-wz)(lz-lx)wx和和lzlx）。）。这就与交换前的树是最优树的假设矛盾。所以上述命题这就与交换前的树是最优树的假设矛盾。所以上述命题成立。成立。命题命题2：设设T是字符集是字符集C对应的一棵哈夫曼树，结点对应的一棵哈夫曼树，结点x和和y是兄是兄弟，它们的双亲为弟，它们的双亲为z，显然有，显然有wz=wx+wy，现删

49、除结点，现删除结点x和和y，让，让z变变为叶子结点，那么这棵新树为叶子结点，那么这棵新树T1一定是字符集一定是字符集C1=C-x,yz的最的最优树。优树。证明：证明：设设T和和T1的带权路径长度分别为的带权路径长度分别为WPL(T)和和WPL(T1)，则有：则有：WPL(T)= WPL(T1)+wx+wy这是因为这是因为WPL(T1)含有含有T中除中除x、y外的所有叶子结点的带权路外的所有叶子结点的带权路径长度和，另加上径长度和，另加上z的带权路径长度。的带权路径长度。假设假设T1不是最优的，则存在另一棵树不是最优的，则存在另一棵树T2，有：，有：WPL(T2)WPL(T1)由于由于zC1，则

50、，则z在在T2中一定是一个叶子结点。若将中一定是一个叶子结点。若将x和和y加入加入T2中作为结点中作为结点z的左、右孩子，则得到表示字符集的左、右孩子，则得到表示字符集C的前缀树的前缀树T3，且有：且有：WPL(T3)=WPL(T2)+wx+wy由前面几个式子看到由前面几个式子看到WPL(T3)=WPL(T2)+wx+wyWPL(T1)+wx+wy=WPL(T)这与这与T为为C的哈夫曼树的假设矛盾。本命题即证。的哈夫曼树的假设矛盾。本命题即证。命题命题1说明该算法满足贪心选择性质，即通过合并来构说明该算法满足贪心选择性质，即通过合并来构造一棵哈夫曼树的过程可以从合并两个权值最小的字符开始。造一

51、棵哈夫曼树的过程可以从合并两个权值最小的字符开始。命题命题2说明该算法满足最优子结构性质，即该问题的最说明该算法满足最优子结构性质，即该问题的最优解包含其子问题的最优解。所以采用哈夫曼树算法产生的优解包含其子问题的最优解。所以采用哈夫曼树算法产生的树一定是一棵最优树。树一定是一棵最优树。算法分析：算法分析：上述算法采用了两重循环，时间复杂度为上述算法采用了两重循环，时间复杂度为O(n2)。如果采用小根堆，因为从堆中删除两个结点（权值最小的两个如果采用小根堆，因为从堆中删除两个结点（权值最小的两个二叉树根结点）和加入一个新结点的时间复杂度是二叉树根结点）和加入一个新结点的时间复杂度是O(log2n)，这，这样修改后构造哈夫曼树算法的时间复杂度为样修改后构造哈夫曼树算法的时间复杂度为O(nlog2n)。问题描述：问题描述：有一个很大的磁盘文件，其中有若干个无序有一个很大的磁盘文件，其中有若干个无序的整数。设计一个磁盘排序方案将该文件的所有整数按递增的整数。设计一个磁盘排序方案将该文件的所有整数按递增（或递减