第7章貪心法7.1貪心法概述7.2求解活動(dòng)安排問(wèn)題7.3求解背包問(wèn)題7.4求解最優(yōu)裝載問(wèn)題7.5求解田忌賽馬問(wèn)題7.6求解多機(jī)調(diào)度問(wèn)題7.7哈夫曼編碼7.8求解流水作業(yè)調(diào)度問(wèn)題7.1.1什么是貪心法

貪心法的基本思路是在對(duì)問(wèn)題求解時(shí)總是做出在當(dāng)前看來(lái)是最好的選擇，也就是說(shuō)貪心法不從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的局部最優(yōu)解。

人們通常希望找到整體最優(yōu)解，所以采用貪心法需要證明設(shè)計(jì)的算法確實(shí)是整體最優(yōu)解或求解了它要解決的問(wèn)題。7.1貪心法概述例如，求解一個(gè)帶權(quán)無(wú)向圖G中從頂點(diǎn)i到頂點(diǎn)j（i≠j）的最短路徑，可以分析出這樣的最短路徑一定是簡(jiǎn)單路徑，所以約束條件為：目標(biāo)函數(shù)就是要使這樣的路徑最短，即：

{(i，i1)，(i1，i2)，…，(im，j)|pathlength=w(i，i1)+w(i1，i2)+…+w(im，j)，

w(i，k)表示(i，k)的權(quán)值

}求解的路徑為{(i，i1)，(i1，i2)，…，(im，j)|(i，i1)、(i1，i2)、…、(im，j)均為圖G的邊，且ik（1≤k≤m）均不相同}ii1i2j…貪心法從問(wèn)題的某一個(gè)初始解{}出發(fā)，采用逐步構(gòu)造最優(yōu)解的方法向給定的目標(biāo)前進(jìn)，每一步?jīng)Q策產(chǎn)生n-元組解（x0，x1，…，xn-1）的一個(gè)分量。貪心法每一步上用作決策依據(jù)的選擇準(zhǔn)則被稱為最優(yōu)量度標(biāo)準(zhǔn)（或貪心準(zhǔn)則），也就是說(shuō)，在選擇解分量的過(guò)程中，添加新的解分量xk后，形成的部分解（x0，x1，…，xk)不違反可行解約束條件。每一次貪心選擇都將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題，并期望通過(guò)每次所做的局部最優(yōu)選擇產(chǎn)生出一個(gè)全局最優(yōu)解。7.1.2貪心法求解的問(wèn)題應(yīng)具有的性質(zhì)1.貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。也就是說(shuō)，貪心法僅在當(dāng)前狀態(tài)下做出最好選擇，即局部最優(yōu)選擇，然后再去求解做出這個(gè)選擇后產(chǎn)生的相應(yīng)子問(wèn)題的解。2.最優(yōu)子結(jié)構(gòu)性質(zhì)

如果一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解，則稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心法求解的關(guān)鍵特征。7.1.3貪心法的一般求解過(guò)程貪心法求解問(wèn)題的算法框架如下：SolutionTypeGreedy(STypea[],intn)//假設(shè)解向量(x0,x1,…,xn-1)類型為SolutionType，其分量為SType類型{SolutionTypex={}；

//初始時(shí)，解向量不包含任何分量for(inti=0;i<n;i++) //執(zhí)行n步操作{STypexi=Select(a); //從輸入a中選擇一個(gè)當(dāng)前最好的分量if(Feasiable(xi)) //判斷xi是否包含在當(dāng)前解中 solution=Union(x,xi); //將xi分量合并形成x}returnx; //返回生成的最優(yōu)解}7.2求解活動(dòng)安排問(wèn)題

【問(wèn)題描述】假設(shè)有一個(gè)需要使用某一資源的n個(gè)活動(dòng)所組成的集合S，S={1，…，n}。該資源任何時(shí)刻只能被一個(gè)活動(dòng)所占用，活動(dòng)i有一個(gè)開(kāi)始時(shí)間bi和結(jié)束時(shí)間ei（bi<ei），其執(zhí)行時(shí)間為ei-bi，假設(shè)最早活動(dòng)執(zhí)行時(shí)間為0。

一旦某個(gè)活動(dòng)開(kāi)始執(zhí)行，中間不能被打斷，直到其執(zhí)行完畢。若活動(dòng)i和活動(dòng)j有bi≥ej或bj≥ei，則稱這兩個(gè)活動(dòng)兼容。

設(shè)計(jì)算法求一種最優(yōu)活動(dòng)安排方案，使得所有安排的活動(dòng)個(gè)數(shù)最多。

【問(wèn)題求解】假設(shè)活動(dòng)時(shí)間的參考原點(diǎn)為0。一個(gè)活動(dòng)i（1≤i≤n）用一個(gè)區(qū)間[bi，ei)表示，當(dāng)活動(dòng)按結(jié)束時(shí)間（右端點(diǎn)）遞增排序后，兩個(gè)活動(dòng)[bi，ei)和[bj，ej)兼容（滿足bi≥ej或bj≥ei）實(shí)際上就是指它們不相交。

用數(shù)組A存放所有的活動(dòng)，A[i].b（1≤i≤n），存放活動(dòng)起始時(shí)間，A[i].e存放活動(dòng)結(jié)束時(shí)間。i1234567891011開(kāi)始時(shí)間130535688212結(jié)束時(shí)間4567891011121315例如，對(duì)于下表的n=11個(gè)活動(dòng)（已按結(jié)束時(shí)間遞增排序）A：產(chǎn)生最大兼容活動(dòng)集合的過(guò)程：活動(dòng)1√活動(dòng)2

活動(dòng)3

活動(dòng)4√活動(dòng)5

活動(dòng)6

活動(dòng)7

活動(dòng)8√活動(dòng)9

活動(dòng)10

