第4章貪心算法-2

4.1貪心算法的基本要素貪心法在作每一次選擇時，都是當(dāng)前狀態(tài)下的最好選擇，希望以此得到整個問題的最優(yōu)解。能否奏效？用貪心法求解的問題應(yīng)具備兩個特性：（1）最優(yōu)子結(jié)構(gòu)性質(zhì)問題的最優(yōu)解包含著子問題的最優(yōu)解。（2）貪心選擇性質(zhì)局部最優(yōu)解的選擇整體最優(yōu)解貪心法與動態(tài)規(guī)劃法的比較

貪心法：當(dāng)前狀態(tài)下，局部最優(yōu)選擇，然后求解作出此選擇之后的子問題。貪心選擇依賴于以往作出的選擇，但不受將來所作的選擇的影響，既不依賴于以后子問題的解。

動態(tài)規(guī)劃法：每步所做的選擇依賴于相關(guān)子問題的解，只有在解出相關(guān)子問題以后，才能作出選擇。如何證明一個問題具有貪心選擇性質(zhì)？

思路：證明每步貪心選擇問題的整體最優(yōu)解。證明步驟：1）假設(shè)問題有一個整體最優(yōu)解。2）修改這個最優(yōu)解，使其以貪心選擇開始，并且證

明修改后的解仍然為最優(yōu)解。3）運(yùn)用數(shù)學(xué)歸納法，證明：每一步貪心選擇問題的整體最優(yōu)解。因?yàn)樽鞒鲐澬倪x擇以后，根據(jù)最優(yōu)子結(jié)構(gòu)性質(zhì)，

原問題轉(zhuǎn)化為規(guī)模更小的子問題。4.2活動安排問題問題的提出n個活動的集合E={1,2,…,n},在某一時間內(nèi)要獨(dú)占使用某個資源。每個活動i使用資源的起始時間為Si，終止時間為Fi?；顒觟和活動j相容：是指[Si,Fi)與[Sj,Fj)不相交，即：Sj>=Fi或Si>=Fj要求盡可能多地安排活動。即從活動集合E中選出最大相容活動子集。思路：最早結(jié)束的活動，優(yōu)先安排。對f1,f2,…,fn從小到大排序,時間O(nlogn)算法：template<classT>voidgreedyselector(intn,Ts[],Tf[],boolA[]){A[1]=true;intj=1;//j記錄最近入選的活動

for(inti=2;i<=n;i++){if(s[i]>=f[j]){//活動i和活動j相容

A[i]=true;j=i;}elseA[i]=false;}}//時間復(fù)雜性：O(n)（不包括排序）[算法思路]將n個活動按結(jié)束時間非減序排列,依次考慮活動i,若i與已選擇的活動相容,則添加此活動到相容活動子集.設(shè)待安排的11個活動起止時間按結(jié)束時間的非減序排列最大相容活動子集(1,4,8,11),也可表示為等長n元數(shù)組:(1,0,0,1,0,0,0,1,0,0,1)思考如下具有11個活動安排的問題？1234567891011503531868122965784111012141312345678910111305356882124567891011121314is[i]f[i]Fj總是當(dāng)前活動集合中結(jié)束最晚的活動一旦Si>=Fj，則活動i和活動j相容，將活動i加入A中，i取代j成為最近加入的活動直觀上，該算法每次總是選取最早完成時間的活動，這樣就為安排其它活動留下盡可能多的時間，從而能安排更多的活動。證明上述貪心算法一定能得到最優(yōu)解：設(shè)n個活動已經(jīng)按照結(jié)束時間的非減次序排列，集合E={1,2,…,n}。首先，活動1包含在最優(yōu)解中。設(shè)A是一個最優(yōu)解，且A中活動也按Fi遞增排序，A中第一個活動為k。假如k≠1，那么構(gòu)造B=A-{k}∪{1}，由F1<=Fk，A中活動互為相容A中活動互為相容；A和B中的活動數(shù)目相同，A是最優(yōu)解B是最優(yōu)解。所以，存在一個以貪心選擇開始的最優(yōu)解。其次，活動1入選之后，問題變?yōu)閷中所有與活動1相容活動的安排子問題。若A是E的最優(yōu)解，則A’=A-{1}是E’={i∈E|Si≥f1}的最優(yōu)解，否則，若B’優(yōu)于A’，則B’∪{1}優(yōu)于A，產(chǎn)生矛盾。由數(shù)學(xué)歸納法貪心法最終能產(chǎn)生最優(yōu)解。注意：上述算法是考慮盡可能多地安排活動數(shù)目。如果從資源的擁有者角度考慮，要盡可能減少資源閑置時間，應(yīng)采取什么安排策略？貪心算法是否有效？4.3最優(yōu)裝載問題描述：將重量為w1,…,wn的集裝箱裝上載重量為C輪船，要求盡可能多地裝入。應(yīng)如何裝載？形式化描述：目標(biāo)函數(shù)極大化maxΣxi

