程序設(shè)計(jì)培訓(xùn)講義4：貪心算法

1、程序設(shè)計(jì)培訓(xùn)之4：貪心算法袁輝勇2010年1月8日 貪心法也稱為貪婪法。貪心法也稱為貪婪法。 算法原理：算法原理：以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪心法不而不考慮各種可能的整體情況，所以貪心法不要回溯。要回溯。 算法優(yōu)點(diǎn)：算法優(yōu)點(diǎn)：因?yàn)槭∪チ藶閷ふ医舛F盡因?yàn)槭∪チ藶閷ふ医舛F盡所有可能所必須耗費(fèi)的大量時間，因此算法效所有可能所必須耗費(fèi)的大量時間，因此算法效率高。率高。 注意：注意：通常使用貪心算法時需要證明。通常使用貪心算法時需要證明。一、概述一、概述例例1：找零錢問題。：找零錢問題。 平時購物找錢時，為使找回的零錢的硬平時購物找錢時，

2、為使找回的零錢的硬幣數(shù)最少，不考慮找零錢的所有各種發(fā)表方幣數(shù)最少，不考慮找零錢的所有各種發(fā)表方案，而是從最大面值的幣種開始，按遞減的案，而是從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，順序考慮各幣種，先盡量用大面值的幣種，當(dāng)不足大面值幣種的金額時才去考慮下一種當(dāng)不足大面值幣種的金額時才去考慮下一種較小面值的幣種。較小面值的幣種。 這就是在使用貪心法。這就是在使用貪心法。http:/ 找出一條路徑，使其從左下角至右上角所經(jīng)過的找出一條路徑，使其從左下角至右上角所經(jīng)過的權(quán)之和最大。權(quán)之和最大。分析：分析：例如下面的一個例如下面的一個23的方格陣中，每一格子都的方格陣中，每一

3、格子都填寫了一個數(shù)。填寫了一個數(shù)。若按若按貪心法貪心法求解，路徑為：求解，路徑為：1346；若按若按動態(tài)規(guī)劃法動態(tài)規(guī)劃法求解，路徑為：求解，路徑為：12106總結(jié)：總結(jié)：由于貪心策略自身的特點(diǎn)，使得數(shù)字由于貪心策略自身的特點(diǎn)，使得數(shù)字10所在的格子成為一個所在的格子成為一個“壞格子壞格子”，即運(yùn)用貪心，即運(yùn)用貪心策略找不到它，運(yùn)用貪心策略求解的第一步策略找不到它，運(yùn)用貪心策略求解的第一步（13）保證了局部最優(yōu)解，卻無法保證全局）保證了局部最優(yōu)解，卻無法保證全局最優(yōu)解。最優(yōu)解。故本問題不能使用貪心法來求解。故本問題不能使用貪心法來求解。 例例3 最優(yōu)裝載問題最優(yōu)裝載問題 有有n個集裝箱要裝上個集

4、裝箱要裝上1艘載重量分別為艘載重量分別為c的輪的輪船，其中第船，其中第i個集裝箱的重量為個集裝箱的重量為wi。最優(yōu)裝載問。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。裝載方案可能不盡可能多的集裝箱裝上輪船。裝載方案可能不唯一，約定長為唯一，約定長為n的的01字符串字符串(1:表示裝表示裝)以字典以字典序最大的那個為符合要求的裝載方案。序最大的那個為符合要求的裝載方案。輸出樣例輸出樣例1101101010010100輸入樣例：輸入樣例：3 5040 10 405 3710 30 24 35 40 枚舉算法思路：枚舉算法思路：