活動(dòng)11√最大兼容活動(dòng)集合：活動(dòng)1活動(dòng)4活動(dòng)8活動(dòng)11求解結(jié)果//問(wèn)題表示structAction //活動(dòng)的類型聲明{intb; //活動(dòng)起始時(shí)間inte; //活動(dòng)結(jié)束時(shí)間booloperator<(constAction&s)const //重載<關(guān)系函數(shù){ returne<=s.e; //用于按活動(dòng)結(jié)束時(shí)間遞增排序}};intn=11;ActionA[]={{0},{1,4},{3,5},{0,6},{5,7},{3,8},{5,9},{6,10},{8,11}, {8,12},{2,13},{12,15}}; //下標(biāo)0不用//求解結(jié)果表示boolflag[MAX]; //標(biāo)記選擇的活動(dòng)intCount=0; //選取的兼容活動(dòng)個(gè)數(shù)voidsolve() //求解最大兼容活動(dòng)子集{memset(flag,0,sizeof(flag)); //初始化為falsesort(A+1,A+n+1); //A[1..n]按活動(dòng)結(jié)束時(shí)間遞增排序intpreend=0; //前一個(gè)兼容活動(dòng)的結(jié)束時(shí)間for(inti=1;i<=n;i++) //掃描所有活動(dòng){if(A[i].b>=preend) //找到一個(gè)兼容活動(dòng){flag[i]=true; //選擇A[i]活動(dòng)

preend=A[i].e; //更新preend值}}}

【算法分析】算法的主要時(shí)間花費(fèi)在排序上，排序時(shí)間為O(nlog2n)，所以整個(gè)算法的時(shí)間復(fù)雜度為O(nlog2n)。

【算法證明】通常證明一個(gè)貪心選擇得出的解是最優(yōu)解的一般的方法是，構(gòu)造一個(gè)初始最優(yōu)解，然后對(duì)該解進(jìn)行修正，使其第一步為一個(gè)貪心選擇，證明總是存在一個(gè)以貪心選擇開(kāi)始的求解方案。

對(duì)于本問(wèn)題，所有活動(dòng)按結(jié)束時(shí)間遞增排序，就是要證明：若X是活動(dòng)安排問(wèn)題A的最優(yōu)解，X=X'∪{1}，則X'是A'={i∈A：ei≥b1}的活動(dòng)安排問(wèn)題的最優(yōu)解。

首先證明總存在一個(gè)以活動(dòng)1開(kāi)始的最優(yōu)解。

如果第一個(gè)選中的活動(dòng)為k（k≠1），可以構(gòu)造另一個(gè)最優(yōu)解Y，Y中的活動(dòng)是兼容的，Y與X的活動(dòng)數(shù)相同。

那么用活動(dòng)1取代活動(dòng)k得到Y(jié)'，因?yàn)閑1≤ek，所以Y'中的活動(dòng)是兼容的，即Y'也是最優(yōu)的，這就說(shuō)明總存在一個(gè)以活動(dòng)1開(kāi)始的最優(yōu)解。

當(dāng)做出了對(duì)活動(dòng)1的貪心選擇后，原問(wèn)題就變成了在活動(dòng)2、…、n中找與活動(dòng)1兼容的那些活動(dòng)的子問(wèn)題。亦即，如果X為原問(wèn)題的一個(gè)最優(yōu)解，則X'=X-{1}也是活動(dòng)選擇問(wèn)題A'={i∈A

|bi≥e1}的一個(gè)最優(yōu)解。

反證法：如果能找到一個(gè)A'的含有比X'更多活動(dòng)的解Y'，則將活動(dòng)1加入Y'后就得到A的一個(gè)包含比X更多活動(dòng)的解Y，這就與X是最優(yōu)解的假設(shè)相矛盾。

因此，在每一次貪心選擇后，留下的是一個(gè)與原問(wèn)題具有相同形式的最優(yōu)化問(wèn)題，即最優(yōu)子結(jié)構(gòu)性質(zhì)。

【例7.2】求解蓄欄保留問(wèn)題。農(nóng)場(chǎng)有n頭牛，每頭牛會(huì)有一個(gè)特定的時(shí)間區(qū)間[b，e]在蓄欄里擠牛奶，并且一個(gè)蓄欄里任何時(shí)刻只能有一頭牛擠奶。

現(xiàn)在農(nóng)場(chǎng)主希望知道最少蓄欄能夠滿足上述要求，并給出每頭牛被安排的方案。對(duì)于多種可行方案，輸出一種即可。

解：牛的編號(hào)為1～n，每頭牛的擠奶時(shí)間相當(dāng)于一個(gè)活動(dòng)，與前面活動(dòng)安排問(wèn)題不同，這里的活動(dòng)時(shí)間是閉區(qū)間，例如[2，4]與[4，7]是交叉的，它們不是兼容活動(dòng)。

采用與求解活動(dòng)安排問(wèn)題類似的貪心思路，將所有活動(dòng)這樣排序：結(jié)束時(shí)間相同按開(kāi)始時(shí)間遞增排序，否則按結(jié)束時(shí)間遞增排序。

求出一個(gè)最大兼容活動(dòng)子集，將它們安排在一個(gè)蓄欄中（蓄欄編號(hào)為1）；如果沒(méi)有安排完，再在剩余的活動(dòng)再求下一個(gè)最大兼容活動(dòng)子集，將它們安排在另一個(gè)蓄欄中（蓄欄編號(hào)為2），以此類推。

也就是說(shuō)，最大兼容活動(dòng)子集的個(gè)數(shù)就是最少蓄欄個(gè)數(shù)。i1234567開(kāi)始時(shí)間125841211結(jié)束時(shí)間457910131513461581247913272115155410最大兼容活動(dòng)子集個(gè)數(shù)為3//問(wèn)題表示structCow //奶牛的類型聲明{intno; //牛編號(hào)intb; //起始時(shí)間inte; //結(jié)束時(shí)間booloperator<(constCow&s)const//重載<關(guān)系函數(shù){if(e==s.e) //結(jié)束時(shí)間相同按開(kāi)始時(shí)間遞增排序returnb<=s.b;else //否則按結(jié)束時(shí)間遞增排序returne<=s.e;}};intn=5;CowA[]={{0},{1,1,10},{2,2,4},{3,3,6},{4,5,8},{5,4,7}};

//下標(biāo)0不用//求解結(jié)果表示intans[MAX]; //ans[i]表示第A[i].no頭牛的蓄欄編號(hào)voidsolve() //求解最大兼容活動(dòng)子集個(gè)數(shù){sort(A+1,A+n+1); //A[1..n]按指定方式排序memset(ans,0,sizeof(ans)); //初始化為0intnum=1; //蓄欄編號(hào)for(inti=1;i<=n;i++) //i、j均為排序后的下標(biāo){if(ans[i]==0) //第i頭牛還沒(méi)有安排蓄欄{ans[i]=num; //第i頭牛安排蓄欄numintpreend=A[i].e; //前一個(gè)兼容活動(dòng)的結(jié)束時(shí)間for(intj=i+1;j<=n;j++) //查找一個(gè)最大兼容活動(dòng)子集{if(A[j].b>preend&&ans[j]==0){ans[j]=num; //將兼容活動(dòng)子集中活動(dòng)安排在num蓄欄中preend=A[j].e; //更新結(jié)束時(shí)間}}num++; //查找下一個(gè)最大兼容活動(dòng)子集,num增1}}}voidmain(){solve();printf("求解結(jié)果\n");for(inti=1;i<=n;i++)printf("牛%d安排的蓄欄:%d\n",A[i].no,ans[i]);}i12345開(kāi)始時(shí)間12354結(jié)束時(shí)間104687求解結(jié)果

