算法設計與分析

Design

and

AnalysisofComputerAlgorithms

第3篇核心篇貪婪算法貪婪算法（貪心法）的設計思想貪婪算法的求解過程貪婪算法的基本要素貪婪算法的應用舉例教學內容：貪婪算法的設計思想【基本思想】將問題的求解過程看作是一系列選擇，每次選擇一個輸入，每次選擇都是當前狀態下的最好選擇（局部最優解），每作一次選擇后，所求問題會簡化為一個規模更小的子問題，從而通過每一步的最優解逐步達到整體的最優解。

貪心法在解決問題的策略上目光短淺，只根據當前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結果，這個選擇都不會改變。換言之，貪心法并不是從整體最優考慮，它所做出的選擇只是在某種意義上的局部最優。這種局部最優選擇并不總能獲得整體最優解（OptimalSolution），但通常能獲得近似最優解（Near-OptimalSolution）。引例[找零錢]一個小孩買了價值少于1美元的糖，并將1美元的錢交給售貨員。售貨員希望用數目最少的硬幣找給小孩。假設提供了數目不限的面值為25美分、10美分、5美分、及1美分的硬幣。售貨員分步驟組成要找的零錢數，每次加入一個硬幣。選擇硬幣時所采用的貪婪準則如下：

每一次選擇應使零錢數盡量增大。為保證解法的可行性（即：所給的零錢等于要找的零錢數），所選擇的硬幣不應使零錢總數超過最終所需的數目。算法思想為使找回的零錢的硬幣數最小，不考慮找零錢的所有各種方案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，只當不足大面值幣種的金額才會去考慮下一種較小面值的幣種，這就是在采用貪婪法。這種方法在這里之所以總是最優，是因為銀行對其發行的硬幣種類和硬幣面值的巧妙安排。如果只有面值分別為1，5和11單位的硬幣，而希望找回總額為15單位的硬幣，按貪婪算法，應找1個11單位面值的硬幣和4個1單位面值的硬幣，共找回5個硬幣。但最優的解答應是3個5單位面值的硬幣。幣種統計問題【例】某單位給每個職工發工資（精確到元）。為了保證不要臨時兌換零錢，且取款的張數最少，去工資錢要統計所以職工的工資所需各種幣種（100,50,20,10,5,2,1共7種）的張數，請編程完成。【算法設計】1、為了保證不要臨時兌換零錢，且取款的張數最少，應該對每一個人的工資，用“貪婪”的思想，先盡量多地取大面額的幣種，由大面額到小面額幣種逐步統計。2、利用數組應用技巧，將7種幣值存儲在數組中，從大面額的幣種到小面額的幣種依次存儲。幣種統計問題幣種統計問題inti,j,n,GZ,A,B[7]={100,50,20,10,5,2,1}; staticintS[7]; cin>>n;//輸入人數 for(i=0;i<n;i++) { cin>>GZ;//輸入每人的工資 for(j=0;j<7;j++) { A=GZ/B[j]; S[j]+=A; GZ=GZ-A*B[j]; } } for(i=0;i<7;i++) cout<<B[i]<<"-----"<<S[i]<<endl;//輸出每種幣種的張數2貪心法的求解過程

用貪心法求解問題應該考慮如下幾個方面：（1）候選集合C：為了構造問題的解決方案，有一個候選集合C作為問題的可能解，即問題的最終解均取自于候選集合C。例如，在付款問題中，各種面值的貨幣構成候選集合。（2）解集合S：隨著貪心選擇的進行，解集合S不斷擴展，直到構成一個滿足問題的完整解。例如，在付款問題中，已付出的貨幣構成解集合。

（3）解決函數solution：檢查解集合S是否構成問題的完整解。例如，在付款問題中，解決函數是已付出的貨幣金額恰好等于應付款。

