第4章貪心算法

2023/2/3計算機算法設(shè)計與分析1第四章

貪心算法2學(xué)習(xí)要點理解貪心算法的概念。掌握貪心算法的基本要素：

（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）貪心選擇性質(zhì)理解貪心算法的一般理論通過應(yīng)用范例學(xué)習(xí)貪心設(shè)計策略。（1）最小生成樹；（2）單源最短路徑；（3）旅行商問題；（4）活動安排問題；（5）最優(yōu)裝載問題；2023/2/3計算機算法設(shè)計與分析3找硬幣假設(shè)有四種硬幣，面值分別為二角五分一角五分一分現(xiàn)在要找給某顧客六角三分錢，哪種找錢方法拿出的硬幣個數(shù)最少呢？二角五分二角五分一角一分一分一分

首先選出一個面值不超過六角三分的最大硬幣，即二角五分；然后從六角三分中減去二角五分，剩下三角八分；再選出一個面值不超過三角八分的最大硬幣，即又一個二角五分，如此一直做下去。這種方法實際上就是貪心算法。2023/2/3計算機算法設(shè)計與分析4再找硬幣若硬幣的面值改為一分、五分和一角一分3種，而要找給顧客的是一角五分錢。還用貪心算法，將找個顧客1個一角一分的硬幣和4個一分的硬幣。然而，3個五分的硬幣顯然才是最好的找法。2023/2/3計算機算法設(shè)計與分析5貪心算法的適用情形設(shè)待求解問題有N個輸入，根據(jù)必須滿足的條件和目標(biāo)函數(shù)，希望從問題的所有允許解中求出最優(yōu)值。2023/2/3計算機算法設(shè)計與分析6貪心算法的特點貪心算法總是作出在當(dāng)前來看是最好的選擇。就是說，貪心算法并不從整體最優(yōu)上來考慮，所作出的選擇只是某種意義上的局部最優(yōu)選擇。貪心法在解決問題的策略上目光短淺，只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個選擇都不會改變。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解，但通常能獲得近似最優(yōu)解。2023/2/3計算機算法設(shè)計與分析7貪心算法的一般框架GreedyAlgorithm(parameters){初始化；重復(fù)執(zhí)行以下的操作：選擇當(dāng)前可以選擇的(相容)最優(yōu)解；將所選擇的當(dāng)前解加入到問題的解中；直至滿足問題求解的結(jié)束條件。}2023年2月3日8煤氣管道的鋪設(shè)

某新建小區(qū)著手鋪設(shè)煤氣管道，已知每一幢樓的接入位置和距離，請求出最短的鋪設(shè)方案。2023年2月3日9學(xué)校有n臺計算機，為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來。兩臺計算機被連接是指它們之間有數(shù)據(jù)線連接。由于計算機所處的位置不同，因此不同的兩臺計算機的連接費用往往是不同的。最優(yōu)布線問題最優(yōu)通信網(wǎng)若要在n個城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條線路即可。如何以最低的經(jīng)濟代價建設(shè)這個通信網(wǎng)，是一個網(wǎng)的最小生成樹問題。2023年2月3日102023/2/3計算機算法設(shè)計與分析11最小生成樹設(shè)G=(V,E)是一個無向連通帶權(quán)圖，即一個網(wǎng)絡(luò)。E的每條邊(v,w)的權(quán)為c[v][w]。如果G的一個子圖G’是一棵包含G的所有頂點的樹，則稱G’為G的生成樹。生成樹的各邊的權(quán)的總和稱為該生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小(優(yōu))生成樹。

2023/2/3計算機算法設(shè)計與分析12樹的基本性質(zhì)連通無回路的圖G稱為樹。樹是點比邊多一的連通圖，G連通且q=p–1

