算法与分析第一章4贪心

1、清华大学出版社清华大学出版社 王晓东等王晓东等 编著编著华中农业大学理学院华中农业大学理学院2007，37 7n找零钱问题找零钱问题n贪心算法贪心算法总是作出在当前看来最好的选择。也就是说贪总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的种意义上的局部最优选择局部最优选择。n当然，希望贪心算法得到的最终结果也是整体最优的。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源

2、最短路经问题，许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。得到整体最优解，其最终结果却是最优解的很好近似。n活动安排问题活动安排问题就是要在所给的活动集合中选出最大就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的的相容活动子集合，是可以用贪心算法有效求解的很好例子。该问题要求高效地安排一系列争用某一很好例子。该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮公共资源的活动。贪心算法提供了一个简

3、单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。的方法使得尽可能多的活动能兼容地使用公共资源。n设有设有n个活动的集合个活动的集合E=1,2,n，其中每个活动，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动间内只有一个活动能使用这一资源。每个活动i都都有一个要求使用该资源的起始时间有一个要求使用该资源的起始时间si和一个结束时和一个结束时间间fi,且且si fi 。如果选择了活动。如果选择了活动i，则它在半开时间，则它在半开时间区间区间si, fi)内占用资源。若区间内占用资源。若区间si, f

4、i)与区间与区间sj, fj)不相交，则称活动不相交，则称活动i与活动与活动j是相容的。也就是说，是相容的。也就是说，当当sifj或或sjfi时，活动时，活动i与活动与活动j相容相容。n在下面所给出的解活动安排问题的贪心算法在下面所给出的解活动安排问题的贪心算法greedySelector :public static int greedySelector(int s, int f, boolean a)int n=s.length-1;a1=true;int j=1;int count=1;for (int i=2;i=fj) ai=true;j=i;count+;else ai=false

5、;return count;各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序排列 n由于输入的活动以其完成时间的由于输入的活动以其完成时间的非减序排列非减序排列，所以算法，所以算法greedySelector每次总是选择具有每次总是选择具有最早完成时间最早完成时间的相容活的相容活动加入集合动加入集合A中。直观上，按这种方法选择相容活动为未中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是选择的意义是使剩余的可安排时间段极大化使剩余的可安排时间段极大化，以便安排尽，以便安排尽可能多

6、的相容活动。可能多的相容活动。n算法算法greedySelector的效率极高。当输入的活动已按结束的效率极高。当输入的活动已按结束时间的非减序排列，算法只需时间的非减序排列，算法只需O(n)的时间安排的时间安排n个活动，个活动，使最多的活动能相容地使用公共资源。如果所给出的活动使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用未按非减序排列，可以用O(nlogn)的时间重排。的时间重排。n例：设待安排的例：设待安排的11个活动的开始时间和结个活动的开始时间和结束时间按结束时间的非减序排列如下：束时间按结束时间的非减序排列如下：i1234567891011Si130535

7、688212fi4567891011121314n算法算法greedySelector 的计算过程如右图的计算过程如右图所示。图中每行相所示。图中每行相应于算法的一次迭应于算法的一次迭代。阴影长条表示代。阴影长条表示的活动是已选入集的活动是已选入集合合A的活动，而空的活动，而空白长条表示的活动白长条表示的活动是当前正在检查相是当前正在检查相容性的活动。容性的活动。n若被检查的活动若被检查的活动i的开始时间的开始时间Si小于最近选择的活动小于最近选择的活动j的结束时间的结束时间fi，则不选择活动，则不选择活动i，否则选择活动，否则选择活动i加加入集合入集合A中。中。n贪心算法并不总能求得问题的贪

8、心算法并不总能求得问题的整体最优解整体最优解。但对于。但对于活动安排问题，贪心算法活动安排问题，贪心算法greedySelector却总能却总能求得的整体最优解，即它最终所确定的相容活动集求得的整体最优解，即它最终所确定的相容活动集合合A的规模最大。这个结论可以用数学归纳法证明。的规模最大。这个结论可以用数学归纳法证明。n本节着重讨论可以用贪心算法求解的问题的一般本节着重讨论可以用贪心算法求解的问题的一般特征。特征。n对于一个具体的问题，怎么知道是否可用贪心算对于一个具体的问题，怎么知道是否可用贪心算法解此问题，以及能否得到问题的最优解呢法解此问题，以及能否得到问题的最优解呢?这这个问题很难给

