貪心算法-課件

第4章貪心算法1第4章貪心算法1學(xué)習(xí)要點(diǎn)理解貪心算法的概念。掌握貪心算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）貪心選擇性質(zhì)理解貪心算法與動(dòng)態(tài)規(guī)劃算法的差異理解貪心算法的一般理論通過(guò)應(yīng)用范例學(xué)習(xí)貪心設(shè)計(jì)策略。（1）活動(dòng)安排問(wèn)題；（2）最優(yōu)裝載問(wèn)題；（3）哈夫曼編碼；（4）單源最短路徑；（5）最小生成樹(shù)；（6）多機(jī)調(diào)度問(wèn)題。2學(xué)習(xí)要點(diǎn)23一、貪心算法定義指的是從對(duì)問(wèn)題的某一初始解出發(fā),一步一步的攀登給定的目標(biāo),盡可能快地去逼近更好的解。當(dāng)達(dá)到某一步,不能再攀登時(shí),算法便終止。二、貪心算法特點(diǎn)貪心算法總是做出在當(dāng)前看來(lái)是最好的選擇,它并不是從總體最優(yōu)上加以考慮,他所作出的選擇只是在某種意義上的局部最優(yōu)選擇。能夠得到的解不一定是最優(yōu)解。概述3一、貪心算法定義指的是從對(duì)問(wèn)題的某一初始解出發(fā),舉例：假設(shè)有四種硬幣25分、10分、5分、1分若干個(gè)。要湊夠63分，應(yīng)該怎樣取硬幣使得硬幣個(gè)數(shù)最少？描述問(wèn)題：數(shù)組a[4]存放所取四種硬幣的個(gè)數(shù),w[4]存放四種硬幣幣值約束條件可行解目標(biāo)函數(shù)4如果把硬幣換為：一分、五分、一角一分，而找給顧客的是一角五分舉例：假設(shè)有四種硬幣25分、10分、5分、1分若干個(gè)。要湊夠5背包問(wèn)題:共有n種物品要裝入一個(gè)背包中，背包可容納的重量是C，每種物品的容量為wi，每個(gè)物品的價(jià)值為Vi，如何裝才能獲得最大的價(jià)值？用一個(gè)向量（x1,x2,x3,…,xn）,表示裝的個(gè)數(shù)多少？約束條件：0<=xi<=1

目標(biāo)函數(shù)：5背包問(wèn)題:共有n種物品要裝入一個(gè)背包中，背包可容納的重量是6假設(shè)n=3，C=20，(v1、v2、v3)=(25、24、15)(w1、w2、w3)=(18、15、10)求6假設(shè)n=3，C=20，(v1、v2、v3)=(25、2顧名思義，貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問(wèn)題，最小生成樹(shù)問(wèn)題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。7顧名思義，貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心4.1活動(dòng)安排問(wèn)題

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

活動(dòng)安排問(wèn)題就是要在4.1活動(dòng)安排問(wèn)題9設(shè)有n個(gè)活動(dòng)的集合E={1,2,…,n}，其中每個(gè)活動(dòng)都要求使用同一資源，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si<fi。如果選擇了活動(dòng)i，則它在半開(kāi)時(shí)間區(qū)間[si,fi)內(nèi)占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動(dòng)i與活動(dòng)j是相容的。也就是說(shuō)，當(dāng)si≥fj或sj≥fi時(shí)，活動(dòng)i與活動(dòng)j相容。4.1活動(dòng)安排問(wèn)題9設(shè)有n個(gè)活動(dòng)的集合E={1,24.1活動(dòng)安排問(wèn)題template<classType>voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}10下面給出解活動(dòng)安排問(wèn)題的貪心算法GreedySelector:各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組s和f中且按結(jié)束時(shí)間的非減序排列

4.1活動(dòng)安排問(wèn)題template<classType>4.1活動(dòng)安排問(wèn)題

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

算法greedySelector的效率極高。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需O(n)的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。如果所給出的活動(dòng)未按非減序排列，可以用O(nlogn)的時(shí)間重排。114.1活動(dòng)安排問(wèn)題 由于輸入的活動(dòng)以其完成時(shí)間的4.1活動(dòng)安排問(wèn)題

例：設(shè)待安排的11個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：124.1活動(dòng)安排問(wèn)題例：設(shè)待安排的11個(gè)活動(dòng)的開(kāi)始時(shí)間和4.1活動(dòng)安排問(wèn)題

算法greedySelector的計(jì)算過(guò)程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長(zhǎng)條表示的活動(dòng)是已選入集合A的活動(dòng)，而空白長(zhǎng)條表示的活動(dòng)是當(dāng)前正在檢查相容性的活動(dòng)。134.1活動(dòng)安排問(wèn)題

算法greedySelector4.1活動(dòng)安排問(wèn)題

若被檢查的活動(dòng)i的開(kāi)始時(shí)間Si小于最近選擇的活動(dòng)j的結(jié)束時(shí)間fi，則不選擇活動(dòng)i，否則選擇活動(dòng)i加入集合A中。

貪心算法并不總能求得問(wèn)題的整體最優(yōu)解。但對(duì)于活動(dòng)安排問(wèn)題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動(dòng)集合A的規(guī)模最大。這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明。144.1活動(dòng)安排問(wèn)題若被檢查的活動(dòng)i的開(kāi)4.2貪心算法的基本要素

本節(jié)著重討論可以用貪心算法求解的問(wèn)題的一般特征。 對(duì)于一個(gè)具體的問(wèn)題，怎么知道是否可用貪心算法解此問(wèn)題，以及能否得到問(wèn)題的最優(yōu)解呢?這個(gè)問(wèn)題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問(wèn)題中看到這類(lèi)問(wèn)題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

154.2貪心算法的基本要素 本節(jié)著重討論可以用貪心算4.2貪心算法的基本要素1、貪心選擇性質(zhì)16

所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問(wèn)題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。

對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。4.2貪心算法的基本要素1、貪心選擇性質(zhì)16所謂貪4.2貪心算法的基本要素

當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(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)鍵特征。

172、最優(yōu)子結(jié)構(gòu)性質(zhì)4.2貪心算法的基本要素 當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子4.2貪心算法的基本要素

貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類(lèi)算法的一個(gè)共同點(diǎn)。但是，對(duì)于具有最優(yōu)子結(jié)構(gòu)的問(wèn)題應(yīng)該選用貪心算法還是動(dòng)態(tài)規(guī)劃算法求解?是否能用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題也能用貪心算法求解?下面研究2個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，并以此說(shuō)明貪心算法與動(dòng)態(tài)規(guī)劃算法的主要差別。183、貪心算法與動(dòng)態(tài)規(guī)劃算法的差異4.2貪心算法的基本要素 貪心算法和動(dòng)態(tài)規(guī)劃算法都要求4.2貪心算法的基本要素0-1背包問(wèn)題：

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

在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。4.2貪心算法的基本要素0-1背包問(wèn)題：19在選4.2貪心算法的基本要素背包問(wèn)題：

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

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

4.2貪心算法的基本要素背包問(wèn)題：20這2類(lèi)問(wèn)題都4.2貪心算法的基本要素

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

21用貪心算法解背包問(wèn)題的基本步驟：4.2貪心算法的基本要素首先計(jì)算每種物品單位重量4.2貪心算法的基本要素voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);inti;for(i=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}22

