第五章貪心算法

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

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

設(shè)有n個(gè)活動的集合E={1,2,…,n}，其中每個(gè)活動都要求使用同一資源，如演講會場等，而在同一時(shí)間內(nèi)只有一個(gè)活動能使用這一資源。每個(gè)活動i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si<fi。如果選擇了活動i，則它在半開時(shí)間區(qū)間[si,fi)內(nèi)占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動i與活動j是相容的。也就是說，當(dāng)si≥fj或sj≥fi時(shí)，活動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í)間和結(jié)束時(shí)間存儲于數(shù)組s和f中且按結(jié)束時(shí)間的非減序排列

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

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

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

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

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

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

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

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

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

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的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排序。因此，算法的計(jì)算時(shí)間上界為O（nlogn）。當(dāng)然，為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)。貪心算法的基本要素對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮0-1背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。 實(shí)際上也是如此，動態(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)

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

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

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

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

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

平均碼長定義為：

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

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

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

(1)樹葉個(gè)樹——n(2)結(jié)點(diǎn)個(gè)數(shù)——2*n-1(3)度為1的結(jié)點(diǎn)個(gè)數(shù)為零3、算法實(shí)現(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];單源最短路徑

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

例如，對右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其他頂點(diǎn)間最短路徑的過程列在下頁的表中。迭代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點(diǎn)信源樹

ADCBHGFE42372262123B點(diǎn)所在無向圖步驟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]穿越沙漠沒有水或食物，你將無法前行，為了穿越沙漠，應(yīng)該購買多少食物呢？

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

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