9、予肯定的回答。个问题很难给予肯定的回答。n但是，从许多可以用贪心算法求解的问题中看到但是，从许多可以用贪心算法求解的问题中看到这类问题一般具有这类问题一般具有2个重要的性质：个重要的性质：贪心选择性贪心选择性质质和和最优子结构性质最优子结构性质。n所谓所谓贪心选择性质贪心选择性质是指所求问题的整体最优解可以通是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。态规划算法的主要区别。n动态规划算法通常以动态规划算法

10、通常以自底向上自底向上的方式解各子问题，而的方式解各子问题，而贪心算法则通常以贪心算法则通常以自顶向下自顶向下的方式进行，以迭代的方的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。问题简化为规模更小的子问题。n对于一个具体问题，要确定它是否具有贪心选择性质，对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体必须证明每一步所作的贪心选择最终导致问题的整体最优解。最优解。n当一个问题的最优解包含其子问题的最优当一个问题的最优解包含其子问题的最优解时，称此问题具有

11、最优子结构性质。问解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用动态规题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。划算法或贪心算法求解的关键特征。n 贪心算法和动态规划算法都要求问题具有最优子贪心算法和动态规划算法都要求问题具有最优子结构性质，这是结构性质，这是2类算法的一个共同点。类算法的一个共同点。n 对于具有最优子结构的问题应该选用贪心算法还对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解是动态规划算法求解?是否能用动态规划算法求解的是否能用动态规划算法求解的问题也能用贪心算法求解问题也能用贪心算法求解?n 下面研究下面研究2个经典

12、的组合优化问题，并以此说明个经典的组合优化问题，并以此说明贪心算法与动态规划算法的主要差别。贪心算法与动态规划算法的主要差别。n0-1背包问题背包问题n背包问题背包问题n0-1背包问题：背包问题：n给定给定n种物品和一个背包。物品种物品和一个背包。物品i的重量是的重量是Wi，其价，其价值为值为Vi，背包的容量为，背包的容量为C。应如何选择装入背包的物。应如何选择装入背包的物品，使得装入背包中物品的总价值最大？品，使得装入背包中物品的总价值最大？n在选择装入背包的物品时，对每种物品在选择装入背包的物品时，对每种物品i只有只有2种选择，种选择，即装入背包或不装入背包。不能将物品即装入背包或不装入背

13、包。不能将物品i装入背包多装入背包多次，也不能只装入部分的物品次，也不能只装入部分的物品i。n背包问题背包问题:n与与0-1背包问题类似，所不同的是在选择物品背包问题类似，所不同的是在选择物品i装入背包时，装入背包时，可以选择物品可以选择物品i的一部分，而不一定要全部装入背包，的一部分，而不一定要全部装入背包，1in。n这这2类问题都具有最优子结构性质，极为相似，但背包类问题都具有最优子结构性质，极为相似，但背包问题可以用贪心算法求解，而问题可以用贪心算法求解，而0-1背包问题却不能用贪背包问题却不能用贪心算法求解。心算法求解。 n首先计算每种物品单位首先计算每种物品单位重量的价值重量的价值V