算法knapsack的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排序。因此，算法的計(jì)算時(shí)間上界為O（nlogn）。為了證明算法的正確性，還必須證明背包問(wèn)題具有貪心選擇性質(zhì)。4.2貪心算法的基本要素voidKnapsack(int4.2貪心算法的基本要素

對(duì)于0-1背包問(wèn)題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無(wú)法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮0-1背包問(wèn)題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問(wèn)題。這正是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。 實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解0-1背包問(wèn)題。234.2貪心算法的基本要素 對(duì)于0-1背包問(wèn)題，貪心選擇4.3最優(yōu)裝載

有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問(wèn)題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。244.3最優(yōu)裝載有一批集裝箱要裝上一艘載重量為c的對(duì)最優(yōu)裝載問(wèn)題進(jìn)行形式化描述25用一個(gè)向量（x1,x2,x3,…,xn）,表示裝的個(gè)數(shù)多少？約束條件：xi

∈{0,1}目標(biāo)函數(shù)：對(duì)最優(yōu)裝載問(wèn)題進(jìn)行形式化描述25用一個(gè)向量（x1,x2,x3261、算法描述最優(yōu)裝載問(wèn)題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略可產(chǎn)生最優(yōu)裝載問(wèn)題的最優(yōu)解。

261、算法描述4.3最優(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]];}}274.3最優(yōu)裝載template<classType>274.3最優(yōu)裝載2、貪心選擇性質(zhì) 可以證明最優(yōu)裝載問(wèn)題具有貪心選擇性質(zhì)。3、最優(yōu)子結(jié)構(gòu)性質(zhì) 最優(yōu)裝載問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 由最優(yōu)裝載問(wèn)題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法loading的正確性。 算法loading的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法所需的計(jì)算時(shí)間為O(nlogn)。

284.3最優(yōu)裝載2、貪心選擇性質(zhì)284.4哈夫曼編碼

哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來(lái)建立一個(gè)用0，1串表示各字符的最優(yōu)表示方式。 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長(zhǎng)的編碼，可以大大縮短總碼長(zhǎng)。1、前綴碼 對(duì)每一個(gè)字符規(guī)定一個(gè)0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。294.4哈夫曼編碼 哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十4.4哈夫曼編碼 編碼的前綴性質(zhì)可以使譯碼方法非常簡(jiǎn)單。 表示最優(yōu)前綴碼的二叉樹(shù)總是一棵完全二叉樹(shù)，即樹(shù)中任一結(jié)點(diǎn)都有2個(gè)兒子結(jié)點(diǎn)。

平均碼長(zhǎng)定義為： 使平均碼長(zhǎng)達(dá)到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。30

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

314.4哈夫曼編碼2、構(gòu)造哈夫曼編碼314.4哈夫曼編碼 在書(shū)上給出的算法huffmanTree中，編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊(duì)列Q用在貪心選擇時(shí)有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹(shù)。一旦2棵具有最小頻率的樹(shù)合并后，產(chǎn)生一棵新的樹(shù)，其頻率為合并的2棵樹(shù)的頻率之和，并將新樹(shù)插入優(yōu)先隊(duì)列Q。經(jīng)過(guò)n－1次的合并后，優(yōu)先隊(duì)列中只剩下一棵樹(shù)，即所要求的樹(shù)T。 算法huffmanTree用最小堆實(shí)現(xiàn)優(yōu)先隊(duì)列Q。初始化優(yōu)先隊(duì)列需要O(n)計(jì)算時(shí)間，由于最小堆的removeMin和put運(yùn)算均需O(logn)時(shí)間，n－1次的合并總共需要O(nlogn)計(jì)算時(shí)間。因此，關(guān)于n個(gè)字符的哈夫曼算法的計(jì)算時(shí)間為O(nlogn)。324.4哈夫曼編碼 在書(shū)上給出的算法huffmanTr4.4哈夫曼編碼3、哈夫曼算法的正確性 要證明哈夫曼算法的正確性，只要證明最優(yōu)前綴碼問(wèn)題具有貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 (1)貪心選擇性質(zhì) (2)最優(yōu)子結(jié)構(gòu)性質(zhì)334.4哈夫曼編碼3、哈夫曼算法的正確性334.5單源最短路徑

