算法-貪心算法

第5章貪心算法主要內(nèi)容5.1貪心算法概述5.2貪心算法的理論基礎(chǔ)5.3刪數(shù)字問題5.4背包問題5.5覆蓋問題5.6圖的著色問題5.7遍歷問題5.8最小生成樹5.9哈夫曼編碼其他貪心算法：Dijkstra最短路徑5.1.1貪心算法找零錢問題，希望用數(shù)目最少的硬幣找零假設(shè)提供了數(shù)目不限的面值為25美分、10美分、5美分、及1美分的硬幣。假設(shè)需要找67美分，25+25+10+5+1+1，共6枚。假設(shè)提供了數(shù)目不限的面值為11美分、5美分及1美分的硬幣？找零15美分

11+1+1+1+1，共5枚（貪心算法）

5+5+5，共3枚（非貪心算法）5.1貪心算法概述貪心算法通過一系列的局部選擇來得到一個(gè)問題的解。所作的每一個(gè)選擇都是當(dāng)前狀態(tài)下“最優(yōu)”的選擇。要依照某種策略。策略“只顧眼前，不管將來”，稱之為“貪心策略”。貪心算法沒有固定的算法框架，算法設(shè)計(jì)的關(guān)鍵是貪心策略的選擇貪心算法在求解最優(yōu)化問題時(shí)，從初始階段開始，每一個(gè)階段總是作一個(gè)使局部最優(yōu)的貪心選擇，不斷把將問題轉(zhuǎn)化為規(guī)模更小的子問題。貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。這樣處理，對大多數(shù)優(yōu)化問題來說能得到最優(yōu)解，但也并不總是這樣。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。5.1.2.貪心算法的基本思想

貪心算法的基本思想是通過一系列選擇步驟來構(gòu)造問題的解，每一步都是對當(dāng)前部分解的一個(gè)擴(kuò)展，直至獲得問題的完整解。所做的每一步選擇都必須滿足：

(1)可行的：必須滿足問題的約束。

(2)局部最優(yōu)：當(dāng)前所有可能的選擇中最佳的局部選擇。

(3)不可取消:

選擇一旦做出，在后面的步驟中就無法改變了。貪心算法是通過做一系列的選擇來給出某一問題的最優(yōu)解，對算法的每一個(gè)決策點(diǎn)，做一個(gè)當(dāng)時(shí)（看起來）是最佳的選擇。這種啟發(fā)式策略并不總是能產(chǎn)生出最優(yōu)解。例5.1刪除數(shù)字問題鍵盤輸入一個(gè)高精度的正整數(shù)N，去掉其中任意S個(gè)數(shù)字后剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對給定的N和S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。輸出應(yīng)包括所去掉的數(shù)字的位置和組成的新的正整數(shù)(N不超過100位)。數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：將輸入的高精度數(shù)存儲為字符串格式。實(shí)例(s=3)：n1=“12435863”貪心策略在位數(shù)固定的前提下，讓高位的數(shù)字盡量小其值就較?。粍h除高位較大的數(shù)字；具體地相鄰兩位比較若高位比低位大則刪除高位。n1=“12435863”4比3大刪除4“1235863”8比6大刪除8“123563”6比3大刪除6“12353”再一個(gè)實(shí)例：n2=“231183”3比1大刪除3“21183”2比1大刪除2“1183”8比3大刪除8“113”由實(shí)例1，相鄰數(shù)字只需要從前向后比較；而從實(shí)例2中可以看出當(dāng)?shù)趇位與第i+1位比較，若刪除第i位后，必須向前考慮第i-1位與第i+1位進(jìn)行比較，才能保證結(jié)果的正確性。n3=”1234567”s=3由這個(gè)實(shí)例看出，經(jīng)過對n3相鄰比較一個(gè)數(shù)字都沒有刪除，這就要考慮將后三位進(jìn)行刪除；當(dāng)然還有可能，在相鄰比較的過程中刪除的位數(shù)小于s時(shí)，也要進(jìn)行相似的操作。n4=”120083”s=32比0大刪除2“10083”1比0大刪除1“0083”8比3大刪除8“003”由這個(gè)實(shí)例子又能看出，當(dāng)刪除掉一些數(shù)字后，結(jié)果的高位有可能出現(xiàn)數(shù)字“0”，直接輸出這個(gè)數(shù)據(jù)不合理，要將結(jié)果中高位的數(shù)字“0”刪除掉，再輸出。特別地還要考慮若結(jié)果串是“0000”時(shí)，不能將全部“0”都刪除，而要保留一個(gè)“0”最后輸出。#include"stdio.h"#include"string.h"main(){inti,j,k,m,n,x,a[200];charb[200];gets(b);for(n=0,i=0;b[i]!='\0';i++){n++;a[i]=b[i]-48;}scanf("%d",&k);i=0;m=0;x=0;