牛2安排的蓄欄:1

牛3安排的蓄欄:2

牛5安排的蓄欄:3

牛4安排的蓄欄:1

牛1安排的蓄欄:4

【問(wèn)題描述】設(shè)有編號(hào)為1、2、…、n的n個(gè)物品，它們的重量分別為w1、w2、…、wn，價(jià)值分別為v1、v2、…、vn，其中wi、vi（1≤i≤n）均為正數(shù)。有一個(gè)背包可以攜帶的最大重量不超過(guò)W。求解目標(biāo)：在不超過(guò)背包負(fù)重的前提下，使背包裝入的總價(jià)值最大（即效益最大化），與0/1背包問(wèn)題的區(qū)別是，這里的每個(gè)物品可以取一部分裝入背包。7.3求解背包問(wèn)題

問(wèn)題求解：這里采用貪心法求解。設(shè)xi表示物品i裝入背包的情況，0≤xi≤1。根據(jù)問(wèn)題的要求，有如下約束條件和目標(biāo)函數(shù)：0≤xi≤1（1≤i≤n）MAX{

}于是問(wèn)題歸結(jié)為尋找一個(gè)滿足上述約束條件，并使目標(biāo)函數(shù)達(dá)到最大的解向量X={x1，x2，…，xn}。例如，n=3，

(w1，w2，w3)=(18，15，10)，(v1，v2，v3)=(25，24，15)，W=20，其中的4個(gè)可行解如下：解編號(hào)(x1，x2，x3)①(1/2，1/3，1/4)16.524.25②(1，2/15，0)2028.2③(0，2/3，1)2031④(0，1，1/2)2031.5在這4個(gè)可行解中，第④個(gè)解的效益最大，可以求出它是這個(gè)背包問(wèn)題的最優(yōu)解。

貪心策略：選擇單位重量?jī)r(jià)值最大的物品。每次從物品集合中選擇單位重量?jī)r(jià)值最大的物品，如果其重量小于背包容量，就可以把它裝入，并將背包容量減去該物品的重量，然后就面臨了一個(gè)最優(yōu)子問(wèn)題——它同樣是背包問(wèn)題，只不過(guò)背包容量減少了，物品集合減少了。因此背包問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。對(duì)于下表一個(gè)背包問(wèn)題，n=5，設(shè)背包容量W=100，其求解過(guò)程如下：i12345wi1020304050vi2030664060vi/wi2.01.52.21.01.2

（1）將單位價(jià)值即v/w遞減排序，其結(jié)果為{66/30，20/10，30/20，60/50，40/40}，物品重新按1～5編號(hào)。（2）設(shè)背包余下裝入的重量為weight=W。i12345wi3010205040vi6620306040vi/wi2.22.01.51.21.0

（3）從i=1開(kāi)始，w[1]<weight成立，表明物品1能夠裝入，將其裝入到背包中，置x[1]=1，weight=weight-w[1]=70，i增1即i=2。w[2]<weight成立，表明物品2能夠裝入，將其裝入到背包中，置x[2]=1，weight=weight-w[2]=60，i增1即i=3。w[3]<weight成立，表明物品3能夠裝入，將其裝入到背包中，置x[3]=1，weight=weight-w[3]=40，i增1即i=4。w[4]<weight不成立，且weight>0，表明只能將物品4部分裝入，裝入比例=weight/w[4]=40/50=80%，置x[4]=0.8。

算法結(jié)束，得到X={1，1，1，0.8，0}。i12345wi3010205040vi6620306040vi/wi2.22.01.51.21.0//問(wèn)題表示intn=5;doubleW=100; //限重structNodeType{doublew;doublev;doublep; //p=v/wbooloperator<(constNodeType&s)const{ returnp>s.p; //按p遞減排序}};NodeTypeA[]={{0},{10,20},{20,30},{30,66},{40,40},{50,60}}; //下標(biāo)0不用//求解結(jié)果表示doubleV; //最大價(jià)值doublex[MAXN];voidKnap() //求解背包問(wèn)題并返回總價(jià)值{V=0; //V初始化為0doubleweight=W; //背包中能裝入的余下重量memset(x,0,sizeof(x)); //初始化x向量inti=1;while(A[i].w<weight) //物品i能夠全部裝入時(shí)循環(huán){x[i]=1; //裝入物品iweight-=A[i].w; //減少背包中能裝入的余下重量V+=A[i].v; //累計(jì)總價(jià)值i++; //繼續(xù)循環(huán)}if(weight>0) //當(dāng)余下重量大于0{x[i]=weight/A[i].w; //將物品i的一部分裝入V+=x[i]*A[i].v; //累計(jì)總價(jià)值}}voidmain(){printf("求解過(guò)程\n");for(inti=1;i<=n;i++) //求v/wA[i].p=A[i].v/A[i].w;printf("(1)排序前\n");dispA();sort(A+1,A+n+1);

//A[1..n]排序printf("(2)排序后\n");dispA();

Knap();printf("(3)求解結(jié)果\n"); //輸出結(jié)果printf("x:[");for(intj=1;j<=n;j++)printf("%g,",x[j]);printf("%g]\n",x[n]);printf("總價(jià)值=%g\n",V);}

【算法證明】假設(shè)對(duì)于n個(gè)物品，按vi/wi（1≤i≤n）值遞減排序得到1、2、…、n的序列，即v1/w1≥v2/w2≥…≥vn/wn。設(shè)X={x1，x2，…，xn}是本算法找到解。如果所有的xi都等于1，這個(gè)解明顯是最優(yōu)解。否則，設(shè)minj是滿足xminj<1的最小下標(biāo)?？紤]算法的工作方式，很明顯，當(dāng)i<minj時(shí)，xi=1，當(dāng)i>minj時(shí)，xi=0，并且。設(shè)X的價(jià)值為V(X)=。設(shè)Y={y1，y2，…，yn}是該背包問(wèn)題的一個(gè)最優(yōu)可行解，因此有