約束條件Σwixi≤C

xi∈{0,1}1≤i≤n實(shí)際上，裝載問題是0/1背包問題的特殊簡化：

v1=v2=…=vn=1船可以分步裝載，每步裝一個貨箱，且需要考慮裝載哪一個貨箱。根據(jù)這種思想可利用如下貪心準(zhǔn)則：從剩下的貨箱中，選擇重量最小的貨箱。這種選擇次序可以保證所選的貨箱總重量最小，從而可以裝載更多的貨箱。根據(jù)這種貪心策略，首先選擇最輕的貨箱，然后選次輕的貨箱，如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個貨箱。貪心策略：重量輕的集裝箱，優(yōu)先裝載。算法說明：時間復(fù)雜性：排序O(nlogn)數(shù)組X：存放最優(yōu)解。起初，xi=0數(shù)組W：存放各個集裝箱重量。Sort(W,t,n)：t[i]存放W中第i小元素的位置例：W={15,9,7,20,8}i=12345t[i]=35214for(i=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}[例]設(shè)n=8，[w1，…w8]=[100,200,50,90,150,50,20,80]，c=400。[算法思路]將裝船過程劃為多步選擇，每步裝一個貨箱，每次從剩下的貨箱中選擇重量最輕的貨箱.如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個貨箱。所考察貨箱的次序?yàn)?7,3,6,8,4,1,5,2。貨箱7,3,6,8,4,1的總重量為390個單位且已被裝載,剩下的裝載能力為10,小于任意貨箱.所以得到解[x1,...x8]=[1,0,1,1,0,1,1,1]最優(yōu)裝載的貪心算法template<classType>voidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);//按貨箱重量排序/for(inti=1;i<=n;i++)x[i]=0;for(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}}//調(diào)整剩余空間/算法分析:

排序?yàn)橹饕惴〞r間,所以T(n)=O(nlogn)算法證明:該算法能得到最優(yōu)解.4.4Huffman編碼*Huffman編碼用于數(shù)據(jù)壓縮例：字符出現(xiàn)頻率與編碼方案

abcdef頻率4513121695定長碼000001010011100101變長碼10100011011變長碼2010110011111011100但是變長碼1的識別困難，因?yàn)椴痪哂星熬Y性質(zhì)變長碼2屬于前綴碼，即任何一個字符的編碼都不是其它字符編碼的前綴。這樣能保證譯碼迅速、唯一確定。例：001011101001011101aabe前綴碼的二叉樹表示樹葉：字符前綴碼：樹根到樹葉的路徑例：變長碼2對應(yīng)的二叉樹26100552530a:4514f:5d:16b:13c:12e:9010000111對應(yīng)前綴碼的二叉樹為完全二叉樹，即每個結(jié)點(diǎn)有兩個兒子。n個字符對應(yīng)n個葉結(jié)點(diǎn)，n-1個內(nèi)部結(jié)點(diǎn)。設(shè)字符c在文件中出現(xiàn)頻率為f(c)，其前綴碼編碼方案對應(yīng)一棵二叉樹，字符c在樹中的深度為d(c),則編碼的平均碼長為：