14、i/Wi，然，然后，依贪心选择策略，后，依贪心选择策略，将尽可能多的单位重量将尽可能多的单位重量价值最高的物品装入背价值最高的物品装入背包。若将这种物品全部包。若将这种物品全部装入背包后，背包内的装入背包后，背包内的物品总重量未超过物品总重量未超过C，则选择单位重量价值次则选择单位重量价值次高的物品并尽可能多地高的物品并尽可能多地装入背包。依此策略一装入背包。依此策略一直地进行下去，直到背直地进行下去，直到背包装满为止。包装满为止。n具体算法可描述如下：具体算法可描述如下：void Knapsack(int n,float M,float v,float w,float x)Sort(n,v,

15、w);int i;for (i=1;i=n;i+) xi=0;float c=M;for (i=1;ic) break;xi=1;c-=wi;if (i102030501.￥60 2.￥100 3.￥120 4.背包 =￥220=￥160=￥180=￥2401002012030601010020601012030601010020802012020300-1背包问题的例子例例3.1 背包问题的实例背包问题的实例 设，设，n=3，M=20， (p1,p2,p3) = (25,24,15)， (w1,w2,w3) = (18,15,10)。 可能的可行解如下：可能的可行解如下： (x1,x2,x3

16、) (1/2,1/3,1/4) 16.5 24.25 /没有装没有装满背包满背包/ (1, 2/15, 0 ) 20 28.2 (0, 2/3, 1) 20 31 (0, 1, 1/2) 20 31.5iixpiixw2. 贪心策略求解贪心策略求解 度量标准的选择：三种不同的选择度量标准的选择：三种不同的选择1）以）以目标函数目标函数作为度量作为度量 即，每装入一件物品，就使背包获得即，每装入一件物品，就使背包获得最大最大可能的可能的效益增量效益增量。 该度量标准下的处理规则是：该度量标准下的处理规则是： 按效益值的按效益值的非增非增次序将物品一件件地放入到背包；次序将物品一件件地放入到背包；

17、 如果正在考虑的物品放不进去，则只取其一部分装满背包：如果该如果正在考虑的物品放不进去，则只取其一部分装满背包：如果该物品的一部分不满足获得最大效益增量的度量标准，则在物品的一部分不满足获得最大效益增量的度量标准，则在剩下剩下的物品种选的物品种选择可以获得最大效益增量的其它物品，将它或其一部分装入背包。择可以获得最大效益增量的其它物品，将它或其一部分装入背包。 如：若如：若M=2M=2, ,背包外还剩两件物品背包外还剩两件物品i,ji,j，且有，且有(pi 4，wi4) 和和(pj 3，wj2)，则下一步应选择，则下一步应选择j而非而非i放入背包：放入背包： pi/2 = 2 pj 3实例分析

18、（例实例分析（例3.1) p1p2 p3 首先将首先将物品物品1 1放入背包，此时放入背包，此时x11，背包获得，背包获得p125的效益增量，同时背的效益增量，同时背包容量减少包容量减少w118个单位，剩余空间个单位，剩余空间M=2M=2。 其次考虑其次考虑物品物品2 2和和3 3。就。就M=2M=2而言有，只能选择物品而言有，只能选择物品2 2或或3 3的的一部分一部分装入背包。装入背包。 物品物品2 2： 若若 x22/15， 则则 p2 x216/53.1 物品物品3 3： 若若 x32/10， 则则 p3 x33 为使背包的效益有最大的增量，应选择为使背包的效益有最大的增量，应选择物品

19、物品2的的2/15装包，即装包，即 x22/15 最后，背包装满，最后，背包装满， M=0M=0，物品物品3 3不装包，即不装包，即x30 。 背包最终可以获得背包最终可以获得效益值效益值 x1 p1 x2 p2x3 p3 28.2 (次优解次优解,非问题的最优解非问题的最优解)2）以）以容量容量作为度量标准作为度量标准 以以目标函数目标函数作为度量标准所存在的问题：尽管背包的效益值作为度量标准所存在的问题：尽管背包的效益值每次得到了最大的增加，但背包容量也过快地被消耗掉了，从而每次得到了最大的增加，但背包容量也过快地被消耗掉了，从而不能装入不能装入“更多更多”的物品。的物品。 改进：让背包改

20、进：让背包容量容量尽可能慢地消耗，从而可以尽量装入尽可能慢地消耗，从而可以尽量装入“较较多多”的物品。的物品。 即，新的标准是：以即，新的标准是：以容量容量作为度量作为度量 该度量标准下的处理规则：该度量标准下的处理规则： 按物品按物品重量的非降次序重量的非降次序将物品装入到背包；将物品装入到背包； 如果正在考虑的物品放不进去，则只取其一部分装满背包；如果正在考虑的物品放不进去，则只取其一部分装满背包；实例分析（例实例分析（例3.1) w3w2 w1 首先将首先将物品物品3 3放入背包，此时放入背包，此时x31，背包容量减少，背包容量减少w310个单个单位，还剩余空间位，还剩余空间M=10M=