。樹是點比邊多一的無回路圖：G無回路且q=p–1樹若添條邊就有回路：G無回路，但對任意的u,v∈V(G)，若uvE(G)，則G+uv中恰有一條回路樹若減條邊就不連通：G連通，但對e∈E(G),G–e不連通。n個頂點的連通圖的生成樹含有n–1條邊。2023年2月3日13實例BCAED706080509075300200BCAED705090300BCAED708050300BCAED70608050若G的任何最小生成樹都不包含e1。設(shè)T為G的最小生成樹，e1T。于是T+e1是一個有回路的圖且該回路中包含e1。該回路中必有條不是e1的邊ei。令T’={T+e1}–ei。T’也是G的生成樹。又c(T’)=c(T)+c(e1)–c(ei)，c(e1)≤c(ei)，從而c(T’)≤c(T)，T’是G的最小生成樹且含有邊e1。矛盾。故必定有圖G的最小生成樹包含了e1。2023/2/3計算機算法設(shè)計與分析14最小生成樹的貪心選擇性質(zhì)令G中權(quán)最小的邊為e1。首先必定有圖G的一棵最小生成樹包含了e1。選定第一條邊e1以后，該如何選擇第二條邊呢？依據(jù)各條邊的權(quán)重，依次選出權(quán)重較輕的n–1條邊。這n–1條邊必定包括了G的n個頂點。這樣就得到了G的一棵最小生成樹。這樣做是否可以呢？不行！因為不能保證這n–1條邊構(gòu)成樹？要保證這n–1條邊構(gòu)成樹，必須使這n–1條邊是連通的或者是無回路的。Prim算法的做法：在保證連通的前提下依次選出權(quán)重較小的n–1條邊（在實現(xiàn)中體現(xiàn)為n個頂點的選擇）。Kruskal算法的做法：在保證無回路的前提下依次選擇權(quán)重較小的n–1條邊。2023/2/3計算機算法設(shè)計與分析15Prim算法基本思想：在保證連通的前提下依次選出權(quán)重較小的n–1條邊。G=(V,E)為無向連通帶權(quán)圖，令V={1,2,…,n}。設(shè)置一個集合S，初始化S={1}，T=Φ。貪心策略：如果V–S中的頂點j與S中的某個點i連接且(i,j)的權(quán)重最小，于是就選擇j(將j加入S)，并將(i,j)加入T中。重復(fù)執(zhí)行貪心策略，直至V–S為空。2023/2/3計算機算法設(shè)計與分析16Prim算法的示例給定一個連通帶權(quán)圖如下：1234561655536624初始時S={1}，T=Φ；1第一次選擇：∵(1,3)權(quán)最小∴S={1,3}T={(1,3)}

；3第二次選擇：∵(3,6)權(quán)最小∴S={1,3,6}，

T={(1,3),(3,6)}

；6第三次選擇：∵(6,4)權(quán)最小∴S={1,3,6,4}，

T={(1,3),(3,6),(6,4)}

；4第四次選擇：∵(2,3)權(quán)最小∴S={1,3,6,4,2}，

T={(1,3),(3,6),(6,4),(2,3)}

；2第五次選擇：∵(5,2)權(quán)最小∴S={1,3,6,4,2,5}，

T={(1,3),(3,6),(6,4),(3,2)(2,5)}

