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

貪心法的基本思路是在對問題求解時總是做出在當前看來是最好的選擇，也就是說貪心法不從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的局部最優(yōu)解。

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

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

w(i，k)表示(i，k)的權值

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

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

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

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

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

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

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

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

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

活動3

活動4√活動5

活動6

活動7

活動8√活動9

活動10

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

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

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

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

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

首先證明總存在一個以活動1開始的最優(yōu)解。

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

那么用活動1取代活動k得到Y(jié)'，因為e1≤ek，所以Y'中的活動是兼容的，即Y'也是最優(yōu)的，這就說明總存在一個以活動1開始的最優(yōu)解。

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

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

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

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

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

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

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

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

求出一個最大兼容活動子集，將它們安排在一個蓄欄中（蓄欄編號為1）；如果沒有安排完，再在剩余的活動再求下一個最大兼容活動子集，將它們安排在另一個蓄欄中（蓄欄編號為2），以此類推。

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

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

牛2安排的蓄欄:1

牛3安排的蓄欄:2

牛5安排的蓄欄:3

牛4安排的蓄欄:1

牛1安排的蓄欄:4

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

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

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

(w1，w2，w3)=(18，15，10)，(v1，v2，v3)=(25，24，15)，W=20，其中的4個可行解如下：解編號(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個可行解中，第④個解的效益最大，可以求出它是這個背包問題的最優(yōu)解。

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

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

（3）從i=1開始，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//問題表示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}}; //下標0不用//求解結(jié)果表示doubleV; //最大價值doublex[MAXN];voidKnap() //求解背包問題并返回總價值{V=0; //V初始化為0doubleweight=W; //背包中能裝入的余下重量memset(x,0,sizeof(x)); //初始化x向量inti=1;while(A[i].w<weight) //物品i能夠全部裝入時循環(huán){x[i]=1; //裝入物品iweight-=A[i].w; //減少背包中能裝入的余下重量V+=A[i].v; //累計總價值i++; //繼續(xù)循環(huán)}if(weight>0) //當余下重量大于0{x[i]=weight/A[i].w; //將物品i的一部分裝入V+=x[i]*A[i].v; //累計總價值}}voidmain(){printf("求解過程\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("總價值=%g\n",V);}

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

，從而有

，

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

≥0這樣與Y是最優(yōu)解的假設矛盾，也就是說沒有哪個可行解的價值會大于V(X)，因此解X是最優(yōu)解。

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

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

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

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

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

對wi從小到大排序得到{w1，w2，…，wn}，設最優(yōu)解向量為x={x1，x2，…，xn}，顯然，x1=1，則x'={x2，…，xn}是裝載問題w'={w2，…，wn}，W'=W-w1的最優(yōu)解，滿足貪心最優(yōu)子結(jié)構(gòu)性質(zhì)。//問題表示intw[]={0,5,2,6,4,3}; //各集裝箱重量,不用下標0的元素intn=5,W=10;//求解結(jié)果表示intmaxw; //存放最優(yōu)解的總重量intx[MAXN]; //存放最優(yōu)解向量voidsolve() //求解最優(yōu)裝載問題{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]; //累計裝載總重量}}最優(yōu)方案

選取重量為2的集裝箱

選取重量為3的集裝箱

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

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

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

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

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

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

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

（2）田忌最快的馬比齊威王最快的馬慢即a[righta]<b[rightb]，則選擇田忌最慢的馬與齊威王最快的馬比賽，田忌輸。因為齊威王最快的馬一定贏，而選擇與田忌最慢的馬比賽對于田忌來說是最優(yōu)的?！觥酢酢酢酢酢雎靉■…□□□□□…■ba[righta]<b[rightb]：ans-=200慢快a■…□□□□■…■b■…■□□□□…■

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

①田忌最慢的馬比齊威王最慢的馬快即a[lefta]>b[leftb]，則兩者比賽（兩個最慢的馬比賽），田忌贏。因為此時齊威王最慢的馬一定輸，而選擇與田忌最慢的馬比賽對于田忌來說是最優(yōu)的。■…□□□□□…■慢快a■…□□□□□…■b■…■□□□□…■慢快a■…■□□□□…■ba[lefta]>b[leftb]：ans+=200

②田忌最慢的馬比齊威王最慢的馬慢，并且田忌最慢的馬比齊威王最快的馬慢，即a[lefta]≤b[leftb]且a[lefta]<b[rightb]，則選擇田忌最慢的馬與齊威王最快的馬比賽，田忌輸。因為此時田忌最慢的馬一定輸，而選擇與齊威王最快的馬比賽對于田忌來說是最優(yōu)的。■…□□□□□…■慢快a■…□□□□□…■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]，說明比賽區(qū)間的所以馬的速度全部相同，任何兩匹馬比賽都沒有輸贏。