，從而有

，

這個(gè)解的價(jià)值為V(Y)=。則V(X)-V(Y)=當(dāng)i<minj時(shí)，xi=1，所以xi-yi≥0，且vi/wi≥vminj/wminj。當(dāng)i>minj時(shí)，xi=0，所以xi-yi≤0，且vi/wi≤vminj/wminj。當(dāng)i=minj時(shí)，vi/wi=vminj/wminj。則V(X)-V(Y)=≥=

≥0這樣與Y是最優(yōu)解的假設(shè)矛盾，也就是說(shuō)沒(méi)有哪個(gè)可行解的價(jià)值會(huì)大于V(X)，因此解X是最優(yōu)解。

【算法分析】排序的時(shí)間復(fù)雜性為O(nlog2n)，while循環(huán)的時(shí)間為O(n)，所以本算法的時(shí)間復(fù)雜度為O(nlog2n)。7.4求解最優(yōu)裝載問(wèn)題

【問(wèn)題描述】有n個(gè)集裝箱要裝上一艘載重量為W的輪船，其中集裝箱i（1≤i≤n）的重量為wi。

不考慮集裝箱的體積限制，現(xiàn)要選出盡可能多的集裝箱裝上輪船，使它們的重量之和不超過(guò)W。

【問(wèn)題求解】第5章討論了簡(jiǎn)單裝載問(wèn)題，采用回溯法選出盡可能少的集裝箱個(gè)數(shù)。這里的最優(yōu)解是選出盡可能多的集裝箱個(gè)數(shù)，并采用貪心法求解。

當(dāng)重量限制為W時(shí)，wi越小可裝載的集裝箱個(gè)數(shù)越多，所以采用優(yōu)先選取重量輕的集裝箱裝船的貪心思路。

對(duì)wi從小到大排序得到{w1，w2，…，wn}，設(shè)最優(yōu)解向量為x={x1，x2，…，xn}，顯然，x1=1，則x'={x2，…，xn}是裝載問(wèn)題w'={w2，…，wn}，W'=W-w1的最優(yōu)解，滿足貪心最優(yōu)子結(jié)構(gòu)性質(zhì)。//問(wèn)題表示intw[]={0,5,2,6,4,3}; //各集裝箱重量,不用下標(biāo)0的元素intn=5,W=10;//求解結(jié)果表示intmaxw; //存放最優(yōu)解的總重量intx[MAXN]; //存放最優(yōu)解向量voidsolve() //求解最優(yōu)裝載問(wèn)題{memset(x,0,sizeof(x)); //初始化解向量sort(w+1,w+n+1); //w[1..n]遞增排序maxw=0;intrestw=W; //剩余重量for(inti=1;i<=n&&w[i]<=restw;i++){x[i]=1; //選擇集裝箱irestw-=w[i]; //減少剩余重量maxw+=w[i]; //累計(jì)裝載總重量}}最優(yōu)方案

選取重量為2的集裝箱

選取重量為3的集裝箱

選取重量為4的集裝箱總重量=9intw[]={0,5,2,6,4,3}; //各集裝箱重量,不用下標(biāo)0的元素intn=5,W=10;

【算法分析】算法的主要時(shí)間花費(fèi)在排序上，時(shí)間復(fù)雜度為O(nlog2n)。7.5求解田忌賽馬問(wèn)題

【問(wèn)題描述】二千多年前的戰(zhàn)國(guó)時(shí)期，齊威王與大將田忌賽馬。雙方約定每人各出300匹馬，并且在上、中、下三個(gè)等級(jí)中各選一匹進(jìn)行比賽，由于齊威王每個(gè)等級(jí)的馬都比田忌的馬略強(qiáng)，比賽的結(jié)果可想而知?，F(xiàn)在雙方各n匹馬，依次派出一匹馬進(jìn)行比賽，每一輪獲勝的一方將從輸?shù)囊环降玫?00銀幣，平局則不用出錢，田忌已知所有馬的速度值并可以安排出場(chǎng)順序，問(wèn)他如何安排比賽獲得的銀幣最多。

輸入：輸入包含多個(gè)測(cè)試用例，每個(gè)測(cè)試用例的第一行正整數(shù)n（n≤1000）馬的數(shù)量，后兩行分別是n個(gè)整數(shù)，表示田忌和齊威王的馬的速度值。輸入n=0結(jié)束。

輸出：每個(gè)測(cè)試用例輸出一行，表示田忌獲得的最多銀幣數(shù)。輸入樣例：39283719587742202020202201922180樣例輸出：20000

【問(wèn)題求解】田忌的馬速度用數(shù)組a表示，齊威王的馬速度用數(shù)組b表示，將a、b數(shù)組遞增排序。采用常識(shí)性的貪心思路，分以下幾種情況：

（1）田忌最快的馬比齊威王最快的馬快即a[righta]>b[rightb]，則兩者比賽（兩個(gè)最快的馬比賽），田忌贏。因?yàn)榇藭r(shí)田忌最快的馬一定贏，而選擇與齊威王最快的馬比賽對(duì)于田忌來(lái)說(shuō)是最優(yōu)的，下圖中“■”代表已經(jīng)比賽的馬，“□”代表尚未比賽的馬，箭頭指向的馬速度更快。■…□□□□□…■慢快a■…□□□□□…■ba[righta]>b[rightb]：ans+=200■…□□□□■…■慢快a■…□□□□■…■b

（2）田忌最快的馬比齊威王最快的馬慢即a[righta]<b[rightb]，則選擇田忌最慢的馬與齊威王最快的馬比賽，田忌輸。因?yàn)辇R威王最快的馬一定贏，而選擇與田忌最慢的馬比賽對(duì)于田忌來(lái)說(shuō)是最優(yōu)的。■…□□□□□…■慢快a■…□□□□□…■ba[righta]<b[rightb]：ans-=200慢快a■…□□□□■…■b■…■□□□□…■

（3）田忌最快的馬與齊威王最快的馬的速度相同即a[righta]=b[rightb]，又分為以下3種情況：