while(k>x&&m==0){i=i+1;if(a[i-1]>a[i])/*出現(xiàn)遞增,刪除遞增的首數(shù)字*/{printf("%d",a[i-1]);for(j=i-1;j<=n-x-2;j++)a[j]=a[j+1];x=x+1;/*x統(tǒng)計(jì)刪除數(shù)字的個(gè)數(shù)*/i=0;}/*從頭開始查遞增區(qū)間*/if(i==n-x-1)m=1;}/*已無遞增區(qū)間,m=1脫離循環(huán)*/printf("\n刪除后所得最大數(shù):");for(i=1;i<=n-k;i++)/*打印剩下的左邊n-k個(gè)數(shù)字*/printf("%d",a[i-1]);}例5.2數(shù)列極差問題

在黑板上寫N個(gè)正整數(shù)排成一個(gè)數(shù)列，進(jìn)行如下操作:每一次擦去其中的兩個(gè)數(shù)a和b，然后在數(shù)列中加入一個(gè)數(shù)a×b+1，如此下去直至黑板上剩下一個(gè)數(shù)，在所有按這種操作方式最后得到的數(shù)中，最大的記作max，最小的記作min，則該數(shù)列的極差定義為M=max-min。如： 對三個(gè)具體數(shù)據(jù)3，5，7討論，可能有以下三種結(jié)果：(3*5+1)*7+1=113,(3*7+1)*5+1=111,(5*7+1)*3+1=109結(jié)論：先運(yùn)算小數(shù)據(jù)得到的是最大值，先運(yùn)算大數(shù)據(jù)得到的是最小值。

顯然此問題適合用貪婪策略,不過在求最大值時(shí)，要先選擇較小的數(shù)操作。求最小值時(shí)，要先選擇較大的數(shù)操作。這是一道兩次運(yùn)用貪心策略解決的問題。1）不斷從現(xiàn)有的數(shù)據(jù)中，選取最大和最小的兩個(gè)數(shù)，計(jì)算后的結(jié)果繼續(xù)參與運(yùn)算，直到剩余一個(gè)數(shù)算法結(jié)束。2)選取最大和最小的兩個(gè)數(shù)較高效的算法是用二分法完成，這里僅用簡單的逐個(gè)比較方法來求解。注意到由于找到的兩個(gè)數(shù)將不再參與其后的運(yùn)算，其中一個(gè)用它們的計(jì)算結(jié)果代替，另一個(gè)用當(dāng)前的最后一個(gè)數(shù)據(jù)覆蓋即可。所以不但要選取最大和最小，還必須記錄它們的位置，以便將其覆蓋。3）求max、min過程必須獨(dú)立，即求max和min都必須從原始數(shù)據(jù)開始,否則不能找到真正的max和min。1)由設(shè)計(jì)2）、3）知，必須用兩個(gè)數(shù)組同時(shí)存儲初始數(shù)據(jù)。2)求最大和最小的兩個(gè)數(shù)的函數(shù)至少要返回兩個(gè)數(shù)據(jù)，方便起見用全局變量實(shí)現(xiàn)。

ints1,s2;main(){intj,n,a[100],b[100],max,min;printf("Howmangdata?");scanf("%d",&n);printf("inputthesedata");for(j=1;j<=n;j=j+1){scanf("%d",&a[j]);b[j]=a[j];}min=calculatemin(a,n);max=calculatemax(b,n);printf("max=%d,min=%d,max-min=%d",max,min,max-min);}求一組數(shù)據(jù)中兩個(gè)最大值算法：