給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源。現(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問(wèn)題通常稱為單源最短路徑問(wèn)題。

1、算法基本思想 Dijkstra算法是解單源最短路徑問(wèn)題的貪心算法。344.5單源最短路徑 給定帶權(quán)有向圖G=(V,E)，其中4.5單源最短路徑

基本思想:設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。 初始時(shí)，S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長(zhǎng)度。354.5單源最短路徑 基本思想:設(shè)置頂點(diǎn)集合S并不斷地作貪問(wèn)題描述:36輸入帶權(quán)有向圖G=(V，E)，V={1，2，…，n}，頂點(diǎn)V1是源C[i][j]表示邊(i,j)的權(quán)dist[i]表示從源到頂點(diǎn)vi的最短特殊路徑長(zhǎng)度prev[i]表示從源到頂點(diǎn)i的最短路徑上,結(jié)點(diǎn)i的前一個(gè)頂點(diǎn)。輸入?yún)?shù)：n,v1,c[i][j]輸出參數(shù)：dist[i],prev[i]問(wèn)題描述:36輸入帶權(quán)有向圖G=(V，E)，V={1，2，算法描述：37基本思想：設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。S[i]—源點(diǎn)到i頂點(diǎn)的最短路徑是否找到初始化：for(i=1;i<=n;i++){s[i]=0;dist[i]=c[v1][i];}S[v1]=1,dist[v1]=0;每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，并將u添加到S中for(num=2;num<=n;num++){從dist[2]到dist[n]選取一頂點(diǎn)u且滿足s[u]=0,使dist[u]=min{dist[2],dist[3],…,dist[n]};s[u]=1;}算法描述：37基本思想：設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)38Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，將u添加到S中后，同時(shí)對(duì)數(shù)組dist作必要的修改。for(j=1;j<=n;j++){if(s[j]==0&&c[u][j]<maxint){newdist=dist[u]+c[u][j];if(newdist<dist[j]){dist[j]=newdist;prev[j]=u;}}}整個(gè)過(guò)程執(zhí)行n-1次38Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度4.5單源最短路徑

例如，對(duì)右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑的過(guò)程列在下頁(yè)的表中。394.5單源最短路徑例如，對(duì)右圖中的有向圖，應(yīng)用Dij4.5單源最短路徑40Dijkstra算法的迭代過(guò)程：

4.5單源最短路徑40Dijkstra算法的迭代過(guò)程：4.5單源最短路徑2、算法的正確性和計(jì)算復(fù)雜性(1)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)(3)計(jì)算復(fù)雜性 對(duì)于具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么Dijkstra算法的主循環(huán)體需要時(shí)間。這個(gè)循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要時(shí)間。算法的其余部分所需要時(shí)間不超過(guò)。414.5單源最短路徑2、算法的正確性和計(jì)算復(fù)雜性414.6最小生成樹(shù)

設(shè)G=(V,E)是無(wú)向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為c[v][w]。如果G的子圖G’是一棵包含G的所有頂點(diǎn)的樹(shù)，則稱G’為G的生成樹(shù)。生成樹(shù)上各邊權(quán)的總和稱為該生成樹(shù)的耗費(fèi)。在G的所有生成樹(shù)中，耗費(fèi)最小的生成樹(shù)稱為G的最小生成樹(shù)。 網(wǎng)絡(luò)的最小生成樹(shù)在實(shí)際中有廣泛應(yīng)用。例如，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通信線路所需的費(fèi)用，則最小生成樹(shù)就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。424.6最小生成樹(shù) 設(shè)G=(V,E)是無(wú)向連通帶權(quán)圖，4.6最小生成樹(shù)1、最小生成樹(shù)性質(zhì) 用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹(shù)的有效算法。本節(jié)介紹的構(gòu)造最小生成樹(shù)的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的例子。盡管這2個(gè)算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹(shù)性質(zhì)： 設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權(quán)c[u][v]最小，那么一定存在G的一棵最小生成樹(shù)，它以(u,v)為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱為MST性質(zhì)。

434.6最小生成樹(shù)1、最小生成樹(shù)性質(zhì)434.6最小生成樹(shù)2、Prim算法

設(shè)G=(V,E)是連通帶權(quán)圖，V={1,2,…,n}。 構(gòu)造G的最小生成樹(shù)的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，jV-S，且c[i][j]最小的邊，將頂點(diǎn)j添加到S中。這個(gè)過(guò)程一直進(jìn)行到S=V時(shí)為止。 在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹(shù)。444.6最小生成樹(shù)2、Prim算法444.6最小生成樹(shù) 利用最小生成樹(shù)性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的邊集合T始終包含G的某棵最小生成樹(shù)中的邊。因此，在算法結(jié)束時(shí)，T中的所有邊構(gòu)成G的一棵最小生成樹(shù)。