①田忌最慢的馬比齊威王最慢的馬快即a[lefta]>b[leftb]，則兩者比賽（兩個(gè)最慢的馬比賽），田忌贏。因?yàn)榇藭r(shí)齊威王最慢的馬一定輸，而選擇與田忌最慢的馬比賽對(duì)于田忌來(lái)說(shuō)是最優(yōu)的?！觥酢酢酢酢酢雎靉■…□□□□□…■b■…■□□□□…■慢快a■…■□□□□…■ba[lefta]>b[leftb]：ans+=200

②田忌最慢的馬比齊威王最慢的馬慢，并且田忌最慢的馬比齊威王最快的馬慢，即a[lefta]≤b[leftb]且a[lefta]<b[rightb]，則選擇田忌最慢的馬與齊威王最快的馬比賽，田忌輸。因?yàn)榇藭r(shí)田忌最慢的馬一定輸，而選擇與齊威王最快的馬比賽對(duì)于田忌來(lái)說(shuō)是最優(yōu)的?！觥酢酢酢酢酢雎靉■…□□□□□…■ba[lefta]≥b[leftb]且a[lefta]<b[rightb]：ans-=200■…■□□□□…■慢快a■…□□□□■…■b

③其他情況，即a[righta]=b[rightb]且a[lefta]≤b[leftb]且a[lefta]≥b[rightb]，則a[lefta]≥b[rightb]=a[righta]，即a[lefta]=a[righta]，b[leftb]≥a[lefta]=b[rightb]，即b[leftb]=b[rightb]，說(shuō)明比賽區(qū)間的所以馬的速度全部相同，任何兩匹馬比賽都沒(méi)有輸贏。

上述過(guò)程看出每種情況對(duì)于田忌來(lái)說(shuō)都是最優(yōu)的，因此最終獲得的比賽方案也一定是最優(yōu)的。//問(wèn)題表示intn;inta[MAX];intb[MAX];//求解結(jié)果表示intans; intmain(){while(true){ scanf("%d",&n); if(n==0)break; for(inti=0;i<n;i++) scanf("%d",&a[i]); for(intj=0;j<n;j++) scanf("%d",&b[j]);

solve(); printf("%d\n",ans);}return0;}voidsolve() //求解算法{sort(a,a+n); //對(duì)a遞增排序sort(b,b+n); //對(duì)b遞增排序ans=0;intlefta=0,leftb=0;intrighta=n-1,rightb=n-1;while(lefta<=righta) //比賽直到結(jié)束{if(a[righta]>b[rightb])

//田忌最快的馬比齊威王最快的馬快，兩者比賽{ans+=200;righta--;rightb--;}elseif(a[righta]<b[rightb])

//田忌最快的馬比齊威王最快的馬慢{ans-=200;

//選擇田忌最慢的馬與比齊威王最快的馬比賽lefta++;rightb--;}else //田忌最快的馬與齊威王最快的馬的速度相同{if(a[lefta]>b[leftb])

//田忌最慢的馬比齊威王最慢的馬快，兩者比賽{ans+=200;lefta++;leftb++;}else{if(a[lefta]<b[rightb])

//否則，用田忌最慢的馬與齊威王最快的馬比賽ans-=200;lefta++;rightb--; }}}}

【算法分析】算法的主要時(shí)間花費(fèi)在排序上，時(shí)間復(fù)雜度為O(nlog2n)。

【問(wèn)題描述】設(shè)有n個(gè)獨(dú)立的作業(yè){1，2，…，n}，由m臺(tái)相同的機(jī)器{1，2，

…，m}進(jìn)行加工處理，作業(yè)i所需的處理時(shí)間為ti（1≤i≤n），每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷，任何作業(yè)也不能拆分成更小的子作業(yè)。多機(jī)調(diào)度問(wèn)題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。7.6求解多機(jī)調(diào)度問(wèn)題

【問(wèn)題求解】貪心法求解多機(jī)調(diào)度問(wèn)題的貪心策略是最長(zhǎng)處理時(shí)間作業(yè)優(yōu)先，即把處理時(shí)間最長(zhǎng)的作業(yè)分配給最先空閑的機(jī)器，這樣可以保證處理時(shí)間長(zhǎng)的作業(yè)優(yōu)先處理，從而在整體上獲得盡可能短的處理時(shí)間。按照最長(zhǎng)處理時(shí)間作業(yè)優(yōu)先的貪心策略，當(dāng)m≥n時(shí)，只要將機(jī)器i的[0，ti)時(shí)間區(qū)間分配給作業(yè)i即可；當(dāng)m<n時(shí)，首先將n個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序，然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機(jī)。

例如，有7個(gè)獨(dú)立的作業(yè){1，2，3，4，5，6，7}，由3臺(tái)機(jī)器{1，2，3}加工處理，各作業(yè)所需的處理時(shí)間如下：作業(yè)編號(hào)1234567作業(yè)的處理時(shí)間214416653采用貪心法求解的過(guò)程如下：（1）7個(gè)作業(yè)按處理時(shí)間遞減排序，其結(jié)果如下表所示。作業(yè)編號(hào)4256371作業(yè)的處理時(shí)間161465432作業(yè)編號(hào)4256371作業(yè)的處理時(shí)間161465432

（2）先將排序后的前3個(gè)作業(yè)分配給3臺(tái)機(jī)器。此時(shí)機(jī)器的分配情況為{{4}，{2}，{5}}，對(duì)應(yīng)的總處理時(shí)間為{16，14，6}。機(jī)器1機(jī)器2機(jī)器3作業(yè)4:16作業(yè)2:14作業(yè)5:6作業(yè)編號(hào)4256371作業(yè)的處理時(shí)間161465432

（3）分配余下的作業(yè)：機(jī)器1機(jī)器2機(jī)器3作業(yè)4，總時(shí)間16作業(yè)2，總時(shí)間14作業(yè)5，總時(shí)間6作業(yè)5、6，總時(shí)間11作業(yè)5、6、3，總時(shí)間15作業(yè)2、7，總時(shí)間17作業(yè)5、6、3、1，總時(shí)間17作業(yè)調(diào)度方案//問(wèn)題表示intn=7;intm=3;structNodeType