5、 這個問題可以用枚舉算法來解：設(shè)立一數(shù)這個問題可以用枚舉算法來解：設(shè)立一數(shù)組組x，數(shù)組每個元素，數(shù)組每個元素xi可能取值為可能取值為0或或1。如果。如果xi 為為0，則貨箱，則貨箱i 將不被裝上船；如果將不被裝上船；如果xi 為為1，則貨箱則貨箱 i 將被裝上船。將被裝上船。 貪心算法思路：貪心算法思路： 這個問題也可以用貪心算法來解：由于貨箱的這個問題也可以用貪心算法來解：由于貨箱的大小都一樣，但貨箱的重量都各不相同，故可以按照大小都一樣，但貨箱的重量都各不相同，故可以按照貨箱重量從大到小的順序來裝載。貨箱重量從大到小的順序來裝載。例例4 裝箱問題裝箱問題 設(shè)有編號為設(shè)有編號為0、1、n-1

6、的的n種物品，體積分種物品，體積分別為別為v0、v1、vn-1。將這。將這n種物品裝到容量都為種物品裝到容量都為V的的若干箱子里。約定這若干箱子里。約定這n種物品的體積均不超過種物品的體積均不超過V，即對，即對于于0in，有，有0viV。不同的裝箱方案所需要的箱子。不同的裝箱方案所需要的箱子數(shù)目可能不同。數(shù)目可能不同。 裝箱問題要求使裝盡這裝箱問題要求使裝盡這n種物品的箱子數(shù)要少。種物品的箱子數(shù)要少。 樣例：樣例： V=1，n=8，物品的體積分別為：，物品的體積分別為：0.8，0.5， 0.4，0.4， 0.3，0.2， 0.2，0.2。 問題分析：問題分析：若考察將若考察將n種物品的集合分劃

7、成種物品的集合分劃成n個或小個或小于于n個物品的所有子集，最優(yōu)解就可以找到。但所有個物品的所有子集，最優(yōu)解就可以找到。但所有可能劃分的總數(shù)可能劃分的總數(shù)(枚舉方法枚舉方法)太大。對適當(dāng)大的太大。對適當(dāng)大的n，找出，找出所有可能的劃分要花費(fèi)的時間是無法承受的。所有可能的劃分要花費(fèi)的時間是無法承受的。能否下面這樣貪心？為什么？能否下面這樣貪心？為什么？ 先將先將n件物品按照體積從大到小排序，然后按排件物品按照體積從大到小排序，然后按排序結(jié)果依次將物品放到它第一個能放進(jìn)去的箱子中。序結(jié)果依次將物品放到它第一個能放進(jìn)去的箱子中。0.50.41、求圖的最小生成樹、求圖

8、的最小生成樹A B C D E F 2 2 1 3 1 5 4二、數(shù)據(jù)結(jié)構(gòu)中的典型貪心算法二、數(shù)據(jù)結(jié)構(gòu)中的典型貪心算法Prim 算法的貪心策略：算法的貪心策略：每次已連通部分與未每次已連通部分與未連通部分之間的最小邊，直到圖連通為止。連通部分之間的最小邊，直到圖連通為止。Kruskal 算法的貪心策略：算法的貪心策略：每次選擇不構(gòu)成回每次選擇不構(gòu)成回路的最小邊，直到圖連通為止。路的最小邊，直到圖連通為止。2、求圖中頂點(diǎn)之間的最短路徑、求圖中頂點(diǎn)之間的最短路徑A B C D E F 2 3 1 10 1 5 4貪心策略：貪心策略：無論是無論是Dijkstra還是還是Folyd算法都算法都是用已發(fā)

9、現(xiàn)的最短路徑來替換。是用已發(fā)現(xiàn)的最短路徑來替換。例如：例如：A到到B的最短路徑的最短路徑 1) 開始開始A到到B的最短路徑為的最短路徑為10, A到到D為為2 2) 在求出在求出A到到E的最短路徑為的最短路徑為3后，發(fā)現(xiàn)后，發(fā)現(xiàn)ADEB的長度為的長度為5，將，將A到到B的的10改為改為6。例例1 1：刪數(shù)問題：刪數(shù)問題三、例題分析：三、例題分析： 鍵盤輸入一個高精度的正整數(shù)鍵盤輸入一個高精度的正整數(shù)N N，去掉其中，去掉其中任意任意S S個數(shù)字后剩下的數(shù)字按左右次序組成一個個數(shù)字后剩下的數(shù)字按左右次序組成一個新的正整數(shù)。對給定的新的正整數(shù)。對給定的N N和和S S，尋找一種刪數(shù)規(guī)，尋找一種刪數(shù)