；52023/2/3計算機算法設(shè)計與分析17Prim算法中的數(shù)據(jù)結(jié)構(gòu)圖用連接矩陣C[i][j]給出，即C[i][j]為結(jié)點i到結(jié)點j的權(quán)重。標(biāo)志數(shù)組S[i]指示頂點i是否已經(jīng)加入到S中。為了有效地找出V–S中滿足與S中的某個點i連接且(i,j)權(quán)重最小的頂點j，對其中的每個頂點j設(shè)立兩個數(shù)組closest[j]和lowcost[j]：closest[j]是S中與j最近的頂點，(closest[j],j)即為選中的邊，而lowcost[j]是相應(yīng)邊的權(quán)重。關(guān)鍵點：如何有效地找出滿足條件iS,jV-S，且權(quán)c[i][j]最小的邊(i,j)？2023/2/3計算機算法設(shè)計與分析18Prim算法的實現(xiàn)Prim(intn,Type**c){

初始化：結(jié)點1放入S；并初始化lowcost[]和

closest[]；

執(zhí)行以下操作n–1次：依據(jù)lowcost[]找出與S最近的點j并放入S；

調(diào)整lowcost[]和closest[]；}intj=1;s[j]=true;for(inti=2;i<=n;i++){closest[i]=1;lowcost[i]=c[1][i];s[i]=false;}for(i=1;i<n;i++){min=inf;for(intk=2;k<=n;k++){if(lowcost[k]<min&&!s[k]){min=lowcost[k];j=k}s[j]=true;s中僅加入了一個新成員j，因此只需要依據(jù)結(jié)點j調(diào)整lowcost[]和closest[]；for(k=2;k<=n;k++){if(c[j][k]<lowcost[k]&&!s[k]){lowcost[k]=c[j][k];closest[k]=j}}}2023/2/3計算機算法設(shè)計與分析19Kruskal算法基本思想：在保證無回路的前提下依次選出權(quán)重較小的n–1條邊。貪心策略：如果(i,j)是E中尚未被選中的邊中權(quán)重最小的，并且(i,j)不會與已經(jīng)選擇的邊構(gòu)成回路，于是就選擇(i,j)。問題：如何知道(i,j)不會造成回路？若邊(i,j)的兩個端點i和j屬于同一個連通分支，則選擇(i,j)會造成回路，反之則不會造成回路因此初始時將圖的n個頂點看成n個孤立分支。2023/2/3計算機算法設(shè)計與分析20Kruskal算法的例子1234561655536624131462253364145235345126356566初始時為6個孤立點123456選擇了邊1，于是1、3點合并為同一個集合。√選擇了邊2，于是4、6點合并為同一個集合?！踢x擇了邊3，于是2、5點合并為同一個集合?！踢x擇了邊4，于是1、3、4、6點合并為同一個集合√考察邊5，因為1、4點屬于同一個集合，被放棄?！吝x擇邊6，于是1、3、4、6、2、5點屬于同一個集合。√已經(jīng)選擇邊了n–1條邊，算法結(jié)束。結(jié)果如圖所示。uvw2023/2/3計算機算法設(shè)計與分析21Kruskal算法的數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)數(shù)組e[]表示圖的邊，e[i].u、e[i].v和e[i].w分別表示邊i的兩個端點及其權(quán)重。函數(shù)Sort(e,w)將數(shù)組e按權(quán)重w從小到大排序。一個連通分支中的頂點表示為一個集合。函數(shù)Initialize(n)將每個頂點初始化為一個集合函數(shù)Find(u)給出頂點u所在的集合。函數(shù)Union(a,b)給出集合a和集合b的并集。重載算符!=判斷集合的不相等。2023/2/3計算機算法設(shè)計與分析22Kruskal算法的實現(xiàn)Kruskal(intn,*e){Sort(e,w);//將邊按權(quán)重從小到大排序

initialize(n);//初始時每個頂點為一個集合

k=1;//k累計已選邊的數(shù)目，

j=1;//j為所選的邊在e中的序號

while(k<n)//選擇n–1條邊

{a=Find(e[j].u);b=Find(e[j].v);//找出第j條邊兩個端點所在的集合

if(a!=b){T[k]=j;Union(a,b);k=k+1;}//若不同，第j條邊放入樹中并合并這兩個集合

j++}}//繼續(xù)考察下一條邊2023/2/3計算機算法設(shè)計與分析23Prim與Kruskal兩算法的復(fù)雜性Prim算法為兩重循環(huán)，外層循環(huán)為n次，內(nèi)層循環(huán)為O(n)，因此其復(fù)雜性為O(n2)。Kruskal算法中，設(shè)邊數(shù)為e，則邊排序的時間為O(eloge)，最多對e條邊各掃描一次，每次確定邊的時間為O(loge)，所以整個時間復(fù)雜性為O(eloge)。當(dāng)e=Ω(n2)時，Kruskal算法要比Prim算法差；當(dāng)e=ο(n2)時，Kruskal算法比Prim算法好得多。2023/2/3計算機算法設(shè)計與分析24貪心算法也能獲得最優(yōu)解用Kruskal算法得到的生成樹T*必是最優(yōu)樹。證明：設(shè)T*不是最優(yōu)，令T是與T*有k條共同邊的最優(yōu)樹且k是最優(yōu)樹與T*共有邊數(shù)的最大值∵