B(T)=Σf(c)d(c)平均碼長最小的方案為最優(yōu)前綴碼Huffman編碼是一種最優(yōu)前綴碼，可用貪心算法構(gòu)造此編碼。構(gòu)造過程：以|c|個葉結(jié)點(diǎn)開始，執(zhí)行|c|-1次“合并”運(yùn)算，最后生成T。字符c的頻率為f(c)；隊(duì)列Q以f(c)為鍵值存放二叉樹各結(jié)點(diǎn)，通過貪心選擇，將最小頻率的兩個二叉樹合并，然后將新樹（頻率為上述兩個二叉樹頻率之和）插入Q中。24template<classT>BinaryTree<int>HuffmanTree(Tf[],intn)

{//根據(jù)權(quán)f[1:n]構(gòu)造霍夫曼樹

//創(chuàng)建一個單節(jié)點(diǎn)樹的數(shù)組

Huffman<T>*W=newHuffman<T>[n+1]；

BinaryTree<int>z,zero；

for(inti=1；i<=n；i++){z.MakeTree(i,zero,zero)；

W[i].weight=f[i]；

W[i].tree=z:}

//數(shù)組變成—個最小堆

MinHeap<Huffman<T>>Q(1)；

Q.Initialize(w,n,n)；

//將堆中的樹不斷合并

Huffman<T>x,y

for(i=1;i<n;i++){Q.DeleteMin(x)；

Q.DeleteMin(y)；

z.MakeTree(0,x.tree,y.tree)；

x.weight+=y.weight；x.tree=z；

Q.Insert(x)；}Q.DeleteMin(x)；//最后的樹

Q.Deactivate()；

delete[]w；

returnx.tree；霍夫曼樹算法時間復(fù)雜度：用f(c)初始化對列Q的時間：O(n)DeleteMin、Insert需要時間：O(logn)n-1次合并需要時間：O(nlogn)、正確性證明（1）貪心選擇性質(zhì)若C是編碼字符集，f(x)和f(y)最小，則存在C的一個最優(yōu)前綴碼使x和y具有相同碼長，且僅最后一位編碼不同。證明：設(shè)T是C的一棵最優(yōu)二叉樹，將T修改成T'和T''，使得x和y在T''中是最深的葉子，且為兄弟，這樣T''與T具有相同的最優(yōu)前綴碼。xybcTbyxcT'bcxyT''F(x)<=f(b),f(y)<=f(c)前綴碼平均碼長之差:B(T)-B(T')=Σf(c)dt(c)-Σf(c)dt’(c)=f(x)dt(x)+f(b)dt(b)-f(x)dt’(x)-f(b)dt’(b)=(f(b)-f(x))(dt(b)-dt(x))>=0同理可證，B(T')-B(T'')>=0B(T'')<=B(T)T''也是最優(yōu)的(2)最優(yōu)子結(jié)構(gòu)性質(zhì)T'=T–{x,y}C'=C–{x,y}∪{z}F(z)=f(x)+f(y)B(T)=B(T')+f(x)+f(y)zxy葉帶權(quán)二叉樹:若二叉樹T的每片葉子v都對應(yīng)一個正實(shí)數(shù)w.最優(yōu)二叉樹*樹的權(quán):在葉帶權(quán)二叉樹中,若帶權(quán)為wi的葉,其通路長度為L(wi),則稱為該葉帶權(quán)二叉樹的權(quán).最優(yōu)二叉樹:在所有葉帶權(quán)為w1,w2,…,wt的二叉樹T中w(T)最小者稱之.圖論>根樹及其應(yīng)用w(T)=wi?

L(wi)123451245334521設(shè)在1000個字母的文章中各字母出現(xiàn)的頻率為:

a:83,b:14,c:28,d:38,e:131,f:29,g:20,h:53......1420282938538313134282938538313134573853831315772538313172110831311101551311552413961100134721313961552411105357833828291420101000110最佳編碼:a:10;b:1111;c:0101;d:110;e:00;f:0100;g:1110;h:0111)將權(quán)從小到大排序2)每次選取最小權(quán)合并例題貪心算法>哈夫曼編碼4.5單源最短路徑問題