10、規(guī)則使得剩下得數(shù)字組成的新數(shù)最小。則使得剩下得數(shù)字組成的新數(shù)最小。 例如：例如：N=956742845689012N=956742845689012，S=3S=3時時 最小的結(jié)果為：最小的結(jié)果為：542845689012542845689012http:/ 這是一道運(yùn)用貪心策略求解的典型問題。這是一道運(yùn)用貪心策略求解的典型問題。此題所需處理的數(shù)據(jù)從表面上看是一個整數(shù)，此題所需處理的數(shù)據(jù)從表面上看是一個整數(shù)，通過對此題分析可以將所給出的高精度正整數(shù)通過對此題分析可以將所給出的高精度正整數(shù)看作由若干個數(shù)字所組成的一串字符，這是求看作由若干個數(shù)字所組成的一串字符，這是求解本題的一個重要手段。解本題的

11、一個重要手段。貪心策略：貪心策略： 如果前面的數(shù)字大于后面的數(shù)字，則應(yīng)如果前面的數(shù)字大于后面的數(shù)字，則應(yīng)該將此數(shù)字刪除；直到刪除該將此數(shù)字刪除；直到刪除s s個數(shù)為止。個數(shù)為止。例例2：部分背包問題：部分背包問題 從從n件不同價(jià)值、不同重量的物品中件不同價(jià)值、不同重量的物品中選取選取一部分一部分，在不超過規(guī)定重量的原則下，使該部，在不超過規(guī)定重量的原則下，使該部分價(jià)值最大。分價(jià)值最大。 貪心策略：貪心策略： 先計(jì)算每種物品單位重量的價(jià)值；用貪心先計(jì)算每種物品單位重量的價(jià)值；用貪心選擇策略選擇策略盡可能多的將單位重量價(jià)值高的物品盡可能多的將單位重量價(jià)值高的物品裝入背包裝入背包，如果這種物品全部裝

12、入背包后，背，如果這種物品全部裝入背包后，背包內(nèi)物品的總重量未達(dá)到背包的容量，再選擇包內(nèi)物品的總重量未達(dá)到背包的容量，再選擇次高的物品裝入背包，依此下去次高的物品裝入背包，依此下去。例例3：數(shù)列極差問題：數(shù)列極差問題 在黑板上寫了在黑板上寫了N個正整數(shù)作成的一個數(shù)列，個正整數(shù)作成的一個數(shù)列，進(jìn)行如下操作：進(jìn)行如下操作： 每一次擦去其中的兩個數(shù)每一次擦去其中的兩個數(shù)a和和b，然后在數(shù)，然后在數(shù)列中加入一個數(shù)列中加入一個數(shù)ab+1，如此下去直至黑板上，如此下去直至黑板上剩下一個數(shù)。剩下一個數(shù)。 在所有按這種操作方式最后得到的數(shù)中，在所有按這種操作方式最后得到的數(shù)中，最大的最大的max，最小的為，最