（4）選擇函數select：即貪心策略，這是貪心法的關鍵，它指出哪個候選對象最有希望構成問題的解，選擇函數通常和目標函數有關。例如，在付款問題中，貪心策略就是在候選集合中選擇面值最大的貨幣。（5）可行函數feasible：檢查解集合中加入一個候選對象是否可行，即解集合擴展后是否滿足約束條件。例如，在付款問題中，可行函數是每一步選擇的貨幣和已付出的貨幣相加不超過應付款。

貪心法的一般過程Greedy(C)//C是問題的輸入集合即候選集合{S={};//初始解集合為空集while(notsolution(S))//集合S沒有構成問題的一個解{x=select(C);//在候選集合C中做貪心選擇iffeasible(S,x)//判斷集合S中加入x后的解是否可行S=S+{x};C=C-{x};}returnS;}活動安排問題

活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。活動安排問題【例】設有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間begin[i]和一個結束時間end[i],且begin[i]<end[i]。如果選擇了活動i，則它在半開時間區間[begin[i],end[i])內占用資源。若區間[begin[i],end[i])與區間[begin[j],end[j])不相交，則稱活動i與活動j是相容的。也就是說，當begin[i]≥end[j]或begin[j]≥end[i]時，活動i與活動j相容。【問題】找出時間上不重疊的事件【算法設計思想】a和b活動的開始時刻小于結束時刻Begin[a]<End[a]Begin[b]<End[b]b活動的開始時刻大于等于a活動的結束時刻,即Begin[b]>=End[a]記為b>a這時b活動與a活動不重疊,則選擇活動b加入集合中，否則不選擇該活動。活動安排問題【例】設待安排的12個活動的開始時間和結束時間按結束時間的非減序排列如下：i01234567891011begin[i]130325641081515end[i]3478910121415181920constintN=12;voidGreedySelector(intBegin[],intEnd[],intSelect[]){ inti,j; Select[0]=1; j=0; for(i=1;i<N;i++) {

if(Begin[i]>=End[j]) { Select[i]=1; j=i; } else Select[i]=0; }}//輸出選擇的活動voidOutputResult(intSelect[N]){ cout<<"{0";for(inti=1;i<N;i++)

if(Select[i]==1)

cout<<","<<i;cout<<"}"<<endl;}voidmain(){ intBegin[N]={1,3,0,3,2,5,6,4,10,8,15,15};//活動的最早開始時間intEnd[N]={3,4,7,8,9,10,12,14,15,18,19,20};//活動的最早結束的事件 staticintSelect[N]; intTimeStart=0; GreedySelector(Begin,End,Select); OutputResult(Select);}運行結果：3、貪心算法的基本要素 對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優解呢?這個問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質：貪心選擇性質和最優子結構性質。3貪心算法的基本要素【貪心選擇性質】

所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態規劃算法的主要區別。貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規模更小的子問題。

【算法缺點】對于一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優解。3貪心算法的基本要素【最優子結構性質】

當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。0-1背包問題：整數背包

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

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

與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。相同：這2類問題都具有最優子結構性質，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。區別：背包問題具有貪心選擇性質，而0-1背包問題卻不具有貪心選擇性質，不能用貪心算法求解。背包問題(KnapsackProblem)24背包問題(KnapsackProblem)【問題描述】已知有n種物品和一個可容納W重量的背包，每種物品I的重量為wi，假定將物品I的某一部分xi放入背包就會得到pixi的效益(0≤xi≤1,pi>0)，采用怎樣的裝包方法才會使裝入背包物品的總效益為最大呢？【問題的形式描述】極大化： ∑pixi

約束條件：∑wixi≤W

0≤xi≤1,pi>0,wi>0,1≤i≤n1≤i≤n1≤i≤n解的意義:xi表示物品i裝入背包的部分占該物品全部的比例（1）選擇價值最大的物品，因為這可以盡可能快地增加背包的總價值。但是，雖然每一步選擇獲得了背包價值的極大增長，但背包容量卻可能消耗得太快，使得裝入背包的物品個數減少，從而不能保證目標函數達到最大。（2）選擇重量最輕的物品，因為這可以裝入盡可能多的物品，從而增加背包的總價值。但是，雖然每一步選擇使背包的容量消耗得慢了，但背包的價值卻沒能保證迅速增長，從而不能保證目標函數達到最大。（3）選擇單位重量價值最大的物品，在背包價值增長和背包容量消耗兩者之間尋找平衡。至少有三種看似合理的貪心策略：背包問題(KnapsackProblem)背包問題(KnapsackProblem)方案1：按物品價值降序裝包方案2：按物品重量升序裝包方案3：按物品價值與重量比值的降序裝包

應用第三種貪心策略，每次從物品集合中選擇單位重量價值最大的物品，如果其重量小于背包容量，就可以把它裝入，并將背包容量減去該物品的重量，然后我們就面臨了一個最優子問題——它同樣是背包問題，只不過背包容量減少了，物品集合減少了。因此背包問題具有最優子結構性質。

背包問題(KnapsackProblem)

首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。 用貪心算法解背包問題的基本步驟：3貪心算法的基本要素voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);//改變數組w和v的排列順序，使其按單位重量價值v[i]/w[i]降序排列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];}//選擇物品的一部分將背包填滿3貪心算法的基本要素算法knapsack的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為O（nlogn）。為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質。