例如，對(duì)于右圖中的帶權(quán)圖，按Prim算法選取邊的過(guò)程如下頁(yè)圖所示。45 利用最小生成樹(shù)性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的邊集合T始終包含G的某棵最小生成樹(shù)中的邊。因此，在算法結(jié)束時(shí)，T中的所有邊構(gòu)成G的一棵最小生成樹(shù)。

例如，對(duì)于右圖中的帶權(quán)圖，按Prim算法選取邊的過(guò)程如下頁(yè)圖所示。4.6最小生成樹(shù) 利用最小生成樹(shù)性質(zhì)和數(shù)學(xué)歸納法容易證明4.6最小生成樹(shù)464.6最小生成樹(shù)464.6最小生成樹(shù) 在上述Prim算法中，還應(yīng)當(dāng)考慮如何有效地找出滿足條件iS,jV-S，且權(quán)c[i][j]最小的邊(i,j)。實(shí)現(xiàn)這個(gè)目的的較簡(jiǎn)單的辦法是設(shè)置2個(gè)數(shù)組closest和lowcost。 在Prim算法執(zhí)行過(guò)程中，先找出V-S中使lowcost值最小的頂點(diǎn)j，然后根據(jù)數(shù)組closest選取邊(j,closest[j］)，最后將j添加到S中，并對(duì)closest和lowcost作必要的修改。 用這個(gè)辦法實(shí)現(xiàn)的Prim算法所需的計(jì)算時(shí)間為474.6最小生成樹(shù) 在上述Prim算法中，還應(yīng)當(dāng)考慮如何有4.6最小生成樹(shù)3、Kruskal算法

Kruskal算法構(gòu)造G的最小生成樹(shù)的基本思想是，首先將G的n個(gè)頂點(diǎn)看成n個(gè)孤立的連通分支。將所有的邊按權(quán)從小到大排序。然后從第一條邊開(kāi)始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接2個(gè)不同的連通分支：當(dāng)查看到第k條邊(v,w)時(shí)，如果端點(diǎn)v和w分別是當(dāng)前2個(gè)不同的連通分支T1和T2中的頂點(diǎn)時(shí)，就用邊(v,w)將T1和T2連接成一個(gè)連通分支，然后繼續(xù)查看第k+1條邊；如果端點(diǎn)v和w在當(dāng)前的同一個(gè)連通分支中，就直接再查看第k+1條邊。這個(gè)過(guò)程一直進(jìn)行到只剩下一個(gè)連通分支時(shí)為止。

484.6最小生成樹(shù)3、Kruskal算法484.6最小生成樹(shù) 例如，對(duì)前面的連通帶權(quán)圖，按Kruskal算法順序得到的最小生成樹(shù)上的邊如下圖所示。494.6最小生成樹(shù) 例如，對(duì)前面的連通帶權(quán)圖，按Krusk4.6最小生成樹(shù) 關(guān)于集合的一些基本運(yùn)算可用于實(shí)現(xiàn)Kruskal算法。 按權(quán)的遞增順序查看等價(jià)于對(duì)優(yōu)先隊(duì)列執(zhí)行removeMin運(yùn)算?？梢杂枚褜?shí)現(xiàn)這個(gè)優(yōu)先隊(duì)列。 對(duì)一個(gè)由連通分支組成的集合不斷進(jìn)行修改，需要用到抽象數(shù)據(jù)類(lèi)型并查集UnionFind所支持的基本運(yùn)算。 當(dāng)圖的邊數(shù)為e時(shí)，Kruskal算法所需的計(jì)算時(shí)間是。當(dāng)時(shí)，Kruskal算法比Prim算法差，但當(dāng)時(shí)，Kruskal算法卻比Prim算法好得多。504.6最小生成樹(shù) 關(guān)于集合的一些基本運(yùn)算可用于實(shí)現(xiàn)Krus4.7多機(jī)調(diào)度問(wèn)題

多機(jī)調(diào)度問(wèn)題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。 這個(gè)問(wèn)題是NP完全問(wèn)題，到目前為止還沒(méi)有有效的解法。對(duì)于這一類(lèi)問(wèn)題,用貪心選擇策略有時(shí)可以設(shè)計(jì)出較好的近似算法。51

約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。4.7多機(jī)調(diào)度問(wèn)題 多機(jī)調(diào)度問(wèn)題要求給出一種作業(yè)調(diào)度方案4.7多機(jī)調(diào)度問(wèn)題

采用最長(zhǎng)處理時(shí)間作業(yè)優(yōu)先的貪心選擇策略可以設(shè)計(jì)出解多機(jī)調(diào)度問(wèn)題的較好的近似算法。 按此策略，當(dāng)時(shí)，只要將機(jī)器i的[0,ti]時(shí)間區(qū)間分配給作業(yè)i即可，算法只需要O(1)時(shí)間。 當(dāng)時(shí)，首先將n個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機(jī)。算法所需的計(jì)算時(shí)間為O(nlogn)。524.7多機(jī)調(diào)度問(wèn)題 采用最長(zhǎng)處理時(shí)間作業(yè)優(yōu)先的貪心選擇策4.7多機(jī)調(diào)度問(wèn)題