a[12345678…]

可以假設(shè)兩個(gè)變量s1,s2分別儲存這兩個(gè)值所在數(shù)組中的下標(biāo)，一個(gè)最大，一個(gè)次大值。數(shù)組只有兩個(gè)元素時(shí)：a1>a2,令s1=1,s2=2;否則s1=2,s2=1;

數(shù)組再增加一個(gè)元素j（下標(biāo)）時(shí)：

if(a[j]>a[s1]){s2=s1;s1=j;}elseif(a[j]>a[s2])s2=j;

max2(inta[],intn){intj;if(a[1]>=a[2]){s1=1;s2=2;}else{s1=2;s2=1;}for(j=3;j<=n;j++){if(a[j]>a[s1]){s2=s1;s1=j;}elseif(a[j]>a[s2])s2=j;}}intcalculatemin(inta[],intn){intj;while(n>2){max2(a,n);a[s1]=a[s1]*a[s2]+1;a[s2]=a[n];n=n-1;}return(a[1]*a[2]+1);}min2(inta[],intn){intj;if(a[1]<=a[2]){s1=1;s2=2;}else{s1=2;s2=1;}for(j=3;j<=n;j++)if(a[j]<a[s1]){s2=s1;s1=j;}elseif(a[j]<a[s2])s2=j;}intcalculatemax(inta[],intn){intj;while(n>2){min2(a,n);a[s1]=a[s1]*a[s2]+1;a[s2]=a[n];n=n-1;}return(a[1]*a[2]+1);}貪心算法例子：設(shè)計(jì)一個(gè)算法，把一個(gè)真分?jǐn)?shù)表示為埃及分?jǐn)?shù)之和的形式。所謂埃及分?jǐn)?shù)，是指分子為1的分?jǐn)?shù)。如：7/8=1/2+1/3+1/24?；舅枷耄褐鸩竭x擇分?jǐn)?shù)所包含的最大埃及分?jǐn)?shù)，這些埃及分?jǐn)?shù)之和就是問題的一個(gè)解。如：7/8>1/2，

7/8-1/2>1/3，

7/8-1/2-1/3=1/24。過程如下：

1)找最小的n（最大的埃及分?jǐn)?shù)1/n），使分?jǐn)?shù)f>1/n；

2)輸出1/n；

3)計(jì)算f=f-1/n；

4)若此時(shí)的f是埃及分?jǐn)?shù)，輸出f,算法結(jié)束,否則返回1）。森林里進(jìn)行一場裝背包比賽：參加者：黑熊猴子啄木鳥每個(gè)比賽者一個(gè)背包，背包的載重量為20公斤。給定N個(gè)物品，每個(gè)物品有一定的重量和價(jià)值。20kg5.3背包問題

森林里進(jìn)行一場裝背包比賽規(guī)則：物品可切一部分放入；背包里裝的物品的總重量不超過背包的載重量；背包里裝的物品的價(jià)值最高者獲勝。黑熊

黑瞎子掰棒子的策略：價(jià)值高的優(yōu)先放入。物品n=3，背包的載重量C=20各個(gè)物品的價(jià)值(v1,v2,v3)=(25,24,15)各個(gè)物品的重量(w1,w2,w3)=(18,15,10)。物品1物品212/15(25,18)(24*2/15,2)計(jì)算器25+24*(2/15)

=

28.2物品3物品212/3猴子耍小聰明策略：重量小的優(yōu)先放入。物品n=3，背包的載重量C=20各個(gè)物品的價(jià)值(v1,v2,v3)=(25,24,15)各個(gè)物品的重量(w1,w2,w3)=(18,15,10)。計(jì)算器15+24*(2/3)

=

31

啄木鳥算盤子策略：單位重量價(jià)值高的優(yōu)先放入。物品n=3，背包的載重量C=20各個(gè)物品的價(jià)值(v1,v2,v3)=(25,24,15)各個(gè)物品的重量(w1,w2,w3)=(18,15,10)單位價(jià)值

(v1/w1,v2/w2,v3/w3)=(1.39,1.6,1.5)物品2物品311/2計(jì)算器24+15*(1/2)

=

31.5啄木鳥算盤子策略的時(shí)間復(fù)雜度?第一步:選出單位重量價(jià)值最高者裝入。