T≠T*∴

ek+1:ek+1E(T)且ek+1∈E(T*)。則T+ek+1含唯一回路C，C必有條邊ek’E(T*)。令T’=(T+ek+1)–ek’,w(T’)=w(T)+w(ek+1)–w(ek’)。由算法知，w(ek+1)w(ek’)，∴

T’是最優(yōu)樹。但T’與T*有k+1條共同邊，矛盾。故T*是最優(yōu)2023/2/3計算機算法設(shè)計與分析250-1背包問題給定n個物品和一個背包。物品i的重量為wi，價值為vi，背包容量為c。問如何選擇裝入背包中的物品，使得裝入背包的物品的價值最大？在裝入背包時，每種物品i只有兩種選擇，裝入或者不裝入，既不能裝入多次，也不能只裝入一部分。因此，此問題稱為0-1背包問題。如果在裝入背包時，物品可以切割，即可以只裝入一部分，這種情況下的問題稱為背包問題。2023/2/3計算機算法設(shè)計與分析260-1背包問題不適用貪心算法背包容量為50kg，物品1,2和3的容量和價值分別為(10kg,$60),(20kg,$100)和(30kg,$120)。單位重量價值最高的為物品1，6$/kg。但是依照貪心算法首選物品1卻不能獲得最優(yōu)解：物品1物品2物品1物品3物品2物品3總價值為$160,空余20kg總價值為$180,空余10kg總價值為$220,沒有空余但是背包問題卻是適用貪心算法的。2023/2/3計算機算法設(shè)計與分析27貪心算法的基本要素貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)解的選擇，即貪心選擇來達(dá)到。貪心選擇每次選取當(dāng)前最優(yōu)解，因此它依賴以往的選擇，而不依賴于將來的選擇。貪心算法通常以自頂向下的方式進(jìn)行，每次貪心選擇就將原問題轉(zhuǎn)化為規(guī)模更小的子問題。最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。2023/2/3計算機算法設(shè)計與分析28如何確定貪心選擇性質(zhì)證明貪心選擇將導(dǎo)致整體的最優(yōu)解：首先證明存在問題的一個整體最優(yōu)解必定包含了第一個貪心選擇。然后證明在做了貪心選擇后，原問題簡化為規(guī)模較小的類似子問題，即可繼續(xù)使用貪心選擇。于是用數(shù)學(xué)歸納法可證明，經(jīng)過一系列貪心選擇可以得到整體最優(yōu)解。2023/2/3計算機算法設(shè)計與分析29單源最短路徑給定一個圖G=(V,E)，其中每條邊的權(quán)是一個非負(fù)實數(shù)。另外給定V中的一個頂點v，稱為源。求從源v到所有其它各個頂點的最短路徑。單源最短路徑問題的貪心選擇策略：選擇從源v出發(fā)目前用最短的路徑所到達(dá)的頂點，這就是目前的局部最優(yōu)解。12543102050100301060賦權(quán)圖G2023/2/3計算機算法設(shè)計與分析30單源最短路徑的貪心算法基本思想：首先設(shè)置一個集合S；用數(shù)組dis[]來記錄v到S中各點的目前最短路徑長度。然后不斷地用貪心選擇來擴充這個集合，并同時記錄或修訂數(shù)組dis[]；直至S包含所有V中頂點。貪心選擇：一個頂點u屬于S當(dāng)且僅當(dāng)從v到u的最短路徑長度已知。初始化：S中僅含有源v。2023/2/3計算機算法設(shè)計與分析31Dijkstra算法Dijkstra算法的做法是：由近到遠(yuǎn)逐步計算，每次最近的頂點的距離就是它的最短路徑長度。然后再從這個最近者出發(fā)。即依據(jù)最近者修訂到各頂點的距離，然后再選出新的最近者。如此走下去，直到所有頂點都走到。2023/2/3計算機算法設(shè)計與分析32Dijkstra算法ProcedureDijkstra{(1)S:={1};//初始化S(2)fori:=2tondo//初始化dis[](3)dis[i]=C[1,i];//初始時為源到頂點i一步的距離(4)fori:=1tondo{(5)從V-S中選取一個頂點u使得dis[u]最??；(6)將u加入到S中；//將新的最近者加入S(7)forw∈V-Sdo//依據(jù)最近者u修訂dis[w](8)dis[w]:=min(dis[w],dis[u]+C[u,w])}}2023/2/3計算機算法設(shè)計與分析33Dijkstra算法舉例迭代Sudis[2]dis[3]dis[4]dis[5]初始{1}--10

∞301001{1,2}21060

30

1002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060

12543102050100301060賦權(quán)圖G由數(shù)組dis[i]可知：從頂點1到頂點2、3、4、5的最短通路的長度分別為10、50、30和60。2023/2/3計算機算法設(shè)計與分析34Dijkstra算法的貪心選擇性質(zhì)Dijkstra算法中所做的貪心選擇是：若u是V–S中具有最短路徑的特殊頂點，就將u選入S，并確定了從源到u的最短路徑長度dis[u]。為什么從源到u沒有更短的路徑呢？若有，則將如下圖所示：Svdis[u](最近距離)uxdis[x]若該路徑經(jīng)S外一點x到達(dá)u，則：dis[x]+d(x,u)＜dis[u]從而dis[x]＜dis[u]，這與u的選取矛盾2023/2/3計算機算法設(shè)計與分析35Dijkstra算法的計算復(fù)雜性Dijkstra算法有兩層循環(huán)，外層循環(huán)為n次，內(nèi)層有兩個循環(huán)：一個是選出最小的u(第5行)，另一個是修訂dis[w](第7、8行)，內(nèi)層循環(huán)的時間為O(n)。因此Dijkstra算法的時間復(fù)雜度為O(n2)。Dijkstra算法能求出從源到其它各頂點的最短通路的長度，但是卻并沒有給出其最短通路。對Dijkstra算法做適當(dāng)?shù)男薷谋憧汕蟪鲎疃掏贰?023/2/3計算機算法設(shè)計與分析36旅行商問題推銷員從某城市出發(fā)，遍歷n個城市最后返回出發(fā)城市。設(shè)從城市i到城市j的費用為cij，如何選擇旅行路線使得該推銷員此趟旅行的總費用最小?圖論語言表述：給定n個節(jié)點簡單無向完全圖G=<V,E,c>，c(i,j)是節(jié)點i到j(luò)的代價(邊權(quán))。在G中求遍歷所有節(jié)點簡單回路C，使C上所有邊權(quán)的和最小。2023/2/3計算機算法設(shè)計與分析37旅行商問題分析123451∞12752∞4433∞124∞35∞