//優(yōu)先隊(duì)列結(jié)點(diǎn)類型{intno; //作業(yè)序號(hào)intt; //執(zhí)行時(shí)間intmno; //機(jī)器序號(hào)booloperator<(constNodeType&s)const{returnt>s.t;} //按t越小越優(yōu)先出隊(duì)};structNodeTypeA[]={{1,2},{2,14},{3,4},{4,16},{5,6},{6,5},{7,3}};voidsolve() //求解多機(jī)調(diào)度問(wèn)題{NodeTypee;if(n<=m){printf("為每一個(gè)作業(yè)分配一臺(tái)機(jī)器\n");return;}sort(A,A+n); //按t遞減排序priority_queue<NodeType>qu; //小根堆for(inti=0;i<m;i++) //先分配m個(gè)作業(yè)，每臺(tái)機(jī)器一個(gè)作業(yè){A[i].mno=i+1; //作業(yè)對(duì)應(yīng)的機(jī)器編號(hào)printf("給機(jī)器%d分配作業(yè)%d,執(zhí)行時(shí)間為%2d,占用時(shí)間段:[%d,%d]\n", A[i].mno,A[i].no,A[i].t,0,A[i].t);qu.push(A[i]);}for(intj=m;j<n;j++) //分配余下作業(yè){e=qu.top();qu.pop(); //出隊(duì)eprintf("給機(jī)器%d分配作業(yè)%d,執(zhí)行時(shí)間為%2d,占用時(shí)間段:[%d,%d]\n", e.mno,A[j].no,A[j].t,e.t,e.t+A[j].t);e.t+=A[j].t;qu.push(e); //e進(jìn)隊(duì)}}

【算法分析】排序的時(shí)間復(fù)雜度為O(nlog2n)，兩次for循環(huán)的時(shí)間合起來(lái)為O(n)，所以本算法的時(shí)間復(fù)雜度為O(nlog2n)。

【問(wèn)題描述】設(shè)要編碼的字符集為{d1，

d2，…，

dn}，它們出現(xiàn)的頻率為{w1，

w2，…，

wn}，應(yīng)用哈夫曼樹(shù)構(gòu)造最優(yōu)的不等長(zhǎng)的由0、1構(gòu)成的編碼方案。7.7哈夫曼編碼

【問(wèn)題求解】先構(gòu)建以這個(gè)n個(gè)結(jié)點(diǎn)為葉子結(jié)點(diǎn)的哈夫曼樹(shù)，然后由哈夫曼樹(shù)產(chǎn)生各葉子結(jié)點(diǎn)對(duì)應(yīng)字符的哈夫曼編碼。

哈夫曼樹(shù)（HuffmanTree）的定義：設(shè)二叉樹(shù)具有n個(gè)帶權(quán)值的葉子結(jié)點(diǎn)，從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)都有一個(gè)路徑長(zhǎng)度。從根結(jié)點(diǎn)到各個(gè)葉子結(jié)點(diǎn)的路徑長(zhǎng)度與相應(yīng)結(jié)點(diǎn)權(quán)值的乘積的和稱為該二叉樹(shù)的帶權(quán)路徑長(zhǎng)度，記作：由n個(gè)葉子結(jié)點(diǎn)可以構(gòu)造出多種二叉樹(shù)，其中具有最小帶權(quán)路徑長(zhǎng)度的二叉樹(shù)稱為哈夫曼樹(shù)（也稱最優(yōu)樹(shù)）。構(gòu)造一棵哈夫曼樹(shù)的方法如下：

（1）由給定的n個(gè)權(quán)值{w1，w2，…，wn}構(gòu)造n棵只有一個(gè)葉子結(jié)點(diǎn)的二叉樹(shù)，從而得到一個(gè)二叉樹(shù)的集合F={T1，T2，…，Tn}。

（2）在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹(shù)作為左、右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，這棵新的二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為其左、右子樹(shù)根結(jié)點(diǎn)權(quán)值之和。即合并兩棵二叉樹(shù)為一棵二叉樹(shù)。

（3）重復(fù)步驟（2），當(dāng)F中只剩下一棵二叉樹(shù)時(shí)，這棵二叉樹(shù)便是所要建立的哈夫曼樹(shù)。例如，給定的a～e的5個(gè)字符，它們的權(quán)值集合為W={4，2，1，7，3}，構(gòu)造哈夫曼樹(shù)的過(guò)程如下。（1）{4，2，1，7，3}

{4，3，7，3}（2）{4，3，7，3}

{4，6，7}（3）{4，6，7}

{10，7}（4）{10，7}

{17}2133641017701010101b(2)：0000 c(1)：0001e(3)：001 a(4)：01d(7)：1WPL=(2+1)*4+3*3+4*2+7*1=36intn;structHTreeNode

//哈夫曼樹(shù)結(jié)點(diǎn)類型{chardata; //字符intweight; //權(quán)值intparent; //雙親的位置intlchild; //左孩子的位置intrchild; //右孩子的位置};HTreeNodeht[MAX]; //存放哈夫曼樹(shù)map<char,string>htcode; //存放哈夫曼編碼structNodeType

//優(yōu)先隊(duì)列結(jié)點(diǎn)類型{intno; //對(duì)應(yīng)哈夫曼樹(shù)ht中的位置chardata; //字符intweight; //權(quán)值booloperator<(constNodeType&s)const{ //用于創(chuàng)建小根堆 returns.weight<weight;}};voidCreateHTree() //構(gòu)造哈夫曼樹(shù){NodeTypee,e1,e2;

priority_queue<NodeType>qu;for(intk=0;k<2*n-1;k++) //設(shè)置所有結(jié)點(diǎn)的指針域ht[k].lchild=ht[k].rchild=ht[k].parent=-1;for(inti=0;i<n;i++) //將n個(gè)結(jié)點(diǎn)進(jìn)隊(duì)qu{e.no=i;e.data=ht[i].data;e.weight=ht[i].weight;qu.push(e);}