有向圖G的每條邊都有一個非負(fù)的長度c[i][j]，路徑的長度即為此路徑所經(jīng)過的邊的長度之和。15432103010506010020例：具有五個頂點(diǎn)的有向圖，各邊上的數(shù)即為長度。對于給定源頂點(diǎn)v1，需找出從它到圖中其他任意頂點(diǎn)的最短路徑。E.Dijkstra的貪心算法通過分步方法求出最短路徑。每一步產(chǎn)生一個到達(dá)新的目的頂點(diǎn)的最短路徑。下一步所能達(dá)到的目的頂點(diǎn)通過如下貪心準(zhǔn)則選?。涸谶€未產(chǎn)生最短路徑的頂點(diǎn)中，選擇路徑長度最短的目的頂點(diǎn)。即按路徑長度順序產(chǎn)生最短路徑。最初產(chǎn)生從v到它自身的路徑，這條路徑?jīng)]有邊，其長度為0。在貪心算法的每一步中，產(chǎn)生下一個最短路徑。艾茲格·迪科斯徹設(shè)u是圖中某個頂點(diǎn)，將從源點(diǎn)v到u且中間只經(jīng)過S中頂點(diǎn)的路徑稱為從源點(diǎn)v到u的特殊路徑。用dist[u]來記錄從源點(diǎn)v到u的特殊路徑長度。每次從V-S中尋找dist[u]最小的u，將u從V-S中去掉，加入S中。u加入S可能導(dǎo)致dist[j]減少，(j∈V-S)，這是由于新增的路徑(v)…(u)(j)有可能比原路徑(v)…(j)短，故用dist[u]+c(u,j)取代原來的dist[j]。Svu1u2V-S用貪心選擇來擴(kuò)充集合S。起初，S中僅包含源點(diǎn)v。某頂點(diǎn)u∈S從源點(diǎn)v到u的最短路徑已知。

算法描述：

(1)用帶權(quán)的鄰接矩陣c來表示帶權(quán)有向圖,c[i][j]表示弧<vi,vj>上的權(quán)值.若<vi,vj>V,則置c[i][j]為設(shè)S為已知最短路徑的終點(diǎn)的集合,它的初始狀態(tài)為空集.

從源點(diǎn)v到圖上其余各點(diǎn)vi的當(dāng)前最短路徑長度的初值為：

dist[i]=c[v][i]viV(2)選擇vj,使得dist[j]=Min{dist[i]|viV-S}vj就是長度最短的最短路徑的終點(diǎn)。令S=S∪{j}(3)修改從v到集合V-S上任一頂點(diǎn)vk的當(dāng)前最短路徑長度:

如果dist[j]+c[j][k]<dist[k]則修改dist[K]=dist[j]+c[j][k](4)重復(fù)操作(2),(3)共n-1次.算法說明：S[i]=false，表示頂點(diǎn)i不在S集合中開始，只有S[v]=truePrev[i]存放頂點(diǎn)i的前驅(qū)結(jié)點(diǎn)，即從源點(diǎn)到頂點(diǎn)i的最短路徑上i的前一個結(jié)點(diǎn)。當(dāng)dist[u]+c[u][i]<dist[i]時，Prev[i]=u根據(jù)Prev的值，產(chǎn)生最短路徑。例：Prev[2]=1,Prev[3]=4，Prev[4]=1，Prev[5]=3頂點(diǎn)1到頂點(diǎn)5的路徑：143512345例題1)v1v2:102)v1v3:503)v1v4:304)v1v5:60迭代Svid[2]d[3]d[4]d[5]初始{1}

10

301001{1,2}21060301002{1,2,4}4105030903{1,2,3,4}3

105030604{1,2,3,4,5}510503060103010050102060