上述過程看出每種情況對于田忌來說都是最優(yōu)的，因此最終獲得的比賽方案也一定是最優(yōu)的。//問題表示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); //對a遞增排序sort(b,b+n); //對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--; }}}}

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

【問題描述】設有n個獨立的作業(yè){1，2，…，n}，由m臺相同的機器{1，2，

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

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

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

（2）先將排序后的前3個作業(yè)分配給3臺機器。此時機器的分配情況為{{4}，{2}，{5}}，對應的總處理時間為{16，14，6}。機器1機器2機器3作業(yè)4:16作業(yè)2:14作業(yè)5:6作業(yè)編號4256371作業(yè)的處理時間161465432

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

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

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

【問題描述】設要編碼的字符集為{d1，

d2，…，

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

w2，…，

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

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

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

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

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

（3）重復步驟（2），當F中只剩下一棵二叉樹時，這棵二叉樹便是所要建立的哈夫曼樹。例如，給定的a～e的5個字符，它們的權值集合為W={4，2，1，7，3}，構(gòu)造哈夫曼樹的過程如下。（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

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

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

priority_queue<NodeType>qu;for(intk=0;k<2*n-1;k++) //設置所有結(jié)點的指針域ht[k].lchild=ht[k].rchild=ht[k].parent=-1;for(inti=0;i<n;i++) //將n個結(jié)點進隊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)造哈夫曼樹的n-1個非葉子結(jié)點{e1=qu.top();qu.pop(); //出隊權值最小的結(jié)點e1e2=qu.top();qu.pop(); //出隊權值次小的結(jié)點e2ht[j].weight=e1.weight+e2.weight;//構(gòu)造哈夫曼樹的非葉子結(jié)點j ht[j].lchild=e1.no;ht[j].rchild=e2.no;ht[e1.no].parent=j; //修改e1.no的雙親為結(jié)點jht[e2.no].parent=j; //修改e2.no的雙親為結(jié)點je.no=j; //構(gòu)造隊列結(jié)點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é)點i的哈夫曼編碼{code="";intcurno=i;intf=ht[curno].parent;while(f!=-1) //循環(huán)到根結(jié)點{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字符的哈夫曼編碼}}【算法證明】先討論兩個命題及其證明過程。命題1：兩個最小權值字符對應的結(jié)點x和y必須是哈夫曼樹中最深的兩個結(jié)點且它們?yōu)樾值?。證明：假設x結(jié)點在哈夫曼樹（最優(yōu)樹）中不是最深的，那么存在一個結(jié)點z，有wz>

wx，但它比x深，即lz>

lx。

此時x和z的帶權和為wx×lx+

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

交換后的帶權和為wx×lz+

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

wx×lx+wz×lz這是因為wx×lz+wz×lx-

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

-

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

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

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

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

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

且有：

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

WPL(T3)=WPL(T2)+wx

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

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

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

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

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

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

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

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

//求解算法{sort(A+1,A+n+1); //按效益遞減排序intsum=0; //初始化處理作業(yè)的時間為0for(inti=1;i<=n;i++){if(A[i].d>sum){bestp+=A[i].p; //累計處理作業(yè)的效益sum+=A[i].t; //累計處理時間}}}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)度問題

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

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

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

當有兩個作業(yè)（a1，b1）和（a2，b2）時，若（a1，b1）在前（a2，b2）在后執(zhí)行：(a)作業(yè)2在M2上執(zhí)行沒有等待的情況(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í)行，可以求出最少時間Tmin=a2+b2+a1+b1-min(b2，a1)將兩種執(zhí)行順序合并起來有：Tmin=a1+b1+a2+b2-max(min(a2，b1)，min(a1，b2))由此可以得到一個貪心的性質(zhì)：對于(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的時間分為兩組，a[i]≤b[i]對應第1組N1，a[i]>b[i]對應第0組N2。

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

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

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