for(intj=n;j<2*n-1;j++) //構(gòu)造哈夫曼樹(shù)的n-1個(gè)非葉子結(jié)點(diǎn){e1=qu.top();qu.pop(); //出隊(duì)權(quán)值最小的結(jié)點(diǎn)e1e2=qu.top();qu.pop(); //出隊(duì)權(quán)值次小的結(jié)點(diǎn)e2ht[j].weight=e1.weight+e2.weight;//構(gòu)造哈夫曼樹(shù)的非葉子結(jié)點(diǎn)j ht[j].lchild=e1.no;ht[j].rchild=e2.no;ht[e1.no].parent=j; //修改e1.no的雙親為結(jié)點(diǎn)jht[e2.no].parent=j; //修改e2.no的雙親為結(jié)點(diǎn)je.no=j; //構(gòu)造隊(duì)列結(jié)點(diǎn)ee.weight=e1.weight+e2.weight;qu.push(e);}}voidCreateHCode() //構(gòu)造哈夫曼編碼{stringcode;code.reserve(MAX);for(inti=0;i<n;i++) //構(gòu)造葉子結(jié)點(diǎn)i的哈夫曼編碼{code="";intcurno=i;intf=ht[curno].parent;while(f!=-1) //循環(huán)到根結(jié)點(diǎn){if(ht[f].lchild==curno)//curno為雙親f的左孩子code='0'+code;else //curno為雙親f的右孩子code='1'+code;curno=f;f=ht[curno].parent;}htcode[ht[i].data]=code;//得到ht[i].data字符的哈夫曼編碼}}【算法證明】先討論兩個(gè)命題及其證明過(guò)程。命題1：兩個(gè)最小權(quán)值字符對(duì)應(yīng)的結(jié)點(diǎn)x和y必須是哈夫曼樹(shù)中最深的兩個(gè)結(jié)點(diǎn)且它們?yōu)樾值?。證明：假設(shè)x結(jié)點(diǎn)在哈夫曼樹(shù)（最優(yōu)樹(shù)）中不是最深的，那么存在一個(gè)結(jié)點(diǎn)z，有wz>

wx，但它比x深，即lz>

lx。

此時(shí)x和z的帶權(quán)和為wx×lx+

wz×lz。zxy如果交換x和z結(jié)點(diǎn)的位置，其他不變

交換后的帶權(quán)和為wx×lz+

wz×lx。有：wx×lz+wz×lx<

wx×lx+wz×lz這是因?yàn)閣x×lz+wz×lx-

(wx×lx+wz×lz)=wx(lz-lx)

-

wz(lz-lx)=(wx-wz)(lz-lx)<0（由前面所設(shè)有wz>wx和lz>lx）。這就與交換前的樹(shù)是最優(yōu)樹(shù)的假設(shè)矛盾。所以上述命題成立。zxyxzy

命題2：設(shè)T是字符集C對(duì)應(yīng)的一棵哈夫曼樹(shù)，結(jié)點(diǎn)x和y是兄弟，它們的雙親為z，顯然有wz

=wx+wy，現(xiàn)刪除結(jié)點(diǎn)x和y，讓z變?yōu)槿~子結(jié)點(diǎn)，那么這棵新樹(shù)T1一定是字符集C1=C-{x，y}∪{z}的最優(yōu)樹(shù)。zxy由T刪除x、y結(jié)點(diǎn)得到T1TzT1

證明：設(shè)T和T1的帶權(quán)路徑長(zhǎng)度分別為WPL(T)和WPL(T1)，則有：WPL(T)=WPL(T1)+wx+wy這是因?yàn)閃PL(T1)含有T中除x、y外的所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度和，另加上z的帶權(quán)路徑長(zhǎng)度。zxy由T刪除x、y結(jié)點(diǎn)得到T1TzT1假設(shè)T1不是最優(yōu)的，則存在另一棵樹(shù)T2，有：

WPL(T2)<WPL(T1)由于z∈C1，則z在T2中一定是一個(gè)葉子結(jié)點(diǎn)。若將x和y加入T2中作為結(jié)點(diǎn)z的左、右孩子，則得到表示字符集C的前綴樹(shù)T3

且有：

WPL(T3)=WPL(T2)+wx+wy由前面幾個(gè)式子看到

WPL(T3)=WPL(T2)+wx

+wy<WPL(T1)+wx+wy=WPL(T)這與T為C的哈夫曼樹(shù)的假設(shè)矛盾。本命題即證。zxyT3zT2

命題1說(shuō)明該算法滿足貪心選擇性質(zhì)，即通過(guò)合并來(lái)構(gòu)造一棵哈夫曼樹(shù)的過(guò)程可以從合并兩個(gè)權(quán)值最小的字符開(kāi)始。

命題2說(shuō)明該算法滿足最優(yōu)子結(jié)構(gòu)性質(zhì)，即該問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解。所以采用哈夫曼樹(shù)算法產(chǎn)生的樹(shù)一定是一棵最優(yōu)樹(shù)。

【算法分析】上述算法采用了小根堆，因?yàn)閺亩阎袆h除兩個(gè)結(jié)點(diǎn)（權(quán)值最小的兩個(gè)二叉樹(shù)根結(jié)點(diǎn)）和加入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度是O(log2n)，這樣修改后構(gòu)造哈夫曼樹(shù)算法的時(shí)間復(fù)雜度為O(nlog2n)。算法導(dǎo)論p239帶懲罰的任務(wù)調(diào)度算法單處理器上帶截止時(shí)間和懲罰的單位時(shí)間任務(wù)調(diào)度問(wèn)題有以下輸入：（1）n個(gè)單位時(shí)間任務(wù)的集合S={a1,a2,……,an}；（2）n個(gè)整數(shù)截止時(shí)間d1,d2,……,dn，每個(gè)di滿足1<=di<=n，期望任務(wù)ai在時(shí)間di之前完成。（3）n個(gè)非負(fù)權(quán)重或者懲罰w1,w2,……,wn，若任務(wù)ai在時(shí)間di之前沒(méi)有完成，就會(huì)受到wi這么多的懲罰，如果任務(wù)在截止時(shí)間之前完成，則不會(huì)受到懲罰。貪心選擇方法：懲罰越大越優(yōu)先執(zhí)行！i1234567di4243146wi70605040302010用sum累計(jì)做過(guò)作業(yè)的時(shí)間（初始化為0）i1234567前sumdi4243146wi70605040302010flag后sum0112√3334523334√√XX√√di>sum可以做di≤sum不能做懲罰=40+30=70voidsolve()

//求解問(wèn)題{memset(flag,0,sizeof(flag)); //flag數(shù)組初始化sort(A,A+n); //按逾期懲罰分遞減排序intsum=0; //累計(jì)做過(guò)作業(yè)的時(shí)間for(inti=0;i<n;i++){ if(A[i].d>sum) {flag[i]=true; //選擇做A[i]作業(yè)

sum++; //時(shí)間加1 }}}Hulu2013北京地區(qū)校招筆試題hulu（“葫蘆”和“互錄）是一家美國(guó)的視頻網(wǎng)站。該網(wǎng)站由美國(guó)國(guó)家廣播環(huán)球公司(NBCUniversal)和?？怂乖?007年3月共同注冊(cè)成立。

該網(wǎng)站在洛杉磯、紐約、北京均設(shè)有辦事處。