對于0-1背包問題，貪心選擇之所以不能得到最優解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。事實上，在考慮0-1背包問題時，應比較選擇該物品和不選擇該物品所導致的最終方案，然后再作出最好選擇。由此就導出許多互相重疊的子問題。3貪心算法的基本要素應用--貨箱裝船

貨箱裝船問題：設有編號為0…n-1的n種物品，重量分別為w0…wn-1，船載重為c，如何裝載，使船可以裝載更多的貨箱。1、算法設計采用貪婪算法船可以分步裝載，每步裝一個貨箱，且需要考慮裝載哪一個貨箱。根據這種思想可利用如下貪婪準則：從剩下的貨箱中，選擇重量最小的貨箱。這種選擇次序可以保證所選的貨箱總重量最小，從而可以裝載更多的貨箱。根據這種貪婪策略，首先選擇最輕的貨箱，然后選次輕的貨箱，如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個貨箱。貨箱裝船#include<iostream.h>voidIndirectSort(intw[],intt[],intn){//Clugetotestwhenweightsalreadyinorder.for(inti=1;i<=n;i++)t[i]=i;}template<classT>voidContainerLoading(intx[],Tw[],Tc,intn){//Greedyalgorithmforcontainerloading.//Setx[i]=1iffcontaineri,1<=i<=nisloaded.//cisshipcapacity,wgivescontainerweights.//doindirectaddressingsortofweights

//tistheindirectaddressingtable

貨箱裝船

int*t=newint[n+1];IndirectSort(w,t,n);for(inti=1;i<=n;i++)x[i]=0;//selectobjectsinorderofweightfor(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}//remainingcapacitydelete[]t;}貨箱裝船voidmain(void){intw[13]={0,20,50,50,80,90,100,150,200},x[13];ContainerLoading(x,w,400,8);cout<<"Loadingvectoris"<<endl;for(inti=1;i<=8;i++)cout<<x[i]<<'';cout<<endl;}2、貪心選擇性質 可以證明最優裝載問題具有貪心選擇性質。3、最優子結構性質 最優裝載問題具有最優子結構性質。 由最優裝載問題的貪心選擇性質和最優子結構性質，容易證明算法ContainerLoading的正確性。 算法ContainerLoading的主要計算量在于將集裝箱依其重量從小到大排序，故算法所需的計算時間為O(nlogn)。

多機調度問題【多機調度問題】設有

n個獨立的作業{1,2,..,n}，由m

臺相同的機器進行加工處理。作業i所需的處理時間為ti

。現約定，任何作業可以在任何一臺機器上加工處理，但未完工前不允許中斷處理，任何作業不能拆分成更小的作業。要求：給出一種作業調度方案，使所給的n個作業在盡可能短的時間內由m臺機器加工處理完成。

多機調度問題

