第五章贪心算法 §1基本思想 找零钱假如售货员需要找给小孩67美分的零钱。现在,售货员 手中只有25美分、10美分、5美分和1美分的硬币。在小孩的催促 下,售货员想尽快将钱找给小孩。她的做法是:先找不大于67美分 的最大硬币25美分硬币,再找不大于67-25=42美分的最大硬币 25美分硬币,再找不大于42-25=17美分的最大硬币10美分硬币, 再找不大于17-10=7美分的最大硬币5美分硬币,最后售货员再找 出两个1美分的硬币。至此,售货员共找给小孩6枚硬币。售货员的 原则是拿尽可能少的硬币个数找给小孩。从另一个角度看,如果售货 员将捡出的硬币逐一放在手中,最后一起交给小孩,那么售货员想使 自己手中的钱数增加的尽量快些,所以每一次都尽可能地捡面额大的 硬币 装载问题有一艘大船用来装载货物。假设有n个货箱,它们的 体积相同,重量分别是W1,w2…wn,货船的最大载重量是c。目标 是在船上装最多货箱该怎样装?如果用x=1表示装第i个货箱,而 x=0表示不装第i个货箱,则上述问题是解优化问题:求x1,x2…, 满足 wx x 1 贪心方法,顾名思义,是在决策中总是作出在当前看来是最好的
第五章 贪心算法 §1 基本思想 找零钱 假如售货员需要找给小孩 67 美分的零钱。现在，售货员 手中只有 25 美分、10 美分、5 美分和 1 美分的硬币。在小孩的催促 下，售货员想尽快将钱找给小孩。她的做法是：先找不大于 67 美分 的最大硬币 25 美分硬币，再找不大于 67－25＝42 美分的最大硬币 25 美分硬币，再找不大于 42－25＝17 美分的最大硬币 10 美分硬币， 再找不大于 17－10＝7 美分的最大硬币 5 美分硬币，最后售货员再找 出两个 1 美分的硬币。至此，售货员共找给小孩 6 枚硬币。售货员的 原则是拿尽可能少的硬币个数找给小孩。从另一个角度看，如果售货 员将捡出的硬币逐一放在手中，最后一起交给小孩，那么售货员想使 自己手中的钱数增加的尽量快些，所以每一次都尽可能地捡面额大的 硬币。 装载问题 有一艘大船用来装载货物。假设有 n 个货箱，它们的 体积相同，重量分别是w w wn , , 1 2L ，货船的最大载重量是 c。目标 是在船上装最多货箱该怎样装？如果用 = 1 i x 表示装第 i 个货箱，而 = 0 i x 表示不装第 i 个货箱，则上述问题是解优化问题：求 x1, x2,⋅⋅⋅⋅⋅⋅， xn， 满足 x c i n i ∑ i ≤ =1 w (5.1) 使得 ∑ = n i i x 1 max (5.2) 贪心方法，顾名思义，是在决策中总是作出在当前看来是最好的
选择。例如找零钱问题中,售货员每捡一个硬币都想着使自己手中的 钱尽快达到需要找钱的总数。在装载问题中,每装一个货箱都想着在 不超重的前提下让船装进更多的箱子。但是贪心方法并未考虑整体最 优解,它所作出的选择只是在某种意义上的局部最优选择。当然,在 采用贪心算法时未必不希望结果是整体最优的。事实上,有相当一部 分问题,采用贪心算法能够达到整体最优。如前面的找零钱问题以及 后面将要讲到的单点源最短路径问题、最小生成树问题、工件排序问 题等。为了更好理解贪心算法,我们将装载问题稍加推广,考虑O/1 背包问题。 0/1背包问题已知容量为M的背包和n件物品。第i件物品的 重量为w,价值是p。因而将物品i的一部分x放进背包即获得px 的价值。问题是:怎样装包使所获得的价值最大。即是如下的优化问 题 max∑px (53) ∑x1≤M l≤i≤n 0≤x1≤1,P1>0,w1>0,1≤i 采用贪心方法,有几种原则可循:a.每次捡最轻的物品装;b.每次捡 价值最大的装;c每次装包时既考虑物品的重量又考虑物品的价值 也就是说每次捡单位价值p1/w1最大的装。按原则a来装只考虑到多 装些物品,但由于单位价值未必高,总价值不能达到最大;按原则b 来装,每次选择的价值最大,但同时也可能占用了较大的空间,装的 物品少,未变能够达到总价值最大。比较合理的原则是c。事实上
选择。例如找零钱问题中，售货员每捡一个硬币都想着使自己手中的 钱尽快达到需要找钱的总数。在装载问题中，每装一个货箱都想着在 不超重的前提下让船装进更多的箱子。但是贪心方法并未考虑整体最 优解，它所作出的选择只是在某种意义上的局部最优选择。当然，在 采用贪心算法时未必不希望结果是整体最优的。事实上，有相当一部 分问题，采用贪心算法能够达到整体最优。如前面的找零钱问题以及 后面将要讲到的单点源最短路径问题、最小生成树问题、工件排序问 题等。为了更好理解贪心算法，我们将装载问题稍加推广，考虑 0/1 背包问题。 0/1 背包问题 已知容量为 M 的背包和 n 件物品。第 i 件物品的 重量为 wi，价值是 pi。因而将物品 i 的一部分 xi放进背包即获得 pixi 的价值。问题是：怎样装包使所获得的价值最大。即是如下的优化问 题： ∑ ≤i≤n i i p x 1 max (5.3) x p w i n w x M i i i i n i i ≤ ≤ > > ≤ ≤ ∑ ≤ ≤ ≤ 0 1, 0, 0, 1 1 (5.4) 采用贪心方法，有几种原则可循：a.每次捡最轻的物品装；b.每次捡 价值最大的装；c.每次装包时既考虑物品的重量又考虑物品的价值， 也就是说每次捡单位价值 i wi p 最大的装。按原则 a 来装只考虑到多 装些物品，但由于单位价值未必高，总价值不能达到最大；按原则 b 来装，每次选择的价值最大，但同时也可能占用了较大的空间，装的 物品少，未变能够达到总价值最大。比较合理的原则是 c。事实上
按照原则c来装,确实能够达到总价值最大。 0/1背包问题贪心算法 Greedy Knapsack(p,w,M,x,n)∥价值数组p[n]、重量数组w[1nl, ∥它们元素的排列顺序是p[iwi]≥p[i+1/w[t+1l,M是背包容量, ∥x是解向量 real pll: n, w[l: n), x[l n], M,rc, nteger 1, n, x=0,∥将解向量初始化为零 rc=M;∥/是背包剩余容量初始化为M for i from 1 to n do if wi> rc then exit endif x[1F1; rc=rc-w[i]; endfor if i<n then x[=rc/w[i] endif end greedy Knapsack 定理1如果p[1]/w[2]≥p[2]/w[2]≥……≥p[n/w[n],则 GreedyKnapsack对于给定的0/1背包问题实例生成一个最优解。 证明设x=(x,x2,…,xn)是 Greedy Knapsack所生成的解,但不是 最优解。因而必有某个x不为1。不妨设x是第一个这样的分量。于 是,当1≤ij时,x1=1;当jin时,x1=0;当ij时,0≤x<1
按照原则 c 来装，确实能够达到总价值最大。 0/1 背包问题贪心算法 GreedyKnapsack(p, w, M, x, n) //价值数组 p[1:n]、重量数组 w[1:n]， //它们元素的排列顺序是p[i]/w[i]≥p[i+1]/w[i+1]; M是背包容量， // x 是解向量 real p[1:n], w[1:n], x[1:n], M, rc; integer i, n; x=0; // 将解向量初始化为零 rc=M; // 是背包剩余容量初始化为 M for i from 1 to n do if w[i] > rc then exit endif x[i]=1; rc=rc-w[i]; endfor if i≤n then x[i]=rc/w[i]; endif end GreedyKnapsack 定理 1 如 果 p[1]/w[2] ≥ p[2]/w[2] ≥ ⋅⋅⋅⋅⋅⋅ ≥ p[n]/w[n], 则 GreedyKnapsack 对于给定的 0/1 背包问题实例生成一个最优解。 证明 设 x=(x1,x2,⋅⋅⋅⋅⋅⋅,xn)是 GreedyKnapsack 所生成的解，但不是 最优解。因而必有某个 xi不为 1。不妨设 xj是第一个这样的分量。于 是，当 1≤ i<j 时，xi＝1；当 j<i≤n 时，xi＝0；当 i=j 时，0≤xi<1
因为ⅹ不是最优解,则存在解向量y=(y,y,……,y,使得 ∑Py>∑Px。不妨假定∑wx=M。设k是使得y≠x的最小 下标,则yx可推出∑1y>∑x=M,y不是解向量,矛盾 现在取新的向量z=(z1,z2,…,zn)满足 Z1=y1,Z2-y2,………,Zk-1=yk-1,Zk=Xn 0≤z=≤yk,…,0≤z≤y而且∑w;(v1-z,)=wk(zk-yk) k+l≤i≤ 这样的向量z是存在的,而且是0/1背包问题的解,因为 11=∑Wy1+Wk=k∑ :2 l≤i<n l<i≤k-1 k+l≤i<n ∑y1+∑W (5.5) l≤i≤k-1 k≤i≤n ∑wy1≤M l≤i<n 至此,我们找到一个新的解向量z。以下证明它的总价值不小于y的 总价值: ∑P1=∑Py+(=k-yk)形kPk/Wk-∑(y1-)wP1/w1 l≤i<n k<isn ≥∑Py+(=k-yk)k-∑(-=)m|p4/k(5.6) k+1≤i<n ∑Py 中间的不等式是由于当Ik时有p/w≥p1/w而得。但与x的不同分量 的个数比y与x的不同分量的个数至少减少一个。以z代替y进行上 面的讨论,我们又可以找到新的解向量z,如此等等,由于分量的个
因为 x 不是最优解，则存在解向量 y=(y1,y2,⋅⋅⋅⋅⋅⋅,yn), 使 得 ∑ i i > ∑ i i p y p x 。不妨假定∑wi xi = M 。设 k 是使得 yk≠ xk的最小 下标，则 yk xk可推出∑wi yi > ∑wi xi = M ，y 不是解向量，矛盾。 现在取新的向量 z=(z1,z2,⋅⋅⋅⋅⋅⋅,zn)满足 z1=y1, z2=y2,⋅⋅⋅⋅⋅⋅, zk-1= yk-1, zk= xk 0≤zk+1≤yk+1, ⋅⋅⋅⋅⋅⋅, 0≤zn≤yn而且 ( ) ( ) 1 k k k k i n i i i ∑w y − z = w z − y + ≤ ≤ 这样的向量 z 是存在的，而且是 0/1 背包问题的解，因为 w y M w y w y w z w y w z w z i n i i k i n i i i k i i k i n k k i i i k i i i n i i = ≤ = + = + + ∑ ∑ ∑ ∑ ∑ ∑ ≤ ≤ ≤ ≤ − ≤ ≤ ≤ ≤ ≤ ≤ − + ≤ ≤ 1 1 1 1 1 1 1 (5.5) 至此，我们找到一个新的解向量 z。以下证明它的总价值不小于 y 的 总价值： ∑ ∑ ∑ ∑ ∑ ∑ ≤ ≤ ≤ ≤ + ≤ ≤ ≤ ≤ ≤ ≤ k 时有 pk/wk≥pi/wi而得。但与 x 的不同分量 的个数比 y 与 x 的不同分量的个数至少减少一个。以 z 代替 y 进行上 面的讨论，我们又可以找到新的解向量 z'，如此等等，由于分量的个
数n有限,必到某一步停止,我们能找到解向量y*,它和x有相同的 分量,又与y又有相同的总价值(大于x的总价值),矛盾。这个矛 盾源于ⅹ不是最优解的假设。故,x是最优解。 贪心算法主要用于处理优化问题。每个优化问题都是由目标函数 和约東条件组成。满足约束条件的解称为可行解,而那些使得目标函 数取极值的可行解称为最优解。如0/背包问题是一个优化问题,式 (53)中的函数是目标函数,而(54)式描述的要求是约束条件,这里优 化是使目标函数取最大值。贪心算法在每一步的决策中虽然没有完全 顾忌到问题整体优化,但在局部择优中是朝着整体优化的方向发展 的。为此,贪心算法首先要确定一个度量准则,每一步都是按这个准 则选取优化方案。如0/1背包问题的贪心准则是选取单位价值pw最 大物品,而装载问题的贪心算法选取的准则是选取最轻的货箱,找零 钱问题所用的贪心准则是选取面值最大的硬币。对于一个给定的问 题,初看起来,往往有若干中贪心准则可选,但在实际上,其中的多 数都不能使贪心算法达到问题的最优解。如O/1背包问题下面的实例: n=3,M=20,p=(25,24,15),w(18,15,10) 如果以价值最大为贪心准则,则贪心算法的执行过程是:首先考虑将 物品1装包,此时获得效益值25,包的剩余容量是2。然后考虑将物 品2装包,但物品2的重量15超出包的剩余容量,只能装入该种物 品的2/15,此时获得的总效益值为25+24×2/15=282。这样得到的可 行解(1,2/15,0)并不是最优解。事实上,如果以单位价值最大为 贪心准则,则贪心算法的执行过程是:先计算出各个物品的单位价值
数 n 有限，必到某一步停止，我们能找到解向量 y*,它和 x 有相同的 分量，又与 y 又有相同的总价值（大于 x 的总价值），矛盾。 这个矛 盾源于 x 不是最优解的假设。故，x 是最优解。 贪心算法主要用于处理优化问题。每个优化问题都是由目标函数 和约束条件组成。满足约束条件的解称为可行解，而那些使得目标函 数取极值的可行解称为最优解。如 0/1 背包问题是一个优化问题，式 (5.3)中的函数是目标函数，而(5.4)式描述的要求是约束条件，这里优 化是使目标函数取最大值。贪心算法在每一步的决策中虽然没有完全 顾忌到问题整体优化，但在局部择优中是朝着整体优化的方向发展 的。为此，贪心算法首先要确定一个度量准则，每一步都是按这个准 则选取优化方案。如 0/1 背包问题的贪心准则是选取单位价值 p/w 最 大物品，而装载问题的贪心算法选取的准则是选取最轻的货箱，找零 钱问题所用的贪心准则是选取面值最大的硬币。对于一个给定的问 题，初看起来，往往有若干中贪心准则可选，但在实际上，其中的多 数都不能使贪心算法达到问题的最优解。如 0/1 背包问题下面的实例： n=3, M=20, p=(25, 24, 15), w=(18,15,10) 如果以价值最大为贪心准则，则贪心算法的执行过程是：首先考虑将 物品 1 装包，此时获得效益值 25，包的剩余容量是 2。然后考虑将物 品 2 装包，但物品 2 的重量 15 超出包的剩余容量，只能装入该种物 品的 2/15，此时获得的总效益值为 25+24×2/15=28.2。这样得到的可 行解（1，2/15，0）并不是最优解。事实上，如果以单位价值最大为 贪心准则，则贪心算法的执行过程是：先计算出各个物品的单位价值
(25/18,24/15,15/10=(1.389,16,1.5)。首先考虑单位价值大的物品装 包,即将物品2装包,此时获得效益值24,背包的剩余容量是5。然 后考虑装物品3,由于物品3的重量超出背包的剩余容量,只能装入 该物品5/15=1/2,至此背包已经装满,所得的总的效益值为 24+15/2=315。比前面的装法的效益值大。实践证明,选择能产生最 优解的贪心准则是设计贪心算法的核心问题。以下给出贪心算法流程 的伪代码。 贪心算法抽象化控制流程 Greedy(A,n)∥A[1n]代表那个输入 solution={};∥解向量初始化为空集 fori from l to n do xSelect(A); if Feasible(solution, x)then solution=Union(solution, x); endif endfor return( solution) end greedy 这里 Selecte(A)是按照谈心准则选取A种的输入项; Feasible( solution, x)是判断已知的解的部分 solution与新选取的x的结合 Union( solution, x)是否是可行解。过程〔redy描述了用贪心策略设计算法的主要工 作和基本控制流程。一旦给出一个特定的问题,就可将 Select, Feasible
(25/18, 24/15, 15/10)=(1.389, 1.6, 1.5)。首先考虑单位价值大的物品装 包，即将物品 2 装包，此时获得效益值 24，背包的剩余容量是 5。然 后考虑装物品 3，由于物品 3 的重量超出背包的剩余容量，只能装入 该物品 5/15=1/2, 至此背包已经装满，所得的总的效益值为 24+15/2=31.5。比前面的装法的效益值大。实践证明，选择能产生最 优解的贪心准则是设计贪心算法的核心问题。以下给出贪心算法流程 的伪代码。 贪心算法抽象化控制流程 Greedy(A, n) // A[1:n]代表那个输入 solution={}; //解向量初始化为空集 for i from 1 to n do x=Select(A); if Feasible(solution, x) then solution=Union(solution, x); endif endfor return(solution); end Greedy 这里 Select(A)是按照谈心准则选取 A 种的输入项； Feasible(solution, x)是判断已知的解的部分solution与新选取的x的结合Union(solution, x)是否是可行解。过程 Greedy 描述了用贪心策略设计算法的主要工 作和基本控制流程。一旦给出一个特定的问题，就可将 Select，Feasible
和 Union具体化并付诸实现。 §2作业排序问题 ●活动安排问题 我们首先从活动安排这一简单课题入手。该问题要求高效地安排 系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的 方法使得尽可能多的活动能够兼容地使用公共资源。 问题:已知n个活动E={1,2,…,n}要求使用同一资源,第k 个活动要求的开始和结束时间为s,f,其中sf或者s>f。活动安排问题就是 要在所给的活动集合中选出最大的相容活动子集。 解决这个问题的基本思路是在安排时应该将结束时间早的活动 尽量往前安排,好给后面的活动安排留出更多的空间,从而达到安排 最多活动的目标。据此,贪心准则应当是:在未安排的活动中挑选结 束时间最早的活动安排。在贪心算法中,将各项活动的开始时间和结 束时间分别用两个数组s和f存储,并使得数组中元素的顺序按结束 时间非减排列:f1≤f,≤…≤fn 活动安排贪心算法伪代码 Greedy Action(s,f,n)∥lln]、红ln]分别代表n项活动的起始 时间和结束时间,并且满足f1≤2]…≤fn l; solution={1};∥解向量初始化为空集 for i from 2 to n do
和 Union 具体化并付诸实现。 §2 作业排序问题 z 活动安排问题 我们首先从活动安排这一简单课题入手。该问题要求高效地安排 一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的 方法使得尽可能多的活动能够兼容地使用公共资源。 问题：已知 n 个活动 E={1, 2, … ,n}要求使用同一资源，第 k 个活动要求的开始和结束时间为 sk, fk, 其中 sk fj或者 sj> fk。活动安排问题就是 要在所给的活动集合中选出最大的相容活动子集。 解决这个问题的基本思路是在安排时应该将结束时间早的活动 尽量往前安排，好给后面的活动安排留出更多的空间，从而达到安排 最多活动的目标。据此，贪心准则应当是：在未安排的活动中挑选结 束时间最早的活动安排。在贪心算法中，将各项活动的开始时间和结 束时间分别用两个数组 s 和 f 存储，并使得数组中元素的顺序按结束 时间非减排列：f1≤ f2≤…≤ fn。 活动安排贪心算法伪代码 GreedyAction(s, f，n) // s[1:n]、f[1:n]分别代表 n 项活动的起始 //时间和结束时间, 并且满足 f[1]≤ f[2]≤…≤ f[n] j=1; solution={1}; //解向量初始化为空集 for i from 2 to n do
fs≥fthe solution= solution u};∥将j加入解中 endif endfor return(solution) end greedy 例子设待安排的11个活动的开始时间和结束时间按结束时间的 非减次序排列如下 k1234 67891011 s]13053568√|8212y 562891011121314 解集合为{1,4-8,11容易证明算法 Greedy Action所得到的解是最 优解。 带限期作业安排问题 将活动排序问题加上效益条件,即是下面的单机作业排序问题。 为使问题简化,我们假定完成每项作业的时间都是都是一样的,比如 都是1。 问题:已知n项作业E={1,2,…,n}要求使用同台机器完成, 而且每项作业需要的时间都是1。第k项作业要求在时间f之前完成 而且完成这项作业将获得效益pk,k=1,2,…,n。E的子集称为相 容的,如果它们可以被安排由一台机器完成(该台机器在同一时刻至
if si≥fj then solution=solution ∪ {j}; // 将 j 加入解中 j=i; endif endfor return(solution); end Greedy 例子 设待安排的 11 个活动的开始时间和结束时间按结束时间的 非减次序排列如下： k 1 2 3 4 5 6 7 8 9 10 11 s[k] 1√ 3 0 5√ 3 5 6 8√ 8 2 12√ f[k] 4 5 6 7 8 9 10 11 12 13 14 解集合为 {1,4,8,11}.容易证明算法 GreedyAction 所得到的解是最 优解。 z 带限期作业安排问题 将活动排序问题加上效益条件，即是下面的单机作业排序问题。 为使问题简化，我们假定完成每项作业的时间都是都是一样的，比如 都是 1。 问题： 已知 n 项作业 E={1, 2, … ,n}要求使用同台机器完成， 而且每项作业需要的时间都是 1。第 k 项作业要求在时间 fk之前完成, 而且完成这项作业将获得效益 pk，k=1, 2, … , n 。E 的子集称为相 容的，如果它们可以被安排由一台机器完成（该台机器在同一时刻至
多完成一个作业)。带限期作业排序问题就是要在所给的作业集合中 选出总效益值最大的相容子集。 这个问题可以看作是活动安排问题的推广,作业i的起始时间 为0≤s≤f-1.而活动安排问题中的效益值可以认为全是1。因此,很 容易想到贪心准则应该是尽量选取效益值最大的作业安排。但由于起 始时间是一个区间,可以将后面考虑的作业插到前面安排时剩余的空 闲时间片里,这是不同的地方。 带限期作业安排的贪心算法伪代码 Greedy Job(f,p,n)/ln]和p[1n]分别代表各项作业的限期和效益 ∥值,而且n项作业的排序满足:p1≥p2≥…≥p local. J={1}; for i from 2 to n do ifJu{i}中的作业是相容的then J=J∪{i};∥将i加入解中 endif endfor end Greedy Job 定理2算法 GreedyJob对于作业排序问题总是得到最优解。 证明:假设贪心算法所选择的作业的集合J不是最优解,则一定 有相容的作业子集I,其产生更大的效益值。并假定I是具有最大效 益值的相容作业子集中使得Ⅰ⌒J最大者。这两个作业集之间没有包
多完成一个作业）。带限期作业排序问题就是要在所给的作业集合中 选出总效益值最大的相容子集。 这个问题可以看作是活动安排问题的推广， 作业 i 的起始时间 为 0≤si≤fi-1. 而活动安排问题中的效益值可以认为全是 1。因此，很 容易想到贪心准则应该是尽量选取效益值最大的作业安排。但由于起 始时间是一个区间，可以将后面考虑的作业插到前面安排时剩余的空 闲时间片里，这是不同的地方。 带限期作业安排的贪心算法伪代码 GreedyJob(f, p, n) //f[1:n]和 p[1:n]分别代表各项作业的限期和效益 //值，而且 n 项作业的排序满足：p1 ≥ p2 ≥ … ≥ pn local J; J={1}; for i from 2 to n do if J ∪ {i} 中的作业是相容的 then J= J ∪ {i}; // 将 i 加入解中 endif endfor end GreedyJob 定理 2 算法 GreedyJob 对于作业排序问题总是得到最优解。 证明：假设贪心算法所选择的作业的集合 J 不是最优解，则一定 有相容的作业子集 I，其产生更大的效益值。并假定 I 是具有最大效 益值的相容作业子集中使得 I ∩ J 最大者。这两个作业集之间没有包
含关系。这是因为算法 Greedy Job的特性和假定I产生的效益值比J 的效益值更大。假设a是J中具有最大效益的作业,于是,J中比 a具有更多效益的作业都应该在I中。对于任何元素b∈IJ,我们有 pa≥pb。否则,由p^pb可推出b∈J,因为按照算法 GreedyJob,b将先 于a被考虑是否该加入J中。而J中那些效益比a效益大的作业也允 许将b加入J,因为它们在I中是相容的。 如果用S1和S分别记对应于I和J的调度表,并且i∈I∩J,i项 作业在S和S1中分别属于时间段t,t1和t,t+1]。若t<t',则在S 中将i项作业与S1在时间段[t,t+1]内排序的作业(如果有的化)交 换,这样得到的调度表S还是相容的。同样讨论tt'情形。由此,我 们可以假设I∩J中作业在S1和S中有相同的排序时间表。现在假设 排序时间表S中,作业a被安排在时间片[ta,t+中。则排序时间表 S1一定有某个作业b∈Ⅳ被安排在时间片[ta,ta+1]中。不然,在排序表 S1中,时间片[ta,t+1空闲,将作业a安排在这个时间片调度,将会 得到效益值更大的相容作业子集,这与Ⅰ的假设矛盾。现在,将S1 中的时间片[ta,t+1]换成调度作业a,则得到新的相容作业集合 I'=(Ⅳ{b}){a}。显然I的效益值不低于I的效益值,但I⌒J比I⌒J 的元素至少少一个,与前面的假设矛盾。证毕 在上述算法中,每次新的作业i填入之前,都要做一次判断,实 际上是检查在[0,1]12,……,[f1,f中是否还有空闲的时间片?若有, 则选择其中之一安排作业i;否则,作业i将被搁置。实现的方法有 两种
含关系。这是因为算法 GreedyJob 的特性和假定 I 产生的效益值比 J 的效益值更大。 假设 a 是 J\I 中具有最大效益的作业，于是，J 中比 a 具有更多效益的作业都应该在 I 中。对于任何元素 b∈I\J，我们有 pa≥pb。否则，由 pat’情形。由此，我 们可以假设 I ∩ J 中作业在 SI和 SJ中有相同的排序时间表。现在假设 排序时间表 SJ中，作业 a 被安排在时间片[ta, ta+1]中。则排序时间表 SI一定有某个作业 b∈I\J 被安排在时间片[ta, ta+1]中。不然，在排序表 SI中，时间片[ta, ta+1]空闲，将作业 a 安排在这个时间片调度，将会 得到效益值更大的相容作业子集，这与 I 的假设矛盾。现在，将 SI 中的时间片[ta, ta+1]换成调度作业 a，则得到新的相容作业集合 I’=(I\{b})∪{a}。显然 I’的效益值不低于 I 的效益值，但 I’ ∩ J 比 I ∩ J 的元素至少少一个，与前面的假设矛盾。 证毕 在上述算法中，每次新的作业 i 填入之前，都要做一次判断，实 际上是检查在[0,1],[1,2], ⋅⋅⋅⋅⋅，[fi-1,fi]中是否还有空闲的时间片？若有， 则选择其中之一安排作业 i；否则，作业 i 将被搁置。实现的方法有 两种