voidDijkstra(intn,intv,Typedist[],intprev[],Type**c){bools[maxint]；

for(inti=1;i<=n;i++){dist[i]=c[v][i]；

s[i]=false；

if(dist[i]==maxint)prev[i]=0；

elseprev[i]=v;}dist[v]=0；s[v]=true；

for(inti=1;i<n；i++){inttemp=maxint；

intu=v；

for(intj=1；j<=n；j++)if((!s[j])&&(dist[j]<temp)){u=j；

temp=dist[j]；}s[u]=true；

for(intj=1；j<=n;j++)；

if((!s[j])＆＆(c[u][j]<maxint)){Typenewdist=dist[u)+c[u][j];if(newdist<dist[j]){dist[]]=newdist；

prev[j]=u;}}}}單源最短路徑問題的Dijkstra算法分析:用帶權(quán)鄰接矩陣表示有n個頂點(diǎn)和e條邊的帶權(quán)有向圖,主循環(huán)體需要O(n)時間,循環(huán)需要執(zhí)行n-1次,所以完成循環(huán)需要O(n2).時間復(fù)雜性分析：O(n2)，任何最短路徑算法必須至少對每條邊檢查一次，因?yàn)槿魏我粭l邊都有可能在最短路徑中。因此這種算法的最小可能時間為O(e)。由于使用耗費(fèi)鄰接矩陣來描述圖，僅決定哪條邊在有向圖中就需O(n2)的時間。算法的其余部分所需時間不超過O(n2)。因此,采用這種描述方法的算法需花費(fèi)O(n2)的時間。Dijkstra算法正確性證明貪心選擇性質(zhì)vuxdist[x]≤d[v,x]d[v,u]=d[v,x]+d[x,u]d[x,u]>0d[v,x]+d[x,u]<dist[u]dist[x]≤dist[u]