例如，設(shè)7個(gè)獨(dú)立作業(yè){1,2,3,4,5,6,7}由3臺(tái)機(jī)器M1，M2和M3加工處理。各作業(yè)所需的處理時(shí)間分別為{2,14,4,16,6,5,3}。按算法greedy產(chǎn)生的作業(yè)調(diào)度如下圖所示，所需的加工時(shí)間為17。

534.7多機(jī)調(diào)度問(wèn)題 例如，設(shè)7個(gè)獨(dú)立作業(yè){1,2,3,454練習(xí)1：裝箱問(wèn)題

設(shè)有編號(hào)為0,1,…,n-1的n種物品，體積分別為V0,V1,…,Vn-1。將這n種物品裝到容量都為V的若干箱子里。約定這n種物品的體積均不超過(guò)V，要求使裝進(jìn)這n種物品的箱子數(shù)要少。

對(duì)適當(dāng)大的n，找出所有可能的劃分要花費(fèi)的時(shí)間是無(wú)法承受的。為此，對(duì)裝箱問(wèn)題采用非常簡(jiǎn)單的近似算法，即貪心法。該算法依次將物品放到它第一個(gè)能放進(jìn)去的箱子中，該算法雖不能保證找到最優(yōu)解，但還是能找到非常好的解。

設(shè)有6種物品，它們的體積分別為：60,45,35,20,20,20單位體積，箱子的容量為100單位體積。按上述算法計(jì)算，需三只箱子，各箱子所裝物品分別為：1,3、2,4,5、6，而最優(yōu)解為兩只箱子。54練習(xí)1：裝箱問(wèn)題設(shè)有編號(hào)為0,1,…,n55算法：{輸入箱子的容積;

輸入物品種數(shù)n;

按體積從大到小順序，輸入各品種的體積;

預(yù)置已用箱子鏈為空;for(i=0;i<n;i++){從已用的第一只箱子開(kāi)始順序?qū)ふ夷芊湃胛锲返南渥觠;if(已用箱子都不能再放物品i){另用一只箱子,并將物品i放入該箱子;boxcount++;}else將物品i放入箱子j;}}55算法：{輸入箱子的容積;56練習(xí)2:刪數(shù)問(wèn)題鍵盤(pán)輸入一個(gè)正整數(shù)N，去掉其中任意S個(gè)數(shù)字后剩下的數(shù)字按左右次序組成一個(gè)新的正整數(shù)。對(duì)給定的N和S，尋找一種刪數(shù)規(guī)則使得剩下的數(shù)字組成的新數(shù)最小。56練習(xí)2:刪數(shù)問(wèn)題鍵盤(pán)輸入一個(gè)正整數(shù)N，去掉其中任意S個(gè)數(shù)57#include"string.h"main(){charn[10];/*鍵盤(pán)輸入的正整數(shù)*/ints;/*要?jiǎng)h除的數(shù)字個(gè)數(shù)*/inti,j,k;printf("inputthenumber:");scanf("%s",n);printf("\ninputthedeletenumber");scanf("%d",&s);for(i=1;i<=s;i++){for(j=0;j<strlen(n);j++){if(){for(k=j;k<strlen(n);k++)n[k]=n[k+1];

;break;}}}printf("theresultis%s",n);}n[j]>n[j+1]n[k]='\0'57#include"string.h"{n[j]第4章貪心算法58第4章貪心算法1學(xué)習(xí)要點(diǎn)理解貪心算法的概念。掌握貪心算法的基本要素（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）貪心選擇性質(zhì)理解貪心算法與動(dòng)態(tài)規(guī)劃算法的差異理解貪心算法的一般理論通過(guò)應(yīng)用范例學(xué)習(xí)貪心設(shè)計(jì)策略。（1）活動(dòng)安排問(wèn)題；（2）最優(yōu)裝載問(wèn)題；（3）哈夫曼編碼；（4）單源最短路徑；（5）最小生成樹(shù)；（6）多機(jī)調(diào)度問(wèn)題。59學(xué)習(xí)要點(diǎn)260一、貪心算法定義指的是從對(duì)問(wèn)題的某一初始解出發(fā),一步一步的攀登給定的目標(biāo),盡可能快地去逼近更好的解。當(dāng)達(dá)到某一步,不能再攀登時(shí),算法便終止。二、貪心算法特點(diǎn)貪心算法總是做出在當(dāng)前看來(lái)是最好的選擇,它并不是從總體最優(yōu)上加以考慮,他所作出的選擇只是在某種意義上的局部最優(yōu)選擇。能夠得到的解不一定是最優(yōu)解。概述3一、貪心算法定義指的是從對(duì)問(wèn)題的某一初始解出發(fā),舉例：假設(shè)有四種硬幣25分、10分、5分、1分若干個(gè)。要湊夠63分，應(yīng)該怎樣取硬幣使得硬幣個(gè)數(shù)最少？描述問(wèn)題：數(shù)組a[4]存放所取四種硬幣的個(gè)數(shù),w[4]存放四種硬幣幣值約束條件可行解目標(biāo)函數(shù)61如果把硬幣換為：一分、五分、一角一分，而找給顧客的是一角五分舉例：假設(shè)有四種硬幣25分、10分、5分、1分若干個(gè)。要湊夠62背包問(wèn)題:共有n種物品要裝入一個(gè)背包中，背包可容納的重量是C，每種物品的容量為wi，每個(gè)物品的價(jià)值為Vi，如何裝才能獲得最大的價(jià)值？用一個(gè)向量（x1,x2,x3,…,xn）,表示裝的個(gè)數(shù)多少？約束條件：0<=xi<=1

