算法-貪心算法

第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貪心算法概述貪心算法通過一系列的局部選擇來得到一個問題的解。所作的每一個選擇都是當(dāng)前狀態(tài)下“最優(yōu)”的選擇。要依照某種策略。策略“只顧眼前，不管將來”，稱之為“貪心策略”。貪心算法沒有固定的算法框架，算法設(shè)計(jì)的關(guān)鍵是貪心策略的選擇貪心算法在求解最優(yōu)化問題時，從初始階段開始，每一個階段總是作一個使局部最優(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)前部分解的一個擴(kuò)展，直至獲得問題的完整解。所做的每一步選擇都必須滿足：

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

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

(3)不可取消:

選擇一旦做出，在后面的步驟中就無法改變了。貪心算法是通過做一系列的選擇來給出某一問題的最優(yōu)解，對算法的每一個決策點(diǎn)，做一個當(dāng)時（看起來）是最佳的選擇。這種啟發(fā)式策略并不總是能產(chǎn)生出最優(yōu)解。例5.1刪除數(shù)字問題鍵盤輸入一個高精度的正整數(shù)N，去掉其中任意S個數(shù)字后剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(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ù)字盡量小其值就較小；刪除高位較大的數(shù)字；具體地相鄰兩位比較若高位比低位大則刪除高位。n1=“12435863”4比3大刪除4“1235863”8比6大刪除8“123563”6比3大刪除6“12353”再一個實(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由這個實(shí)例看出，經(jīng)過對n3相鄰比較一個數(shù)字都沒有刪除，這就要考慮將后三位進(jìn)行刪除；當(dāng)然還有可能，在相鄰比較的過程中刪除的位數(shù)小于s時，也要進(jìn)行相似的操作。n4=”120083”s=32比0大刪除2“10083”1比0大刪除1“0083”8比3大刪除8“003”由這個實(shí)例子又能看出，當(dāng)刪除掉一些數(shù)字后，結(jié)果的高位有可能出現(xiàn)數(shù)字“0”，直接輸出這個數(shù)據(jù)不合理，要將結(jié)果中高位的數(shù)字“0”刪除掉，再輸出。特別地還要考慮若結(jié)果串是“0000”時，不能將全部“0”都刪除，而要保留一個“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ù)字的個數(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個數(shù)字*/printf("%d",a[i-1]);}例5.2數(shù)列極差問題

在黑板上寫N個正整數(shù)排成一個數(shù)列，進(jìn)行如下操作:每一次擦去其中的兩個數(shù)a和b，然后在數(shù)列中加入一個數(shù)a×b+1，如此下去直至黑板上剩下一個數(shù)，在所有按這種操作方式最后得到的數(shù)中，最大的記作max，最小的記作min，則該數(shù)列的極差定義為M=max-min。如： 對三個具體數(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ù)操作。這是一道兩次運(yùn)用貪心策略解決的問題。1）不斷從現(xiàn)有的數(shù)據(jù)中，選取最大和最小的兩個數(shù)，計(jì)算后的結(jié)果繼續(xù)參與運(yùn)算，直到剩余一個數(shù)算法結(jié)束。2)選取最大和最小的兩個數(shù)較高效的算法是用二分法完成，這里僅用簡單的逐個比較方法來求解。注意到由于找到的兩個數(shù)將不再參與其后的運(yùn)算，其中一個用它們的計(jì)算結(jié)果代替，另一個用當(dāng)前的最后一個數(shù)據(jù)覆蓋即可。所以不但要選取最大和最小，還必須記錄它們的位置，以便將其覆蓋。3）求max、min過程必須獨(dú)立，即求max和min都必須從原始數(shù)據(jù)開始,否則不能找到真正的max和min。1)由設(shè)計(jì)2）、3）知，必須用兩個數(shù)組同時存儲初始數(shù)據(jù)。2)求最大和最小的兩個數(shù)的函數(shù)至少要返回兩個數(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ù)中兩個最大值算法：

a[12345678…]

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

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

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

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

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

=

31

啄木鳥算盤子策略：單位重量價(jià)值高的優(yōu)先放入。物品n=3，背包的載重量C=20各個物品的價(jià)值(v1,v2,v3)=(25,24,15)各個物品的重量(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啄木鳥算盤子策略的時間復(fù)雜度?第一步:選出單位重量價(jià)值最高者裝入。

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

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

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

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

該問題就是背包問題：已知：給定n種物品和一個背包。物品i重量是Wi，其價(jià)值為Vi，背包容量為C。求解：如何選擇裝入背包的物品，使得裝入背包中物品總價(jià)值最大?每個物品xi可以不被裝入背包，也可以部分裝入背包,0≤xi≤1每個物品的價(jià)值和重量值都大于0，總共有n個物品，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);

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

5.4覆蓋問題

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

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

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

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

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

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

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

貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結(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;}}下面給出解活動安排問題的貪心算法GreedySelector:各活動的起始時間和結(jié)束時間存儲于數(shù)組s和f中且按結(jié)束時間的非減序排列

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

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

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

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

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

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

{

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

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

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

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

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

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},