21、10。同时同时，背包获得背包获得p315的效益增量的效益增量。 其次考虑其次考虑物品物品2 2。就。就M=10M=10而言有，也只能选择物品而言有，也只能选择物品2 2的的一部分一部分装装入背包。入背包。下一步将放入下一步将放入物品物品2的的10/15装包，即装包，即 x210/152/3 最后，背包装满最后，背包装满M=0M=0，物品物品1 1将不能装入背包，故将不能装入背包，故 x10 。 背包最终可以获得背包最终可以获得效益值效益值 x1 p1 x2 p2x3 p3 31 (次优解次优解,非问题的最优解非问题的最优解) 存在的问题：效益值没有得到存在的问题：效益值没有得到“最大程度最大程

22、度”的增加的增加3）最优的度量标准）最优的度量标准 影响背包效益值得因素：影响背包效益值得因素：n 背包的背包的容量容量Mn 放入背包中的物品的重量及其可能带来的效益值放入背包中的物品的重量及其可能带来的效益值 可能的策略可能的策略是：在背包效益值的增长速率和背包容量是：在背包效益值的增长速率和背包容量消耗速率之间取得消耗速率之间取得平衡平衡，即每次装入的物品应使它所占用的，即每次装入的物品应使它所占用的每一每一单位容量单位容量能获得当前最大的单位效益。能获得当前最大的单位效益。 在这种策略下的在这种策略下的量度量度是：已装入的物品的累计效益值是：已装入的物品的累计效益值与所用容量之比。与所用

23、容量之比。 故，新的故，新的量度标准量度标准是：每次装入要使累计效益值与所用是：每次装入要使累计效益值与所用容量的比值有最多的增加（首次装入）和最小的减小（其后容量的比值有最多的增加（首次装入）和最小的减小（其后的装入）。的装入）。 此时，将按照物品的单位效益值：此时，将按照物品的单位效益值：pi/wi 比值的非增次比值的非增次序考虑。序考虑。实例分析（例实例分析（例3.1) p1/ /w1p3/ /w3 p2/ /w2 首先，将首先，将物品物品2 2放入背包，此时放入背包，此时x21，背包容量减少，背包容量减少w215 个单位，还剩余空间个单位，还剩余空间M=5M=5。同时，。同时，背包获得

24、背包获得p224的的 效益增量效益增量。 其次，在剩下的其次，在剩下的物品物品1 1和和3 3中，应选择物品中，应选择物品3,3,且就且就M=5M=5而言有，而言有， 只能放入物品只能放入物品3 3的的一部分一部分到背包中到背包中 。即即 x35/101/2 最后，背包装满最后，背包装满M=0M=0，物品物品1 1将不能装入背包，故将不能装入背包，故x10 。 最终可以获得的背包最终可以获得的背包效益值效益值 x1 p1 x2 p2x3 p3 31.5 (最优解最优解)算法算法4.2 背包问题的贪心算法背包问题的贪心算法 procedure GREEDYKNAPSACK(P,W,M,X,n)

25、/P(1:n)和和W(1:n)分别含有按分别含有按P(i)/W(i)P(i1)/W(i1)排排序的序的n 件物品的效益值和重量。件物品的效益值和重量。M是背包的容量大小，而是背包的容量大小，而X(1:n)是解是解 向量向量/ real P(1:n), W(1:n), X(1:n), M, cu; integer I,n X0 /将解向量初始化为将解向量初始化为0/ cuM /cu是背包的剩余容量是背包的剩余容量/ for i1 to n do if W(i) cu then exit endif X(i) 1 cu cu-W(i) repeat if in then X(i) cu/W(i)

26、endif end GREEDY-KNAPSACK 即证明：由第三种策略所得到的贪心解是问题的即证明：由第三种策略所得到的贪心解是问题的最优解最优解。 最优解最优解的含义：在满足约束条件的情况下，使目标函数的含义：在满足约束条件的情况下，使目标函数取极（大或小）值的可行解。取极（大或小）值的可行解。 贪心解是贪心解是可行解可行解，故只需证明：贪心解可使目标函数取得，故只需证明：贪心解可使目标函数取得极值。极值。 证明的证明的基本思想基本思想： 将此贪心解与（假设中的）任一最优解将此贪心解与（假设中的）任一最优解相比较相比较。 如果这两个解相同，则显然贪心解就是最优解。如果这两个解相同，则显然贪