這與假設(shè)矛盾。假設(shè)有一條從源到u的更短的路徑（經(jīng)過X）。4.6最小生成樹圖G=(V,E)是無向連通帶權(quán)圖，即一個網(wǎng)絡(luò)。若子圖G’是一棵包含G的全部頂點(diǎn)的樹，則稱G’為G的生成樹。生成樹上各邊的權(quán)之和稱為生成樹的耗費(fèi)。耗費(fèi)最小的生成樹叫最小生成樹。最小的生成樹在通信網(wǎng)絡(luò)、電路設(shè)計(jì)中應(yīng)用廣泛。貪心算法可用于構(gòu)造最小生成樹(Prim算法或Kruskal算法）問題陳述:設(shè)G(V,E)是一個無向連通帶權(quán)圖。E中每條邊(v,w)的權(quán)為c[v][w],若G的一個子圖G’是一棵包含G的所有頂點(diǎn)的樹，則稱G’為G的生成樹。生成樹各邊權(quán)的總和稱為該生成樹的耗費(fèi)。在G的所有生成樹中,耗費(fèi)最小的生成樹稱為G的最小生成樹.抽象描述:輸入:任一連通生成子圖(該子圖的邊集合)

可行解:圖的生成樹,

優(yōu)化函數(shù):生成樹的各邊權(quán)值之和最優(yōu)解:使優(yōu)化函數(shù)達(dá)到最小的生成樹.最小生成樹性質(zhì)：設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。若(u,v)∈E,u∈U,v∈V-U,且在所有這樣的邊中，(u,v)的權(quán)c[u][v]最小，那么一定存在G的一棵最小生成樹包含邊(u,v)。UV-Uuu’v’v算法思路:首先置S={1},T=?.若SV,就作如下的貪心選擇：選取滿足條件iS,jV-S,且c[i][j]最小的邊(i,j),將頂點(diǎn)j添加到S中邊(i,j)添加到T中.這個過程一直進(jìn)行到S=V時為止.T中的所有邊構(gòu)成G的一棵最小生成樹。voidPrim(intn,Type**c){T=?;S={1};while(S!=V){(i,j)=iS且jV-S的最小權(quán)邊;T=T∪{(i,j)};S=S∪{j};}}算法描述Prim算法設(shè)G=(V,E)是一個連通帶權(quán)圖,V={l,2,…,n}。例題例題SSSSSSS=V算法說明：T中最后包含n-1條邊。時間復(fù)雜度O(n2)具體實(shí)現(xiàn)為了找出滿足i∈S,j∈V-S且c[i][j]最小的邊(i,j)，設(shè)置兩個數(shù)組：closest和Lowcostclosest[j]表示j在S中一個鄰接頂點(diǎn)，并且c[j][closest[j]]≤c[j][k]，k是j在S中的其它鄰接頂點(diǎn)Lowcost[j]=c[j][closest[j]]Template<classType>VoidPrim(intn,Type**c){Typelowcost[maxint];intclosest[maxint];bools[maxint];s[1]=true;for(inti=2;i<=n;i++){lowcost[i]=c[1][i]; closest[i]=1;s[i]=false;}for(inti=1;i<=n;i++){Typemin=inf;intj=1;

for(intk=2;k<=n;k++)if((lowcost[k]<min)&&(!s[k])){min=lowcost[k];j=k;}cout<<j<<closet[j]<<endl;s[j]=true;for(intk=2;k<=n;k++)if((c[j][k]<lowcost[k]&&(!s[k])){lowcost[k]=c[j][k];closet[k]=j;}}}Kruskal算法：(假設(shè)有n個頂點(diǎn)，e條邊)1）將圖G的n個頂點(diǎn)看作n個孤立的連通分支2）將邊按權(quán)值從小到大排列3）在不構(gòu)成環(huán)路的情況下，依次選取權(quán)值最小的邊，直到有n-1條邊為止。當(dāng)查看第k條邊(v,w)時，若v和w屬于兩個不同的連通分支T1和T2，就用邊(v,w)將T1和T2連成一個連通分支，并繼續(xù)處理第k+1條邊。若v和w屬于同一個連通分支，則直接查看第k+1條邊。例題template<classType>boolKruskal(intn,inte,EdgeNode<Type>E[],EdgeNode<Type>t[])MinHeap<EdgeNode<Type>>H(1);H.Initialize(E,e,e);UnionFindU(n);intk=0;while(e&&k<n-1){EdgeNode<int>x;H.DeleteMin(x);e--;inta=U.Find(x.u);intb=U.Eind(x.v);if(a!=b){t[k++]=x;U.Union(a,b);}}H.Deactivate()renturn(k==n-1)Kruska算法e1(1)e2(6)e8(9)e6(2)e9(4)e5(5)e4(7)e10(8)e11(3)e7(10)e3(11)1)以G中全部點(diǎn)為點(diǎn)作圖2)按權(quán)的大小次序依次添加各邊,若出現(xiàn)回路則忽略此邊.3)加入n-1條邊后就得到最小生成樹.12537求最小生成樹(Kruscal)最優(yōu)解:(e1,e6,e11,e5,e4)Kruskal算法在實(shí)現(xiàn)時需要用到集合的并運(yùn)算(union)和查找運(yùn)算(find)。抽象數(shù)據(jù)類型UnionFind支持這些基本運(yùn)算。時間復(fù)雜度為O(eloge)

。

Kruskal算法的時間復(fù)雜度為O(eloge)

。Prim算法或Kruskal算法的比較兩個算法的時間復(fù)雜度分別為O(n2)和O(eloge)

