第五章貪心算法顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當然，希望貪心算法得到的最終結果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結果卻是最優(yōu)解的很好近似?；顒影才艈栴}

活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。

設有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi,且si<fi。如果選擇了活動i，則它在半開時間區(qū)間[si,fi)內占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動i與活動j是相容的。也就是說，當si≥fj或sj≥fi時，活動i與活動j相容。在下面所給出的解活動安排問題的貪心算法greedySelector:publicstaticintgreedySelector(int[]s,int[]f,booleana[]){intn=s.length-1;a[1]=true;intj=1;intcount=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){a[i]=true;j=i;count++;}elsea[i]=false;}returncount;}各活動的起始時間和結束時間存儲于數(shù)組s和f中且按結束時間的非減序排列

由于輸入的活動以其完成時間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。

算法greedySelector的效率極高。當輸入的活動已按結束時間的非減序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。例：設待安排的11個活動的開始時間和結束時間按結束時間的非減序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314

算法greedySelector的計算過程如左圖所示。圖中每行相應于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當前正在檢查相容性的活動。若被檢查的活動i的開始時間Si小于最近選擇的活動j的結束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。

貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結論可以用數(shù)學歸納法證明。0-1背包問題：

給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?

在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。背包問題：

與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。

這2類問題都具有最優(yōu)子結構性質，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。用貪心算法解背包問題的基本步驟：

首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。 具體算法可描述如下頁：

publicstaticfloatknapsack(floatc,float[]w,float[]v,float[]x){intn=v.length;Element[]d=newElement[n];for(inti=0;i<n;i++)d[i]=newElement(w[i],v[i],i);MergeSort.mergeSort(d);inti;floatopt=0;for(i=0;i<n;i++)x[i]=0;for(i=0;i<n;i++){if(d[i].w>c)break;x[d[i].i]=1;opt+=d[i].v;c-=d[i].w;}if(i<n){x[d[i].i]=c/d[i].w;opt+=x[d[i].i]*d[i].v;}returnopt;}

算法knapsack的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為O（nlogn）。當然，為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質。貪心算法的基本要素對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。事實上，在考慮0-1背包問題時，應比較選擇該物品和不選擇該物品所導致的最終方案，然后再作出最好選擇。由此就導出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。 實際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。最優(yōu)裝載有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。1.算法描述 最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。具體算法描述如下頁。

publicstaticfloatloading(floatc,float[]w,int[]x){intn=w.length;Element[]d=newElement[n];for(inti=0;i<n;i++)d[i]=newElement(w[i],i);MergeSort.mergeSort(d);floatopt=0;for(inti=0;i<n;i++)x[i]=0;for(inti=0;i<n&&d[i].w<=c;i++){x[d[i].i]=1;opt+=d[i].w;c-=d[i].w;}returnopt;}其中Element類說明為參見本書P115哈夫曼樹(最優(yōu)二叉樹)1、最優(yōu)二叉樹（HuffmanTree)

樹的路徑長度：是從樹根到每一結點的路徑長度之和。(完全二叉樹)樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度(該結點到樹根之間路徑長度與結點上權的乘積)之和。7524WPL=36WPL=46WPL=35dcbacbaddcba舉例：考試分數(shù)段人數(shù)統(tǒng)計。

1、最優(yōu)二叉樹（HuffmanTree)

構造方法：(1)根據(jù)給定的n個權值{w1,w2,…,wn}構成n棵二叉樹的集合F={T1，T2，…，Tn}，其中二叉樹Ti中只有一個帶權為wi的根結點，其左右子樹均為空。(2)在F中選取兩棵結點的權值最小的樹作為左右子樹構造一棵新的二叉樹，且新二叉樹的根結點權值為其左右子樹上結點權值之和。(3)在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。(4)重復(2)和(3)，直到F只含一棵二叉樹，即為所求。

例a7b5c2d4a7b5c2d46a7b5c2d4611a7b5c2d461118哈夫曼編碼哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。1.前綴碼 對每一個字符規(guī)定一個0,1串作為其代碼，并要求任一字符的代碼都不是其他字符代碼的前綴。這種編碼稱為前綴碼。

編碼的前綴性質可以使譯碼方法非常簡單。 表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹，即樹中任一結點都有2個兒子結點。

平均碼長定義為：

使平均碼長達到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。2.構造哈夫曼編碼

哈夫曼提出構造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。 哈夫曼算法以自底向上的方式構造表示最優(yōu)前綴碼的二叉樹T。 算法以|C|個葉結點開始，執(zhí)行|C|－1次的“合并”運算后產(chǎn)生最終所要求的樹T。2、赫夫曼編碼：

例：有一串電文：ababadababbcddcdaa問題提出：如何電文編碼使總碼最短？前提：字符不等概率，能順利翻譯解決方法：字符不是等長碼——前綴編碼構造赫夫曼數(shù)，左支為‘0’，右支為‘1’例：右圖結點赫夫曼編碼為:a(0)b(10)c(110)d(111)dcban個權值的赫夫曼樹的特點：

(1)樹葉個樹——n(2)結點個數(shù)——2*n-1(3)度為1的結點個數(shù)為零3、算法實現(xiàn)：

voidHuffmaCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){if(n<=1)return;m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(Htnode));for(p=HT,i=1;i<=n;++i,++p,++w)*p={*w,0,0,0};for(;i<=m;++i,++p)*p={0,0,0,0};for(i=n+1;i<=m;++i){Select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;

}/*哈夫曼編碼*/HC=(HuffmanCode)malloc((n+1)*sizeof(char*));cd=(char)malloc(n*sizeof(char));cd[n-1]=“\0”;for(i=1;i<=n;++i){

start=n-1;for(c=I,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)if(HT[f].lchild==c)cd[--start]=“0”;elsecd[--start]=“1”;HC[I]=(char*)malloc((n-start)*sizeof(char));Strcpy(HC[i],&cd[start]);}free(cd);}iweightparentlchildrchild152293748514623738119101112131415F={5，29，7，8，14，23，3，11}538715399817①②③④⑤⑥⑦⑧781543781010153419811811811111989141529514151212295102319426231913134261129295822914291458212425815151001314typedefstruct{intweight;intparent,lchild,rchild;}hu;huht[16];單源最短路徑

給定帶權有向圖G=(V,E)，其中每條邊的權是非負實數(shù)。另外，還給定V中的一個頂點，稱為源?，F(xiàn)在要計算從源到所有其他各頂點的最短路長度。這里路的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑問題。 1.算法基本思想 Dijkstra算法是解單源最短路徑問題的貪心算法。其基本思想是，設置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。 初始時，S中僅含有源。設u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其他頂點之間的最短路徑長度。

例如，對右圖中的有向圖，應用Dijkstra算法計算從源頂點1到其他頂點間最短路徑的過程列在下頁的表中。迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060算法代碼描述參見教材P122AGHDFEBCB點信源樹

ADCBHGFE42372262123B點所在無向圖步驟B的子信源碼ACDEFGH初始化{B}27∞2∞∞∞1{BA，B}

7∞2∞8∞2{BA，B，BE}

7∞

43∞3{BA，B，BE，EG}

7∞

4

74{BA，B，BE，EF，EG}

7∞

65{BA，B，BE，EF，EG，F(xiàn)H}

78

6{BA，B，BC，BE，EF，EG，F(xiàn)H}

8

7{BA，B，BC，HD，BE，EF，EG，F(xiàn)H}

[例題3]穿越沙漠沒有水或食物，你將無法前行，為了穿越沙漠，應該購買多少食物呢？

在出發(fā)地，你可以采購食物和獲得無限多的免費水，但由于背包容量有限，在任意時候擁有的水和食物總量不得超過一個給定值limit。沙漠中有若干綠洲，在綠洲你可以得到無限多的水，可以存儲食物。你將被告知出發(fā)地、目的地和所有綠洲的平面位置。每走x單位長的路程你就要消耗x個單位的水和x個單位的食物。請確定在出發(fā)地最少購買的食物量。注：出發(fā)地的食物按照整數(shù)單位出售并且總量為10的6次冪。

注：題目來源ACM/ICPCWorldFinals2002[分析]由于水是免費的，所以我們需要讓帶的食物盡量少。假設已經(jīng)知道從綠洲j出發(fā)時必須在綠洲j保存的食物總量d[j],考慮從綠洲i出發(fā)，第一次到達綠洲j的情況：需要在綠洲i保存多少食物，才能保證在綠洲j保存d[j]單位的食物？為了在綠洲j儲存t單位的食物，我們需要在i和j之間進行往返。假設i和j的直線距離為dist，則每次應該攜帶dist單位的水和limit-dist單位的食物到j，然后從j帶dist單位的水和dist單位的食物返回i。從t往回倒推，每次往返讓j多存儲了limit-3*dist單位的食物，而最后一次到j后并不需要返回i，因此最后一次可以在綠洲j存儲limit-2*dist單位的食物。因此，需要往返的次數(shù)m為不小于（d[j]-limit+2*dist）/(limit-3*dist)的最小整數(shù)。在往返時消耗的食物量為（2m+1）*dist，因此從綠洲i出發(fā)第一次到達綠洲j時，至少需要存儲d[j]+(2m+1)*dist單位的食物。接下來，對t來說，d[t]=0,利用最短路的標號法思想，從t往回推，每次選擇需要存儲食物最少的綠洲，把它的標號永久化。每次確定一個永久標號的時間花費為O(n)，故總的時間復雜度為O(n*n)。最小生成樹設G=(V,E)是無向連通帶權圖，即一個網(wǎng)絡。E中每條邊(v,w)的權為c[v][w]。如果G的子圖G’是一棵包含G的所有頂點的樹，則稱G’為G的生成樹。生成樹上各邊權的總和稱為該生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。 網(wǎng)絡的最小生成樹在實際中有廣泛應用。例如，在設計通信網(wǎng)絡時，用圖的頂點表示城市，用邊(v,w)的權c[v][w]表示建立城市v和城市w之間的通信線路所需的費用，則最小生成樹就給出了建立通信網(wǎng)絡的最經(jīng)濟的方案。1.最小生成樹性質 用貪心算法設計策略可以設計出構造最小生成樹的有效算法。本節(jié)介紹的構造最小生成樹的Prim算法和Kruskal算法都可以看作是應用貪心算法設計策略的例子。盡管這2個算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹性質： 設G=(V,E)是連通帶權圖，U是V的真子集。如果(u,v)

E，且u

U，v

V-U，且在所有這樣的邊中，(u,v)的權c[u][v]最小，那么一定存在G的一棵最小生成樹，它以