對于n個節(jié)點的旅行商問題，n個節(jié)點的任意一個圓排列都是問題的一個可能解。n個節(jié)點的圓排列有(n-1)!個，因此問題歸結(jié)為在(n-1)!個回路中選取最小回路。是否能夠不用O((n-1)!)時間來求解旅行商問題？2023/2/3計算機算法設(shè)計與分析38旅行商問題的貪心算法基本思想：首先設(shè)置一個集合Path和當(dāng)前節(jié)點v，然后不斷地用貪心選擇來擴充這個集合，直至Path包含所有V中頂點。貪心選擇：如果V–Path中的頂點j是與當(dāng)前節(jié)點v相鄰接的頂點中邊權(quán)最小的，于是就選擇j(將j加入Path)，并將j作為新的當(dāng)前節(jié)點。初始化：Path中僅含有源v。2023/2/3計算機算法設(shè)計與分析39最臨近算法中的數(shù)據(jù)結(jié)構(gòu)圖用連接矩陣W[i][j]給出，即W[i][j]為結(jié)點i到結(jié)點j的權(quán)重。Path[]記錄依次連接的城市，p記錄當(dāng)前到達(dá)的最后一個頂點，cost為當(dāng)前路徑長度。如果節(jié)點k已經(jīng)到達(dá)，則arrived[k]=true。2023/2/3計算機算法設(shè)計與分析40旅行商問題的最臨近算法CostTypeTray_Greedy(intn,CostType**w,int*path){for(i=1;i<=n;i++)arrived[i]=false;cost=0;//初始化

path[1]=1;p=1;arrived[1]=true;//從節(jié)點1出發(fā)

for(i=2;i<=n;i++){min=inf;for(j=1;j<=n;j++)if(!arrived[j]&&w[p][j]<min){k=j;min=w[p][j]}//搜索最臨近p且尚未到達(dá)過的節(jié)點kcost=cost+w[p][k];path[i]=k;arrived[k]=true;p=k;//將節(jié)點k加入到路徑中

}cost=cost+w[p][1];returncost;//加上回路最后一條邊的權(quán)

}2023/2/3計算機算法設(shè)計與分析41旅行商算法舉例從節(jié)點1出發(fā)：Path=<1,2,5,3,4,1>;cost=14;