當(dāng)圖的邊數(shù)較少時，Kruskal算法優(yōu)于Prim算法；當(dāng)圖的邊數(shù)較多時，用Prim算法為好。4.7多機(jī)調(diào)度問題N個獨(dú)立的作業(yè){1,2,…,n}，m臺相同的機(jī)器。每個作業(yè)需要在機(jī)器上加工ti時間。每個作業(yè)不能拆分成更小的作業(yè)，只能在一臺機(jī)器上完成，而且處理過程不能中斷。如何調(diào)度，使得全部作業(yè)在最短時間內(nèi)完成？當(dāng)n≤m時，很簡單。當(dāng)n>m時，屬于NP完全難題，迄今未有效解決。用貪心算法可得到近似解。貪心策略：處理時間長的作業(yè)優(yōu)先調(diào)度。將n個作業(yè)按處理時間，由大到小排序，依次分給空閑機(jī)器。例：7個獨(dú)立的作業(yè){a,b,c,d,e,f,g}，加工時間分別為{2，14，4，16，6，5，3}3臺機(jī)器：M1,M2,M3貪心調(diào)度結(jié)果：加工時間為17，達(dá)到最優(yōu)dbegfca請考慮舉個反例。classJobNode{friendvoidGreedy(JobNode*,int,int);friendvoidmain(void);public:operatorint()const{returntime;}private:intID,time;};classMachineNode{friendvoidGreedy(JobNode*,int,int);public:operatorint()const{returnavail;}private:intID,avail;}多機(jī)調(diào)度問題的貪心近似算法template<classType>voidGreedy(Typea[]，intn，intm){if(n<=m){cont<<”為每個作業(yè)分配一臺機(jī)器.“<<endlreturn；}Sort(a，n)；MinHeap<MachineNode>H(m)；MachineNodex；for(int：i=1；i<=m;i++){x．a(chǎn)vail=0；

x．ID=i;H．Insert(x)；}for(inti=n；i>=1；i--){H．DeleteMin(x)；

cout<<”將機(jī)器”<<x．ID<<“從”<<x．a(chǎn)vail<<"到”

<<(x．a(chǎn)vail十a(chǎn)[i]．time)<<”的時間段分配給作業(yè)”<<a[i].ID<<endl；

x．a(chǎn)vail+=a[i]．time；

H．insert(x)；}}有期限的任務(wù)安排問題*設(shè)有n項(xiàng)任務(wù)J1,…,Jn，每項(xiàng)都有一個完成期限b1,…,bn，任務(wù)Ji在這期限bi內(nèi)完成可獲利Ci，自然不允許不在期限內(nèi)完成了。假定每個任務(wù)的加工所用的機(jī)器時間都為一個單位，問應(yīng)如何安排加工順序，使得收益最多？這里優(yōu)先的標(biāo)準(zhǔn)除考慮加工的任務(wù)的利潤C(jī)i的大小外還需考慮到任務(wù)期限。例如有四個任務(wù)J1,J2,J3,J4．完成任務(wù)的期限分別為2，1，3，4個單位時間，在期限內(nèi)完成可分別獲利潤100．150，200，250元。若僅考慮收入的大小，順序?yàn)镴4,J3,J2,J1。但依此順序，J4加工完畢時，J2已過期限，只好放棄J2而加工J3．J3加工完畢時，J1又超過期限，只好放棄，結(jié)果總收入為450元。如若加工順序改為J2,J1,J3,J4時，則總收入可達(dá)到100+150+200+250＝700元；現(xiàn)假定任務(wù)J1,J2,…,Jn滿足

C1>=C2>=…>=Cn基本思想：按照b1,b2,…,bn依序?qū)ζ溥M(jìn)行調(diào)整，排在后面的或提前或排除。優(yōu)先策略如下：假設(shè)已安排了前面s個，即Jr1,Jr2,…,Jrs為最優(yōu)安排的前s個，則應(yīng)滿足bri≤i,i=1,2,…,s(*)即已經(jīng)安排的任務(wù)都能在規(guī)定期限內(nèi)完成。對后面等待安排的任務(wù)Jk來說，與之對應(yīng)的Ck無疑滿足Ck≤Cri,i=1,2,…,s若bk＞s，即任務(wù)Jk的利潤比序列(*)中所有的都少，期限又長，則Jk可直接加入到序列(*)后面。若bk≤s，即任務(wù)Jk期限較急，Jk是否能插入到序列(*)中去？插入到哪里？就得看序列(*)是否存在允許Jk插入的可能了。首先要和Jrs進(jìn)行比較，若