n個(gè)中取最大值第二步：刪除該物品。第三步:重復(fù)1,2步,直至再裝入就超出背包的載重量為止。第四步:把最后選擇物品的一部分裝入背包:

剩余載重量/最后選擇物品的重量O(n)O(n2)O(n)啄木鳥算盤子策略能否改進(jìn)?時(shí)間復(fù)雜度?第一步:按照單位重量價(jià)值遞減排序。

n個(gè)數(shù)排序第二步:按排序順序依次裝入直至再裝入就超出背包的載重量為止。第三步:把最后選擇物品的一部分裝入背包:

剩余載重量/最后選擇物品的重量O(nlogn)O(nlogn)O(n)背包問題

該問題就是背包問題：已知：給定n種物品和一個(gè)背包。物品i重量是Wi，其價(jià)值為Vi，背包容量為C。求解：如何選擇裝入背包的物品，使得裝入背包中物品總價(jià)值最大?每個(gè)物品xi可以不被裝入背包，也可以部分裝入背包,0≤xi≤1每個(gè)物品的價(jià)值和重量值都大于0，總共有n個(gè)物品，vi>0，wi>0，1≤i≤n約束條件:背包載重量是C，因此選入背包中物品的總重量不得超過C背包問題的形式化描述問題的求解目標(biāo):背包中的物品總價(jià)值最大。目標(biāo)函數(shù): max物品可拆背包問題C程序設(shè)計(jì)代碼如下：for(i=1;i<=n-1;i++)/*對n件物品按單位重量的效益從大到小排序*/for(j=i+1;j<=n;j++)if(p[i]/w[i]<p[j]/w[j]){h=p[i];p[i]=p[j];p[j]=h;h=w[i];w[i]=w[j];w[j]=h;}cw=c;s=0;/*cw為背包還可裝的重量*/for(i=1;i<=n;i++){if(w[i]>cw)break;x[i]=1.0;/*若w(i)<=cw,整體裝入*/cw=cw-w[i];s=s+p[i];}x[i]=(float)(cw/w[i]);/*若w(i)>cw,裝入一部分x(i)*/s=s+p[i]*x[i];printf("裝包：");/*輸出裝包結(jié)果*/for(i=1;i<=n;i++)if(x[i]<1)break;elseprintf("\n裝入重量為%5.1f的物品.",w[i]);if(x[i]>0&&x[i]<1)printf("\n裝入重量為%5.1f的物品百分之%5.1f.",w[i],x[i]*100);printf("\n所得最大效益為：%7.1f",s);

二分圖是一個(gè)無向圖，它的n個(gè)頂點(diǎn)可二分為集合A和集合B，且同一集合中的任意兩個(gè)頂點(diǎn)在圖中無邊相連（即任何一條邊都是一個(gè)頂點(diǎn)在集合A中，另一個(gè)在集合B中）。當(dāng)且僅當(dāng)B中的每個(gè)頂點(diǎn)至少與A中一個(gè)頂點(diǎn)相連時(shí)，A的一個(gè)子集A‘覆蓋集合B（或簡單地說，A’是一個(gè)覆蓋）。覆蓋A‘的大小即為A’中的頂點(diǎn)數(shù)目。當(dāng)且僅當(dāng)A‘是覆蓋B的子集中最小的時(shí)，A’為最小覆蓋。

5.4覆蓋問題

如下圖所示：A={1,2,3,4};B={5,6,7,8,9,10,11};選擇A的一個(gè)最小覆蓋子集A‘，使B中的每個(gè)頂點(diǎn)至少與A中一個(gè)頂點(diǎn)相連。算法設(shè)計(jì)如下：先構(gòu)造鄰接矩陣，如圖1可以構(gòu)造如下： 圖1 圖2計(jì)算a各個(gè)頂點(diǎn)的度，從中選擇度最大的頂點(diǎn)，加入到子集中，如第一次，各個(gè)頂點(diǎn)度為4，2，4，2，可以將結(jié)點(diǎn)1加入到子集。修改鄰接矩陣，將結(jié)點(diǎn)1從a集合中去掉，與1所連的邊都抹掉。如圖2。重復(fù)上面過程，直到鄰接矩陣值都為0，則找到一組解，否則失敗。該算法的時(shí)間復(fù)雜度取決于數(shù)據(jù)的存儲方式，若使用鄰接矩陣，則需花(n2)的時(shí)間來尋找圖中的邊，若用鄰接鏈表，則需(n+e)的時(shí)間。故覆蓋算法總的復(fù)雜性為O(n2)或O(n+e)1、活動(dòng)安排問題

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