目標(biāo)函數(shù)：5背包問(wèn)題:共有n種物品要裝入一個(gè)背包中，背包可容納的重量是63假設(shè)n=3，C=20，(v1、v2、v3)=(25、24、15)(w1、w2、w3)=(18、15、10)求6假設(shè)n=3，C=20，(v1、v2、v3)=(25、2顧名思義，貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問(wèn)題，最小生成樹(shù)問(wèn)題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。64顧名思義，貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心4.1活動(dòng)安排問(wèn)題

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

活動(dòng)安排問(wèn)題就是要在4.1活動(dòng)安排問(wèn)題66設(shè)有n個(gè)活動(dòng)的集合E={1,2,…,n}，其中每個(gè)活動(dòng)都要求使用同一資源，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間fi,且si<fi。如果選擇了活動(dòng)i，則它在半開(kāi)時(shí)間區(qū)間[si,fi)內(nèi)占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動(dòng)i與活動(dòng)j是相容的。也就是說(shuō)，當(dāng)si≥fj或sj≥fi時(shí)，活動(dòng)i與活動(dòng)j相容。4.1活動(dòng)安排問(wèn)題9設(shè)有n個(gè)活動(dòng)的集合E={1,24.1活動(dòng)安排問(wèn)題template<classType>voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}67下面給出解活動(dòng)安排問(wèn)題的貪心算法GreedySelector:各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組s和f中且按結(jié)束時(shí)間的非減序排列

4.1活動(dòng)安排問(wèn)題template<classType>4.1活動(dòng)安排問(wèn)題

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

算法greedySelector的效率極高。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需O(n)的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。如果所給出的活動(dòng)未按非減序排列，可以用O(nlogn)的時(shí)間重排。684.1活動(dòng)安排問(wèn)題 由于輸入的活動(dòng)以其完成時(shí)間的4.1活動(dòng)安排問(wèn)題

例：設(shè)待安排的11個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：694.1活動(dòng)安排問(wèn)題例：設(shè)待安排的11個(gè)活動(dòng)的開(kāi)始時(shí)間和4.1活動(dòng)安排問(wèn)題

算法greedySelector的計(jì)算過(guò)程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長(zhǎng)條表示的活動(dòng)是已選入集合A的活動(dòng)，而空白長(zhǎng)條表示的活動(dòng)是當(dāng)前正在檢查相容性的活動(dòng)。704.1活動(dòng)安排問(wèn)題

算法greedySelector4.1活動(dòng)安排問(wèn)題

若被檢查的活動(dòng)i的開(kāi)始時(shí)間Si小于最近選擇的活動(dòng)j的結(jié)束時(shí)間fi，則不選擇活動(dòng)i，否則選擇活動(dòng)i加入集合A中。

貪心算法并不總能求得問(wèn)題的整體最優(yōu)解。但對(duì)于活動(dòng)安排問(wèn)題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動(dòng)集合A的規(guī)模最大。這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明。714.1活動(dòng)安排問(wèn)題若被檢查的活動(dòng)i的開(kāi)4.2貪心算法的基本要素

本節(jié)著重討論可以用貪心算法求解的問(wèn)題的一般特征。 對(duì)于一個(gè)具體的問(wèn)題，怎么知道是否可用貪心算法解此問(wèn)題，以及能否得到問(wèn)題的最優(yōu)解呢?這個(gè)問(wèn)題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問(wèn)題中看到這類(lèi)問(wèn)題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。

724.2貪心算法的基本要素 本節(jié)著重討論可以用貪心算4.2貪心算法的基本要素1、貪心選擇性質(zhì)73

所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問(wèn)題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。

對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。4.2貪心算法的基本要素1、貪心選擇性質(zhì)16所謂貪4.2貪心算法的基本要素

當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(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)鍵特征。

742、最優(yōu)子結(jié)構(gòu)性質(zhì)4.2貪心算法的基本要素 當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子4.2貪心算法的基本要素

貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類(lèi)算法的一個(gè)共同點(diǎn)。但是，對(duì)于具有最優(yōu)子結(jié)構(gòu)的問(wèn)題應(yīng)該選用貪心算法還是動(dòng)態(tài)規(guī)劃算法求解?是否能用動(dòng)態(tài)規(guī)劃算法求解的問(wèn)題也能用貪心算法求解?下面研究2個(gè)經(jīng)典的組合優(yōu)化問(wèn)題，并以此說(shuō)明貪心算法與動(dòng)態(tài)規(guī)劃算法的主要差別。753、貪心算法與動(dòng)態(tài)規(guī)劃算法的差異4.2貪心算法的基本要素 貪心算法和動(dòng)態(tài)規(guī)劃算法都要求4.2貪心算法的基本要素0-1背包問(wèn)題：

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

在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。4.2貪心算法的基本要素0-1背包問(wèn)題：19在選4.2貪心算法的基本要素背包問(wèn)題：

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

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

4.2貪心算法的基本要素背包問(wèn)題：20這2類(lèi)問(wèn)題都4.2貪心算法的基本要素

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

78用貪心算法解背包問(wèn)題的基本步驟：4.2貪心算法的基本要素首先計(jì)算每種物品單位重量4.2貪心算法的基本要素voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);inti;for(i=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}79