13、小的為min，則該數(shù)列的極差，則該數(shù)列的極差定義為定義為M=max-min。 任務(wù)：對于給定的數(shù)列，編程計(jì)算出極差任務(wù)：對于給定的數(shù)列，編程計(jì)算出極差M。 算法分析：算法分析： 1、求、求max與求與求min是兩個相似的過程。下面是兩個相似的過程。下面把求解把求解max與與min的過程分開，著重探討求解的過程分開，著重探討求解max的問題。的問題。 2、假設(shè)有、假設(shè)有3個數(shù)：個數(shù)：a、b和和max，并且假設(shè)它，并且假設(shè)它們存在關(guān)系：們存在關(guān)系：maxab，此時有三種求值方式，此時有三種求值方式，設(shè)其所求值分別為設(shè)其所求值分別為z1，z2，z3 則有則有: z1=(ab+1)max+1 z2=(

14、bmax+1)a+1 z3=(amax+1)b+1 因?yàn)橐驗(yàn)? z1-z2=max-a=0，z1-z3= max-b=0 z2-z3=a-b=0即即: z1=z2=z3 貪心策略：貪心策略： 若使第若使第K (1KN-1) 次變換后所得值最大，次變換后所得值最大，必使第必使第k-1次變換后所得值最大。次變換后所得值最大。 在進(jìn)行第在進(jìn)行第K次變換時，只需取在進(jìn)行次變換時，只需取在進(jìn)行K-1次次變換后所得數(shù)列中的兩最小數(shù)變換后所得數(shù)列中的兩最小數(shù)p和和q施加操作：施加操作：ppq+1即可。即可。例例4 4：找零錢問題：找零錢問題 一個小孩買了價(jià)值少于一個小孩買了價(jià)值少于1 1美元的糖，并將美元的

15、糖，并將1 1美元的錢交給售貨員。售貨員希望用數(shù)目最少美元的錢交給售貨員。售貨員希望用數(shù)目最少數(shù)目硬幣找給小孩。假設(shè)提供了面值為數(shù)目硬幣找給小孩。假設(shè)提供了面值為2525美分、美分、1010美分、美分、5 5美分、及美分、及1 1美分的硬幣。美分的硬幣。貪心策略：貪心策略： 售貨員分步驟組成要找的零錢數(shù)，每次加售貨員分步驟組成要找的零錢數(shù)，每次加入一個硬幣。每一次應(yīng)選擇使用小于等于零錢入一個硬幣。每一次應(yīng)選擇使用小于等于零錢的最大價(jià)值的硬幣。的最大價(jià)值的硬幣。例例4 4：事件序列問題：事件序列問題 已知已知N N個事件的發(fā)生時刻和結(jié)束時刻。例如個事件的發(fā)生時刻和結(jié)束時刻。例如下表中的一些在時間

16、上沒有重疊的事件，可以下表中的一些在時間上沒有重疊的事件，可以構(gòu)成一個事件序列，如事件構(gòu)成一個事件序列，如事件22，8 8，1010。 事件序列包含的事件數(shù)目，稱為該事件序事件序列包含的事件數(shù)目，稱為該事件序列的長度。請找出一個最長的事件序列。列的長度。請找出一個最長的事件序列。問題分析問題分析2：如果在可能的事件如果在可能的事件a1a2an中中選取在時間上不重疊的最長序列，那么最長序選取在時間上不重疊的最長序列，那么最長序列中一定存在包含結(jié)束最早的事件。列中一定存在包含結(jié)束最早的事件。問題分析問題分析1： 不妨用不妨用Bi和和E i表示事件表示事件i的開始時刻和結(jié)的開始時刻和結(jié)束時刻。則題的要求就是找一個最長的序列：束時刻。則題的要求就是找一個最長的序列： a1a2an，滿足：，滿足： Ba1E a1=Ba2E a2= B an=M，那么顯然用，那么顯然用M條長度為條長度為1的線段的線段可以覆蓋住所有的區(qū)間，所求的線段總長為可以覆蓋住所有的區(qū)間，所求的線段總長為M。2、如果、如果N=1，那么顯然所需線段總長為？，那么顯然所需線段總長為？ 如果如果N=2，相當(dāng)于，相當(dāng)于N=1的情況下從某處斷開的情況下從某處斷開（從哪兒斷開呢？）（從哪兒斷開呢？） 如果如果N=k呢？呢？