27、心解就是最优解。 如果这两个解不同，就设法去找两者开始如果这两个解不同，就设法去找两者开始不同不同的第一个分量位置的第一个分量位置i，然后设法用贪心解的这个然后设法用贪心解的这个xi去去替换替换最优解对应的分量最优解对应的分量 ，并证明最优解在分，并证明最优解在分量代换前后总的效益值没有任何变化量代换前后总的效益值没有任何变化(且不违反约束条件且不违反约束条件)。 然后比较二者。若还不同，则然后比较二者。若还不同，则反复进行代换，直到代换后产生的反复进行代换，直到代换后产生的“最优解最优解”与贪心解完全一样。与贪心解完全一样。 在上述在上述代换中，最优解的代换中，最优解的效益值没有任何损失效益

28、值没有任何损失，从而证明贪心解的，从而证明贪心解的 效益值与代换前后最优解的效益值相同。即，贪心解如同最优解一效益值与代换前后最优解的效益值相同。即，贪心解如同最优解一 样可取得目标函数的最大样可取得目标函数的最大/最小值。最小值。 从而得证：该从而得证：该贪心解贪心解即是问题的即是问题的最优解最优解。 定理定理4.1 如果如果p1/w1 p2/w2 pn/wn,则算法则算法GREEDY-KNAPSACK对于给定的背包问题实例生成一个最优解。对于给定的背包问题实例生成一个最优解。证明证明： 设设X=(x1, x2, , xn)是是GREEDY-KNAPSACK所生成的所生成的贪心解贪心解。 如

29、果所有的如果所有的xi都等于都等于1,则显然则显然X就是问题的就是问题的最优解最优解。否则，。否则， 设设j是使是使xi1的最小下标。由算法的执行过程可知，的最小下标。由算法的执行过程可知，l xi=1 1ij,l 0 xj 1l xi=0 jin 假设假设Y是问题的最优解：是问题的最优解：Y=(y1, y2, , yn) 且有：且有： 若若X Y，则，则X就是最优解。否则，就是最优解。否则， X和和Y至少在至少在1个分量上存在不同。个分量上存在不同。 设设k是使得是使得yk xk的最小下标，则有的最小下标，则有yk xk。可分以下情况。可分以下情况说明：说明： a) 若若kj，则，则xk=1