因此最臨近法不保證求得旅行商問題的精確解，只能得到問題地近似解。一般地，貪心選擇只依賴于前面選擇步驟地最優(yōu)性，因此是局部最優(yōu)的，所以貪心法不能夠確保求出問題的最優(yōu)解。不難看出，從節(jié)點2出發(fā)：Path=<2,1,3,4,5,2>;cost=10;且此為最優(yōu)解！2023/2/3計算機算法設(shè)計與分析42改進(jìn)的旅行商算法如果分別從節(jié)點i出發(fā)（i=1,2,..n）執(zhí)行算法Tray_Greedy，通過結(jié)果比較，取最小代價回路，可以求得更接近于最佳解的近似解。作業(yè)：對算法Tray_Greedy進(jìn)行修改補充，得到改進(jìn)后的旅行商貪心算法Tray_Greedy1。

2023/2/3計算機算法設(shè)計與分析43Tray_Greedy算法的計算復(fù)雜性Tray_Greedy算法有兩層循環(huán)，外層循環(huán)為n次，內(nèi)層循環(huán)也是n次，因此Tray_Greedy算法的時間復(fù)雜度為O(n2)Tray_Greedy1

算法分別從n個節(jié)點出發(fā)計算最小代價回路，其時間復(fù)雜度為O(n3)2023/2/3計算機算法設(shè)計與分析44活動安排問題設(shè)有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，且在同一時間里只能有一個活動可以使用該資源。現(xiàn)要求給出一個活動安排，使得利用該資源活動為最多。每個活動i都有使用該資源的一個啟始時間si和一個結(jié)束時間fi，si＜fi，其占用資源的時間為半開區(qū)間[si,fi)。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動i與活動j是相容的。

活動安排問題就是求E的最大相容活動子集。

2023/2/3計算機算法設(shè)計與分析45活動安排的例子i1234567891011s[i]650283183512f[i]1096131254118714

貪心法求解活動安排問題的關(guān)鍵是如何選擇貪心策略，使得按照一定的順序選擇相容活動，并能安排盡量多的活動。至少有兩種看似合理的貪心策略：（1）最早開始時間：可以增大資源的利用率。（2）最早結(jié)束時間：可以使下一個活動盡早開始。