并于2007年十月獲得了私人股權(quán)投資公司普羅維登斯股本合伙人一億美元的風(fēng)險(xiǎn)投資基金。2011年7月19日微軟放棄競(jìng)購(gòu)Hulu，雅虎以20億美元?jiǎng)俪?。填空題：1、中序遍歷二叉樹(shù)，結(jié)果為ABCDEFGH，后序遍歷結(jié)果為ABEDCHGF，先序遍歷結(jié)果為（）。2、對(duì)字符串HELL0_HULU中的字符進(jìn)行二進(jìn)制編碼，使得字符串的編碼長(zhǎng)度盡可能短，最短長(zhǎng)度為（）。3、對(duì)長(zhǎng)度12的有序數(shù)組進(jìn)行二分查找，目標(biāo)等概率出現(xiàn)在數(shù)組的每個(gè)位置上，則平均比較次數(shù)為（）。4、一副撲克（去王），每個(gè)人隨機(jī)的摸兩張，則至少需要（）人摸牌，才能保證有兩個(gè)人抽到同樣的花色。令A(yù)、B、C、D依次代表?yè)淇伺浦械乃姆N花色，隨機(jī)抽取的兩張牌的花色組合有10種，根據(jù)抽屜原理，則至少11個(gè)人抽時(shí)，才能保證有兩個(gè)人抽到同樣的花色。5、x個(gè)小球中有唯一一個(gè)球較輕，用天平秤最少稱量y次能找出這個(gè)較輕的球，寫出y和x的函數(shù)表達(dá)式y(tǒng)=f(x)。（）……（共11題）大題：1、n個(gè)數(shù)，找出其中最小的k個(gè)數(shù)，寫出代碼，要求最壞情況下的時(shí)間復(fù)雜度不能高于O(nlog2k)。2、寫程序輸出8皇后問(wèn)題的所有排列，要求使用非遞歸的深度優(yōu)先遍歷。3、有n個(gè)作業(yè)，a1,a2，…，an，作業(yè)aj的處理時(shí)間為tj，產(chǎn)生的效益為pj，最后完成期限為dj，作業(yè)一旦被調(diào)度則不能中斷，如果作業(yè)aj在dj前完成，則獲得效益pj，否則無(wú)效益。給出最大化效益的作業(yè)調(diào)度算法。#include<stdio.h>#include<algorithm>usingnamespacestd;#defineMAXN51intn=3;intt[]={0,1,4,1}; //下標(biāo)0不用intd[]={0,5,4,5};intp[]={0,2,8,6};structAction{intt; //處理時(shí)間intd; //完成期限intp; //效益booloperator<(constActiont)const{ returnp>t.p; //按效益遞減排序}};ActionA[MAXN]; //求解結(jié)果表示intbestp=0; //最大的效益voidsolve()

//求解算法{sort(A+1,A+n+1); //按效益遞減排序intsum=0; //初始化處理作業(yè)的時(shí)間為0for(inti=1;i<=n;i++){if(A[i].d>sum){bestp+=A[i].p; //累計(jì)處理作業(yè)的效益sum+=A[i].t; //累計(jì)處理時(shí)間}}}voidmain(){for(inti=1;i<=n;i++) //產(chǎn)生A數(shù)組元素{ A[i].t=t[i]; A[i].d=d[i]; A[i].p=p[i];}

solve();printf("%d\n",bestp); //輸出14}7.8求解流水作業(yè)調(diào)度問(wèn)題

【問(wèn)題描述】有n個(gè)作業(yè)（編號(hào)為1～n）要在由兩臺(tái)機(jī)器M1和M2組成的流水線上完成加工。每個(gè)作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時(shí)間分別為ai和bi（1≤i≤n）。

流水作業(yè)調(diào)度問(wèn)題要求確定這n個(gè)作業(yè)的最優(yōu)加工順序，使得從第一個(gè)作業(yè)在機(jī)器M1上開(kāi)始加工，到最后一個(gè)作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少?？梢约俣ㄈ魏巫鳂I(yè)一旦開(kāi)始加工，就不允許被中斷，直到該作業(yè)被完成，即非優(yōu)先調(diào)度。

【問(wèn)題求解】采用歸納思路。當(dāng)只有一個(gè)作業(yè)（a1，b1），顯然最少時(shí)間Tmin=a1+b1。

當(dāng)有兩個(gè)作業(yè)（a1，b1）和（a2，b2）時(shí)，若（a1，b1）在前（a2，b2）在后執(zhí)行：(a)作業(yè)2在M2上執(zhí)行沒(méi)有等待的情況(b)作業(yè)2在M2上執(zhí)行有等待的情況Tmin=a1+b1+a2+b2-b1（b1<a2）Tmin=a1+b1+a2+b2-a2（a2<b1）Tmin=a1+b1+a2+b2-min(a2，b1)。若(a2，b2)在前（a1，b1）在后執(zhí)行，可以求出最少時(shí)間Tmin=a2+b2+a1+b1-min(b2，a1)將兩種執(zhí)行順序合并起來(lái)有：Tmin=a1+b1+a2+b2-max(min(a2，b1)，min(a1，b2))由此可以得到一個(gè)貪心的性質(zhì)：對(duì)于(a1，b1)和(a2，b2)中的元素若min(a1，b2)≤min(a2，b1)，則(a1，b1)放在(a2，b2)前面；反之，若min(a2，b1)≥min(a1，b2)(a2，b2)放在(a1，b1)前面。讓(a,b)中a比較小的盡可能先執(zhí)行，(a,b)中b比較小的盡可能后執(zhí)行！Johnson貪心算法。其步驟如下：

（1）把所有作業(yè)按M1、M2的時(shí)間分為兩組，a[i]≤b[i]對(duì)應(yīng)第1組N1，a[i]>b[i]對(duì)應(yīng)第0組N2。

（2）將N1的作業(yè)按a[i]遞增排序，N2的作業(yè)按b[i]遞減排序。

（3）按順序先執(zhí)行N1的作業(yè)，再執(zhí)行N2的作業(yè)，得到的就是耗時(shí)最少的最優(yōu)調(diào)度方案。實(shí)際上，N2的作業(yè)也按b[i]遞增排序，從后面向前面順序執(zhí)行示例：n=4編號(hào)1234M151248M262147組號(hào)1010時(shí)間time5247

（1）把所有作業(yè)按M1、M2的時(shí)間