30、。因为。因为yk xk,从而有从而有yk xk b) 若若k=j，由于，由于 ，且对，且对1ij，有，有yi=xi=1,而对而对jin,有有xi0；故此时若；故此时若ykxk，则将有，则将有 ，与，与Y是可行是可行解相矛盾。而解相矛盾。而yk xk,所以所以yk xk c) 若若kj，则，则 ，不能成立，不能成立Mxwii Mywii Mywii Myiiw 在在Y中作以下调整：将中作以下调整：将yk增加到增加到xk，因为，因为ykxk,为保持为保持解的可行性，必须从解的可行性，必须从(yk+1,yn)中减去同样多的量。设调整中减去同样多的量。设调整后的解为后的解为Z=(z1, z2, , z

31、n)，其中，其中zixi，1ik，且有：，且有： Z的效益值有：的效益值有：nikkkkiiiyzwzyw)()(niiiinikiikkkkkiiniiiwpwzywpwyzypzp11/)(/)(nikkinikiikkkiiwpwzywyzyp1/)()(niiiyp1差值差值0由以上分析得，由以上分析得，n若若 ，则，则Y将不是最优解；将不是最优解；n若若 ，则或者，则或者Z=X，则，则X就是最优解；就是最优解；n或者或者ZX，则重复以上替代过程，或者证明，则重复以上替代过程，或者证明Y不是最优解，不是最优解，或者把或者把Y转换成转换成X，从而证明，从而证明X是最优解是最优解iiiiy

32、pzpiiiiypzpn有一批集装箱要装上一艘载重量为有一批集装箱要装上一艘载重量为c的轮船。其中集装箱的轮船。其中集装箱i的重量为的重量为Wi。最优装载问题要求确定在装载体积不受限制。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。的情况下，将尽可能多的集装箱装上轮船。n该问题可形式化描述为该问题可形式化描述为n其中变量其中变量xi=0表示不装入集装箱表示不装入集装箱i，xi=1表示装入集装箱表示装入集装箱i。nixcxwxiniiinii110max11，n最优装载问题可用贪心算法求解。采用重量最优装载问题可用贪心算法求解。采用重量最轻者先装的贪心选择策略，可产

33、生最优装最轻者先装的贪心选择策略，可产生最优装载问题的最优解。具体算法描述如下：载问题的最优解。具体算法描述如下： templatevoid Loading(int x, Type w, Type c, int n)int *t = new int n+1;Sort(w, t, n);for (int i = 1; i = n; i+) xi = 0;for (int i = 1; i = n & wti m时，首先将时，首先将n个作业依其所需的处理时间从大到小个作业依其所需的处理时间从大到小排序。然后依此顺序将作业分配给空闲的处理机。算法所排序。然后依此顺序将作业分配给空闲的处理机。

34、算法所需的计算时间为需的计算时间为O(nlogn)。n例如，设例如，设7个独立作业个独立作业1,2,3,4,5,6,7由由3台机器台机器M1，M2和和M3加工处理。各作业加工处理。各作业所需的处理时间分别为所需的处理时间分别为2,14,4,16,6,5,3。按算法。按算法greedy产生产生的作业调度如下图所示，所需的加工时间的作业调度如下图所示，所需的加工时间为为17。下面的关于下面的关于极大独立子集的性质是很有用的。的性质是很有用的。定理4.1：拟阵M中所有极大独立子集大小相同。这个定理可以用反证法证明。这个定理可以用反证法证明。若对拟阵若对拟阵M=(S,I)M=(S,I)中的中的S S指

35、定权函数指定权函数W W，使得对于任意，使得对于任意x x S S，有，有W(x)0W(x)0，则称拟阵，则称拟阵M M为为带权拟阵。依此权函数，。依此权函数，S S的任一子集的任一子集A A的权定义为的权定义为 。2.关于带权拟阵的贪心算法许多可以用贪心算法求解的问题可以表示为求带权拟许多可以用贪心算法求解的问题可以表示为求带权拟阵的阵的最大权独立子集问题。 AxxWAW)()(给定带权拟阵给定带权拟阵M=(S,I)M=(S,I)，确定，确定S S的独立子集的独立子集A A I I使得使得W(A)W(A)达到最大。这种使达到最大。这种使W(A)W(A)最大的独立子集最大的独立子集A A称为拟

36、阵称为拟阵M M的的最优子集。由于。由于S S中任一元素中任一元素x x的权的权W(x)W(x)是正的，因此，是正的，因此，最优子集也一定是极大独立子集。例如，在最小生成树问题可以表示为确定带权拟阵在最小生成树问题可以表示为确定带权拟阵 的最优子集问题。求带权拟阵的最优子集的最优子集问题。求带权拟阵的最优子集A A的算法可用于解的算法可用于解最小生成树问题。最小生成树问题。下面给出求下面给出求带权拟阵最优子集的贪心算法。该算法以的贪心算法。该算法以具有正权函数具有正权函数W W的带权拟阵的带权拟阵M=(S,I)M=(S,I)作为输入，经计算后输作为输入，经计算后输出出M M的最优子集的最优子集

37、A A。GMnSet Set greedy (M,W) (M,W)nA=A=; ;n 将将S S中元素依权值中元素依权值W W（大者优先）组成优先队列；（大者优先）组成优先队列；n while (S!=while (S!=) ) n S.removeMax(x); S.removeMax(x);n if (Ax if (Ax I) A=Ax;I) A=Ax;n n return A return An 算法算法greedy的计算时间复杂性为的计算时间复杂性为 。引理4.2(拟阵的贪心选择性质)设设M=(S,I)M=(S,I)是具有权函数是具有权函数W W的带权拟阵，且的带权拟阵，且S S中元素

38、依中元素依权值从大到小排列。又设权值从大到小排列。又设x x S S是是S S中第一个使得中第一个使得xx是独立是独立子集的元素，则存在子集的元素，则存在S S的最优子集的最优子集A A使得使得x x A A。算法算法greedy在以贪心选择构造最优子集在以贪心选择构造最优子集A A时，首次选时，首次选入集合入集合A A中的元素中的元素x x是单元素独立集中具有最大权的元素。是单元素独立集中具有最大权的元素。此时可能已经舍弃了此时可能已经舍弃了S S中部分元素。可以证明这些被舍弃的中部分元素。可以证明这些被舍弃的元素不可能用于构造最优子集。元素不可能用于构造最优子集。)(log(nnfnnO引

39、理4.3：设设M=(S,I)M=(S,I)是拟阵。若是拟阵。若S S中元素中元素x x不是空集不是空集的可的可扩展元素，则扩展元素，则x x也不可能是也不可能是S S中任一独立子集中任一独立子集A A的可扩展元素。的可扩展元素。引理4.4(拟阵的最优子结构性质)设设x x是求带权拟阵是求带权拟阵M M(S(S，I)I)的最优子集的贪心算法的最优子集的贪心算法greedy所选择的所选择的S S中的第一个元素。那么，原问题可简化为中的第一个元素。那么，原问题可简化为求带权拟阵求带权拟阵M M=(S=(S,I,I) )的的最优子集问题，其中：问题，其中：S S=y|y=y|y S S且且x,y x,

40、y III I=B|B=B|B S-xS-x且且Bx Bx IIM M的权函数是的权函数是M M的权函数在的权函数在S S上的限制上的限制( (称称M M为为M M关关于元素于元素x x的的收缩) )。定理4.5(带权拟阵贪心算法的正确性)设设M M(S,I)(S,I)是具有权函数是具有权函数W W的带权拟阵，算法的带权拟阵，算法greedygreedy返回返回M M的最优子集。的最优子集。3.任务时间表问题给定一个给定一个单位时间任务的有限集的有限集S S。关于。关于S S的一个的一个时间表用于描述用于描述S S中单位时间任务的执行次序。时间中单位时间任务的执行次序。时间表中第表中第1 1个

41、任务从时间个任务从时间0 0开始执行直至时间开始执行直至时间1 1结束，第结束，第2 2个任务从时间个任务从时间1 1开始执行至时间开始执行至时间2 2结束，结束，第，第n n个任个任务从时间务从时间n-1n-1开始执行直至时间开始执行直至时间n n结束。结束。具有具有截止时间和和误时惩罚的单位时间任务时间表问题的单位时间任务时间表问题可描述如下。可描述如下。(1) n(1) n个单位时间任务的集合个单位时间任务的集合S=1,2,S=1,2,n,n；(2) (2) 任务任务i i的截止时间的截止时间 ,1in,1 n,1in,1 n，即要求，即要求任务任务i i在时间在时间 之前结束；之前结束

42、；(3) (3) 任务任务i i的误时惩罚的误时惩罚 ,1in,1in,即任务即任务i i未在时间未在时间 之前结束将招致的之前结束将招致的 惩罚；若按时完成则无惩罚。惩罚；若按时完成则无惩罚。任务时间表问题要求确定要求确定S S的一个时间表（最优时间的一个时间表（最优时间表）使得总误时惩罚达到最小。表）使得总误时惩罚达到最小。idididiwiwid这个问题看上去很复杂，然而借助于这个问题看上去很复杂，然而借助于拟阵，可以用，可以用带权拟阵的贪心算法有效求解。有效求解。对于一个给定的对于一个给定的S的时间表，在截止时间之前完成的的时间表，在截止时间之前完成的任务称为任务称为及时任务，在截止时间之后完成的任务称为，在截止时间之后完成的任务称为误时任务。S的任一时间表可以调整成的任一时间表可以调整成及时优先形式，即其中所，即其中所有及时任务先于误时任务，而不影响原时间表中各任务的有及时任务先于误时任务，而不影响原时间表中各任务的及时或误时性质。及时或误时性质