由于活動占用資源的時間沒有限制，因此，后一種貪心選擇更為合理。2023/2/3計算機算法設(shè)計與分析46活動安排問題的貪心算法基本思想：某項活動結(jié)束時間愈早，安排其它活動的剩余區(qū)間愈大。所以貪心策略為盡量選擇結(jié)束時間早的活動來安排。為此，將活動按結(jié)束時間的非減順序排序，即f1≤f2≤…≤fn。顯然排序需要的時間為O(nlogn)。貪心選擇：當(dāng)安排下第i個活動后，可能有：fi>si+1，所以第i+1個活動無法安排，這就必須舍棄第i+1個活動，檢測第i+2個活動……直到第i+k個活動的si+k>fi，就把此活動安排進(jìn)來。2023/2/3計算機算法設(shè)計與分析47先將所有活動按照結(jié)束時間f[i]遞增排序活動安排的例子首先選定活動1，其結(jié)束時間f[1]=4。然后因s[4]=5≥4，選定活動4，這時f[4]=7。又因s[8]=8≥7，選定活動8，這時f[8]=11。最后因s[11]=12≥11，選定活動11。最終的活動安排為：1、4、8和11。i1234567891011s[i]130535688212f[i]45678910111213142023年2月3日48活動安排的貪心算法將所有活動按結(jié)束時間排序，得到活動集合E={e1,e2…en}；先將e1選入結(jié)果集合A中，即A={e1}；依次掃描每一個活動ei：

如果ei的開始時間晚于最后一個選入A的活動ej的結(jié)束時間，則將ei選入A中，否則放棄ei；2023/2/3計算機算法設(shè)計與分析49活動安排貪心算法的實現(xiàn)typedefstruct{

int

number;//活動的編號

floatstart;

//活動開始的時間

floatend;

//活動結(jié)束的時間

Boolselected;//標(biāo)記活動是否被選擇

}Active;intgreedySelector(Activeactivity[],intn){QuickSort(activity,n);//將活動按結(jié)束時間排序

activity[1].selected=true;

j=1;count=1;

for(i=2;i<=n;i++)

if(activity[i].start>=activity[j].end){activity[i].selected=true;

j=i;count++;}

else

activity[i].selected=false;

returncount;

}2023年2月3日50算法正確性證明需要證明：活動安排問題有一個最優(yōu)解以貪心選擇開始；活動安排問題具有最優(yōu)子結(jié)構(gòu)；算法每一步按照貪心選擇計算，最終可得到原問題的一個最優(yōu)解。2023/2/3計算機算法設(shè)計與分析51貪心算法能夠得到活動安排問題的最優(yōu)解設(shè)活動集合E={1,2,…,n}已按結(jié)束時間的非減順序排列，活動1具有最早結(jié)束時間。首先必定有最優(yōu)解包含活動1。否則設(shè)A是E的最優(yōu)解，且A中最早結(jié)束的活動是k。若k＞1，則活動1必與A中除k以外的活動相容。令B=A–{k}∪{1}，則B也是最優(yōu)解。進(jìn)一步，假設(shè)A是原問題的包含活動1的最優(yōu)解，則A’=A–{1}是活動集合E’={i∈E且si≥f1}的一個最優(yōu)解。反之，如果能夠找到E’的一個解B’，它包含了比A’更多的活動，則將活動1加入到B’中將產(chǎn)生E的一個解B，它包含比A更多的活動。這與假設(shè)矛盾。因此，所做的每一步貪心選擇都將產(chǎn)生一個比原問題規(guī)模更小的具有相同特征的子問題。由數(shù)學(xué)歸納法可知，貪心法得到的是最優(yōu)解。2023/2/3計算機算法設(shè)計與分析52算法復(fù)雜性分析算法由兩部分組成：第一部分是排序，時間復(fù)雜度為O(nlogn)；第二部分是選擇合適的活動，是一個定長循環(huán)，時間復(fù)雜度為O(n)；故總的時間復(fù)雜度為O(nlogn)。2023/2/3計算機算法設(shè)計與分析53最優(yōu)裝載問題有一批集裝箱要裝上一艘載重為C的輪船。其中集裝箱i的重量為Wi。假定裝載體積不受限制，要將盡可能多(這個多，是指的貨物數(shù)目)的集裝箱裝上輪船。

該問題的形式化描述為：有約束條件

其中，xi=0表示不裝入集裝箱，xi=1反之。2023/2/3計算機算法設(shè)計與分析54最優(yōu)裝載問題的貪心算法基本思想：這個題目比較簡單，可以用貪心法求解。每次采用