算法knapsack的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排序。因此，算法的計(jì)算時(shí)間上界為O（nlogn）。為了證明算法的正確性，還必須證明背包問(wèn)題具有貪心選擇性質(zhì)。4.2貪心算法的基本要素voidKnapsack(int4.2貪心算法的基本要素

對(duì)于0-1背包問(wèn)題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無(wú)法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮0-1背包問(wèn)題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問(wèn)題。這正是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。 實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解0-1背包問(wèn)題。804.2貪心算法的基本要素 對(duì)于0-1背包問(wèn)題，貪心選擇4.3最優(yōu)裝載

有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問(wèn)題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。814.3最優(yōu)裝載有一批集裝箱要裝上一艘載重量為c的對(duì)最優(yōu)裝載問(wèn)題進(jìn)行形式化描述82用一個(gè)向量（x1,x2,x3,…,xn）,表示裝的個(gè)數(shù)多少？約束條件：xi

∈{0,1}目標(biāo)函數(shù)：對(duì)最優(yōu)裝載問(wèn)題進(jìn)行形式化描述25用一個(gè)向量（x1,x2,x3831、算法描述最優(yōu)裝載問(wèn)題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略可產(chǎn)生最優(yōu)裝載問(wèn)題的最優(yōu)解。

261、算法描述4.3最優(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]];}}844.3最優(yōu)裝載template<classType>274.3最優(yōu)裝載2、貪心選擇性質(zhì) 可以證明最優(yōu)裝載問(wèn)題具有貪心選擇性質(zhì)。3、最優(yōu)子結(jié)構(gòu)性質(zhì) 最優(yōu)裝載問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 由最優(yōu)裝載問(wèn)題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法loading的正確性。 算法loading的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法所需的計(jì)算時(shí)間為O(nlogn)。

854.3最優(yōu)裝載2、貪心選擇性質(zhì)284.4哈夫曼編碼

哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來(lái)建立一個(gè)用0，1串表示各字符的最優(yōu)表示方式。 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長(zhǎng)的編碼，可以大大縮短總碼長(zhǎng)。1、前綴碼 對(duì)每一個(gè)字符規(guī)定一個(gè)0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。864.4哈夫曼編碼 哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十4.4哈夫曼編碼 編碼的前綴性質(zhì)可以使譯碼方法非常簡(jiǎn)單。 表示最優(yōu)前綴碼的二叉樹(shù)總是一棵完全二叉樹(shù)，即樹(shù)中任一結(jié)點(diǎn)都有2個(gè)兒子結(jié)點(diǎn)。

平均碼長(zhǎng)定義為： 使平均碼長(zhǎng)達(dá)到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。87

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

884.4哈夫曼編碼2、構(gòu)造哈夫曼編碼314.4哈夫曼編碼 在書(shū)上給出的算法huffmanTree中，編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊(duì)列Q用在貪心選擇時(shí)有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹(shù)。一旦2棵具有最小頻率的樹(shù)合并后，產(chǎn)生一棵新的樹(shù)，其頻率為合并的2棵樹(shù)的頻率之和，并將新樹(shù)插入優(yōu)先隊(duì)列Q。經(jīng)過(guò)n－1次的合并后，優(yōu)先隊(duì)列中只剩下一棵樹(shù)，即所要求的樹(shù)T。 算法huffmanTree用最小堆實(shí)現(xiàn)優(yōu)先隊(duì)列Q。初始化優(yōu)先隊(duì)列需要O(n)計(jì)算時(shí)間，由于最小堆的removeMin和put運(yùn)算均需O(logn)時(shí)間，n－1次的合并總共需要O(nlogn)計(jì)算時(shí)間。因此，關(guān)于n個(gè)字符的哈夫曼算法的計(jì)算時(shí)間為O(nlogn)。894.4哈夫曼編碼 在書(shū)上給出的算法huffmanTr4.4哈夫曼編碼3、哈夫曼算法的正確性 要證明哈夫曼算法的正確性，只要證明最優(yōu)前綴碼問(wèn)題具有貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 (1)貪心選擇性質(zhì) (2)最優(yōu)子結(jié)構(gòu)性質(zhì)904.4哈夫曼編碼3、哈夫曼算法的正確性334.5單源最短路徑

給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源。現(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問(wèn)題通常稱為單源最短路徑問(wèn)題。

1、算法基本思想 Dijkstra算法是解單源最短路徑問(wèn)題的貪心算法。914.5單源最短路徑 給定帶權(quán)有向圖G=(V,E)，其中4.5單源最短路徑

基本思想:設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。 初始時(shí)，S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長(zhǎng)度。924.5單源最短路徑 基本思想:設(shè)置頂點(diǎn)集合S并不斷地作貪問(wèn)題描述:93輸入帶權(quán)有向圖G=(V，E)，V={1，2，…，n}，頂點(diǎn)V1是源C[i][j]表示邊(i,j)的權(quán)dist[i]表示從源到頂點(diǎn)vi的最短特殊路徑長(zhǎng)度prev[i]表示從源到頂點(diǎn)i的最短路徑上,結(jié)點(diǎn)i的前一個(gè)頂點(diǎn)。輸入?yún)?shù)：n,v1,c[i][j]輸出參數(shù)：dist[i],prev[i]問(wèn)題描述:36輸入帶權(quán)有向圖G=(V，E)，V={1，2，算法描述：94基本思想：設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。S[i]—源點(diǎn)到i頂點(diǎn)的最短路徑是否找到初始化：for(i=1;i<=n;i++){s[i]=0;dist[i]=c[v1][i];}S[v1]=1,dist[v1]=0;每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，并將u添加到S中for(num=2;num<=n;num++){從dist[2]到dist[n]選取一頂點(diǎn)u且滿足s[u]=0,使dist[u]=min{dist[2],dist[3],…,dist[n]};s[u]=1;}算法描述：37基本思想：設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)95Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，將u添加到S中后，同時(shí)對(duì)數(shù)組dist作必要的修改。for(j=1;j<=n;j++){if(s[j]==0&&c[u][j]<maxint){newdist=dist[u]+c[u][j];if(newdist<dist[j]){dist[j]=newdist;prev[j]=u;}}}整個(gè)過(guò)程執(zhí)行n-1次38Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度4.5單源最短路徑