設(shè)有n個(gè)活動(dòng)的集合E={1,2,…,n}，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的時(shí)間[si,fi)：（起始時(shí)間si，結(jié)束時(shí)間fi,且si<fi

）。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動(dòng)i與活動(dòng)j是相容的。也就是說，當(dāng)si≥fj或sj≥fi時(shí)，活動(dòng)i與活動(dòng)j相容。

例：設(shè)待安排的11個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：i1234567891011S[i]130535688212f[i]4567891011121314

由于輸入的活動(dòng)以其完成時(shí)間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時(shí)間的相容活動(dòng)加入集合A中。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。 算法greedySelector的效率極高。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需O(n)的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。如果所給出的活動(dòng)未按非減序排列，可以用O(nlogn)的時(shí)間重排。

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

貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動(dòng)安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動(dòng)集合A的規(guī)模最大。這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明。voidGreedySelector(intn,Types[],Typef[],intA[]){A[1]=1;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=1;j=i;}elseA[i]=0;}}下面給出解活動(dòng)安排問題的貪心算法GreedySelector:各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲于數(shù)組s和f中且按結(jié)束時(shí)間的非減序排列

2、多機(jī)調(diào)度問題 多機(jī)調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺機(jī)器加工處理完成。

這個(gè)問題到目前為止還沒有有效的解法。對于這一類問題,用貪心選擇策略有時(shí)可以設(shè)計(jì)出較好的近似算法。

約定，每個(gè)作業(yè)均可在任何一臺機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。

采用最長處理時(shí)間作業(yè)優(yōu)先的貪心選擇策略可以設(shè)計(jì)出解多機(jī)調(diào)度問題的較好的近似算法。 按此策略，當(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)。

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

排序后：{4(16),2(14),5(6),6(5),3(4),7(3),1(2),}3、地圖的著色（4色）定理：任何平面地圖可以使用4種顏色給每個(gè)不同的城市著色，而保證相鄰的城市著不同的顏色思路：把地圖上的每個(gè)城市抽象為一個(gè)點(diǎn)，并給每個(gè)城市編號，，相鄰的城市之間用直線連接。據(jù)此做出鄰接矩陣，若第i個(gè)城市與第j個(gè)城市相鄰，則metro[i][j]=1,否則metro[i][j]=0。算法：按照編號從小到大的順序檢查每個(gè)城市，對每個(gè)城市從1到4使用4種顏色著色，若當(dāng)前顏色可用（即不與相鄰城市顏色相同），則著色；否則測試下一種顏色。

voidcolor(intmetro[N][N],intr_color[N],intsum)

{

inti,j,k;

for(i=1;i<=sum;i++)/*檢查所有城市*/

for(j=1;j<=4;j++)/*對每個(gè)城市嘗試4種顏色的著色方案*/

{

r_color[i]=j;/*嘗試著色*/

for(k=1;k<i;k++)/*檢查是否與相鄰城市顏色相同*/

if(metro[i][k]==1&&r_color[k]==r_color[i])

break;/*相同則跳出，此時(shí)有k<i，則下面條件不成立，繼續(xù)嘗試下一種顏色*/

if(k>=i)/*若不相同，則使用當(dāng)前顏色，并檢查下一個(gè)城市*/

break;

}

}#defineN21voidmain()

{

intr_color[N]={0};inti;

intmetro[N][N]={{0},/*鄰接矩陣*/

{0,1,1,1,1,1,1},

{0,1,1,1,1},

{0,1,1,1,0,0,1},

{0,1,1,0,1,1},

{0,1,0,0,1,1,1,0,0,1,0,0,0,0,0,0,1},

{0,1,0,1,0,1,1,1,1,1},

{0,0,0,0,0,0,1,1,1},