第9講貪心算法

1、第9講 貪心算法,一、問題引入 例8-1工資發(fā)放問題：某單位發(fā)放員工的工資為整數(shù)，用票面為100、50、20、10、5、2、1圓的幣發(fā)放，問如何發(fā)放，使得每位員工所領(lǐng)工資的票數(shù)最少？ 例如：發(fā)放工資2379元，票數(shù)最少時(shí)，應(yīng)為100元：23張；50元：1張； 20元：1張； 5元：1張； 2元：2張。 思路分析： 我們會(huì)下意識(shí)地想到，要使總的票數(shù)最少，應(yīng)當(dāng)首先考慮使用大面額幣值，其次考慮面額稍小一點(diǎn)的幣值，最后面額最小的幣值。,程序設(shè)計(jì)基本如下： int m,i,a7,b7=100,50,20,10,5,2,1; coutm; for(i=0;i=6;i+) ai=m/bi; m=m%bi;

2、coutbi“ : ”aiendl; ,上述尋求的票面發(fā)放思想實(shí)際上就是貪心算法。貪心算法，顧名思義，總是作出在當(dāng)前看來最優(yōu)的選擇，并不是從總體上考慮最優(yōu)，它的選擇只是在某種意義上的局部最優(yōu)。 例8-2假設(shè)現(xiàn)有四種硬幣，面值二角五分、一角、五分和一分?，F(xiàn)要找給某顧客六角三分錢，要讓硬幣數(shù)最少，如何找法？ 如果硬幣面值改為一分、五分、一角一分三種，而找給顧客一角五分錢又如何找法？ 分析：第一個(gè)問題可就大面值幣解決。第二個(gè)顯然不行，而用三個(gè)五分幣最隹。 總結(jié)：貪心算法不是對(duì)所有問題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣的許多問題它能產(chǎn)生整體最優(yōu)解，如：?jiǎn)卧醋疃搪窂健⒆钚∩蓸鋯栴}等。在一些情況下，貪心

3、算法不能得到整體最做出解，但其結(jié)果卻是最優(yōu)解的很好的近似解。,二、最優(yōu)解、全局最優(yōu)和最優(yōu)子結(jié)構(gòu)概念 最優(yōu)解-一個(gè)問題的求解表示成問題規(guī)模n的函數(shù)f(n),當(dāng)n很大時(shí),我們可以得到相應(yīng)的下界,下界在該問題的所有算法或某類算法中復(fù)雜性中取,那么它將有意義,這時(shí)得到的下界稱為問題的下界或某類算法的下界,我們就說該問題的這個(gè)特定算法是該問題的最優(yōu)算法或該某類算法中的最優(yōu)算法。簡(jiǎn)單說,最優(yōu)算法稱為最優(yōu)解，有二重含義，一是達(dá)到目標(biāo)時(shí)次數(shù)最少，二是同樣次數(shù)數(shù)量級(jí)下，解的結(jié)果最優(yōu)。例好sin(x)的算法編寫，一重循環(huán)是最優(yōu)解，二重循環(huán)則不是最優(yōu)解。 全局最優(yōu)-一個(gè)問題的考慮，從全局角度考慮，每一步或一階段都是

4、最優(yōu)的，稱之為全局最優(yōu)。 最優(yōu)子結(jié)構(gòu)-當(dāng)問題的最優(yōu)解包含了其子問題的最優(yōu)解時(shí)，稱該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。,三、貪心算法的基本要素 貪心算法通過一系列的選擇來得到一個(gè)問題的解。它所作的每一個(gè)選擇都是當(dāng)前狀態(tài)下某種意義的最好選擇，即貪心選擇。希望通過每次的貪心選擇導(dǎo)致最終結(jié)果是問題的一個(gè)最優(yōu)解。這種啟發(fā)式的策略并不總能有效，然而許多情況下能達(dá)到預(yù)期目的。 對(duì)于一個(gè)具體問題，我們?cè)趺粗揽捎秘澬乃惴▉砬蠼獯藛栴}？這個(gè)問題很難給予肯定回答。 從實(shí)際經(jīng)驗(yàn)和許多可用貪心算法求解的問題中，人們總結(jié)，它們一般具有二個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 1、貪心選擇性質(zhì) 對(duì)于一個(gè)具體問題，如果我們證明