例如，對(duì)右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑的過(guò)程列在下頁(yè)的表中。964.5單源最短路徑例如，對(duì)右圖中的有向圖，應(yīng)用Dij4.5單源最短路徑97Dijkstra算法的迭代過(guò)程：

4.5單源最短路徑40Dijkstra算法的迭代過(guò)程：4.5單源最短路徑2、算法的正確性和計(jì)算復(fù)雜性(1)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)(3)計(jì)算復(fù)雜性 對(duì)于具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么Dijkstra算法的主循環(huán)體需要時(shí)間。這個(gè)循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要時(shí)間。算法的其余部分所需要時(shí)間不超過(guò)。984.5單源最短路徑2、算法的正確性和計(jì)算復(fù)雜性414.6最小生成樹(shù)

設(shè)G=(V,E)是無(wú)向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為c[v][w]。如果G的子圖G’是一棵包含G的所有頂點(diǎn)的樹(shù)，則稱G’為G的生成樹(shù)。生成樹(shù)上各邊權(quán)的總和稱為該生成樹(shù)的耗費(fèi)。在G的所有生成樹(shù)中，耗費(fèi)最小的生成樹(shù)稱為G的最小生成樹(shù)。 網(wǎng)絡(luò)的最小生成樹(shù)在實(shí)際中有廣泛應(yīng)用。例如，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通信線路所需的費(fèi)用，則最小生成樹(shù)就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。994.6最小生成樹(shù) 設(shè)G=(V,E)是無(wú)向連通帶權(quán)圖，4.6最小生成樹(shù)1、最小生成樹(shù)性質(zhì) 用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹(shù)的有效算法。本節(jié)介紹的構(gòu)造最小生成樹(shù)的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的例子。盡管這2個(gè)算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹(shù)性質(zhì)： 設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有這樣的邊中，(u,v)的權(quán)c[u][v]最小，那么一定存在G的一棵最小生成樹(shù)，它以(u,v)為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱為MST性質(zhì)。

1004.6最小生成樹(shù)1、最小生成樹(shù)性質(zhì)434.6最小生成樹(shù)2、Prim算法

設(shè)G=(V,E)是連通帶權(quán)圖，V={1,2,…,n}。 構(gòu)造G的最小生成樹(shù)的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，jV-S，且c[i][j]最小的邊，將頂點(diǎn)j添加到S中。這個(gè)過(guò)程一直進(jìn)行到S=V時(shí)為止。 在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹(shù)。1014.6最小生成樹(shù)2、Prim算法444.6最小生成樹(shù) 利用最小生成樹(shù)性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的邊集合T始終包含G的某棵最小生成樹(shù)中的邊。因此，在算法結(jié)束時(shí)，T中的所有邊構(gòu)成G的一棵最小生成樹(shù)。

例如，對(duì)于右圖中的帶權(quán)圖，按Prim算法選取邊的過(guò)程如下頁(yè)圖所示。102 利用最小生成樹(shù)性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的邊集合T始終包含G的某棵最小生成樹(shù)中的邊。因此，在算法結(jié)束時(shí)，T中的所有邊構(gòu)成G的一棵最小生成樹(shù)。

例如，對(duì)于右圖中的帶權(quán)圖，按Prim算法選取邊的過(guò)程如下頁(yè)圖所示。4.6最小生成樹(shù) 利用最小生成樹(shù)性質(zhì)和數(shù)學(xué)歸納法容易證明4.6最小生成樹(shù)1034.6最小生成樹(shù)464.6最小生成樹(shù) 在上述Prim算法中，還應(yīng)當(dāng)考慮如何有效地找出滿足條件iS,jV-S，且權(quán)c[i][j]最小的邊(i,j)。實(shí)現(xiàn)這個(gè)目的的較簡(jiǎn)單的辦法是設(shè)置2個(gè)數(shù)組closest和lowcost。 在Prim算法執(zhí)行過(guò)程中，先找出V-S中使lowcost值最小的頂點(diǎn)j，然后根據(jù)數(shù)組closest選取邊(j,closest[j］)，最后將j添加到S中，并對(duì)closest和lowcost作必要的修改。 用這個(gè)辦法實(shí)現(xiàn)的Prim算法所需的計(jì)算時(shí)間為1044.6最小生成樹(shù) 在上述Prim算法中，還應(yīng)當(dāng)考慮如何有4.6最小生成樹(shù)3、Kruskal算法

Kruskal算法構(gòu)造G的最小生成樹(shù)的基本思想是，首先將G的n個(gè)頂點(diǎn)看成n個(gè)孤立的連通分支。將所有的邊按權(quán)從小到大排序。然后從第一條邊開(kāi)始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接2個(gè)不同的連通分支：當(dāng)查看到第k