【分析】：這個問題是一個NP完全問題（(Non-deterministicPolynomial)，即多項式復雜程度的非確定性問題），到目前為止還沒有一個有效的解法。對于這一類問題，用貪心選擇策略有時可以設計出較好的近似算法。采用最長處理時間作業優先的貪心選擇策略可以設計出解多機調度問題的較好的近似算法。

按此策略，當n<=m時，只要將機器i的[0,ti]時間區間分配給作業i即可。

當n>m時，首先將n個作業依其所需的處理時間從大到小排序，然后依此順序將作業分配給空閑的處理機。多機調度問題

【例如】設7個獨立作業{1,2,3,4,5,6,7}由3臺機器M1，M2和M3加工處理。各作業所需的處理時間分別為{2,14,4,16,6,5,3}。用貪心選擇策略產生的作業調度如下圖所示，所需的加工時間為17。

【問題描述】

鍵盤輸入一個高精度的正整數N，去掉其中任意S個數字后剩下的數字按原左右次序將組成一個新的正整數。編程對給定的N和S，尋找一種方案使得剩下的數字組成的新數最小。輸入數據均不需判錯,輸出應包括所去掉的數字的位置和組成的新的正整數。

刪數游戲【算法分析】這是一道運用貪心策略求解的典型問題。在位數固定的前提下，讓高位的數字盡量小其值就較小，依據此貪婪策略就可以解決這個問題。怎么樣根據貪婪策略刪除數字呢？總目標是刪除高位較大的數字，具體地相鄰兩位比較若高位比低位大則刪除高位。每次刪除一個數字,選擇一個使剩下的數最小的數字作為刪除對象,之所以選擇這樣”貪心”的操作,是因為刪S個數字的全局最優解包含了刪一個數字的子問題的最優解。

刪數游戲【例如】N=175438,S=4;可以刪去7,5,4,8,得到13。刪除S次，每次刪的數要使剩下的數盡量小。例如上面的例子，第一次刪7,至少比第一次刪1,5,4,3,8好！

這樣，刪數過程是：175438

15438

1438

138

13【算法思想】從左向右找到第一個i,使n[i]>n[i+1]，如果找到了，就刪除第i個數字，否則刪除刪除了若干個最右邊的大數字。

刪數游戲當S=1時,在N中刪除哪一個數字能達到最小的目的?從左到右每相鄰的兩個數字比較:若出現左邊大于右邊,則刪除左邊的大數字.若不出現降序排列,即所有數字全部升序,則刪除最右邊的大數字.當S>1,按上述操作一個一個刪除,刪除一個達到最小后,再從頭即從串首開始,刪除第2個,依次分解為S次完成.若刪除不到S個后已無左邊大于右邊的減序,則停止刪除操作,打印剩下串的左邊L-S個數字即可(相當于刪除了若干個最右邊的大數字,這里L為原數字N的位數).

刪數游戲#include<iostream>#include<string>usingnamespacestd;intmain(){ stringn;//利用字符串數組保存高精度數字 ints,i,x,m,l;cout<<"inputdataanddeletedatalength:"; cin>>n>>s; i=-1; m=0; x=0;//x統計刪除數字的個數 l=n.length(); while(x<s&&m==0) { i++; if(n[i]>n[i+1])//出現遞減,刪除遞減的首數字 {n=n.erase(i,1); x++; i=-1;//從頭開始查遞減區間 } if(i==1-x-2&&x<s) m=1;//已經無遞減區間,循環結束 }

if(x<s)cout<<n.substr(0,l-s+x);//只打印剩下的左邊l-(s-x)個數字elsecout<<n<<endl;return0;}運行結果：設計一個算法，把一個真分數表示為埃及分數之和的形式。【問題分析】

所謂埃及分數，是指分子為1的形式。古代埃及有一個非常奇怪的習慣，他們喜歡把一個分數表示為若干個分子為1的分數之和的形式。如：7/8=1/2+1/3+1/24

埃及分數【算法思想】逐步選擇分數所包含的最大埃及分數，這些埃及分數之和就是問題的一個解。數學家斐波那契提出的一種求解埃及分數的貪心算法，基本思想是：

(1)設某個真分數