5、每一步所作的貪心選擇最終導(dǎo)致問題的一個(gè)整體最優(yōu)解時(shí)，則稱此方法具有貪心選擇性質(zhì)。問題的貪心選擇證明往往采用數(shù)學(xué)規(guī)納法。 2、最優(yōu)子結(jié)構(gòu)性質(zhì),例8-3事件序列問題 已知N=12個(gè)事件的發(fā)生時(shí)刻和結(jié)束時(shí)刻（見下 表，已按結(jié)束時(shí)刻做了升序排列）。一些在時(shí)間上 沒有重疊的事件可以構(gòu)成一個(gè)事件序列，如事件2、 8、10，寫成2，8，10。事件序列包含的事件數(shù)目 稱為該事件序列的長(zhǎng)度。請(qǐng)編程找出一個(gè)最長(zhǎng)的事 件序列。,分析：用Begini表示事件i的發(fā)生時(shí)刻，Endi表示事件i的結(jié)束時(shí)刻，事件a ，b（aBegina，故 BeginaEnda BeginbEndb 對(duì)于三個(gè)事件a，b，c（abc），沒有重

6、疊則同樣可推出： BeginaEnda BeginbEndb BegincEndc。 本題的目標(biāo)是找到一個(gè)最長(zhǎng)的序列a1a2an，滿足： Begina1Enda1 Begina2Enda2 BeginanEndan 選擇策略：在可能的事件系列a1a2an選擇時(shí)間上不重疊的最長(zhǎng)系列，一定存在一個(gè)包含a1的最長(zhǎng)系列。,證明： 確定貪心選擇性質(zhì)： 在當(dāng)前可選的事件中，選取最先結(jié)束且與前不重疊的那個(gè)事件進(jìn)入序列，不斷做下去，則構(gòu)成的系列一定是最長(zhǎng)序列。 程序設(shè)計(jì)：,例8-4區(qū)間覆蓋問題 用i來表示x軸上坐標(biāo)為i-1,i的區(qū)間（長(zhǎng)度為 1），并給出M個(gè)不同的整數(shù)(1M 200) ，表示M個(gè)這樣的區(qū)間?，F(xiàn)

7、在要求畫幾條線 段覆蓋住所有的區(qū)間，條件是：每條線段任 意長(zhǎng)，但要求所畫線段的長(zhǎng)度之和最小，并 且線段的數(shù)目不超過N（ 1N50 ） 分析：區(qū)間記錄、數(shù)組設(shè)置、線段劃分 確定貪心選擇性質(zhì)： 程序設(shè)計(jì)：,const int M=5,N=3; void main() void sort(int *a,int n); int pM=0,2,3,7,10,zc,dM-1; zc=pM-1+1; for(int i=0;iM-1;i+) di=pi+1-pi-1; sort(d,M-1); for(i=0;iN-2;i+)zc=zc-di; cout“Mini length=”zcendl; void

8、sort(int *a,int n) int i,j,t; for(i=0;in-2;i+) for(j=i+1;jn;j+ if(aiaj) t=ai,ai=aj,aj=t; ,四、貪心算法的相關(guān)理論 （1）多階段決策問題 如果一個(gè)問題的解決過程可以分為若干階段，在每一階段都做出相應(yīng)的決策，所有決策構(gòu)成了問題的解決策略。 如果每一階段面臨的問題都是原問題的一個(gè)子問題，而且子問題的解決只與當(dāng)前和以后的階段決策有關(guān)，與以前的各階段的決策無關(guān)，則稱該問題具有無后向性特點(diǎn)。 （2）貪心算法解題的一般步驟,分析問題： 該問題能否滿足最優(yōu)化原理 問題能否轉(zhuǎn)化為多階段決策問題； 各階段問題是否具有無后向性特點(diǎn)； 最優(yōu)解的子問題解是否最優(yōu)。 選擇的策略能否得到最優(yōu)解 為給出最終解或所有解