第4章 貪心算法

第4章貪心算法找錢問題：假設(shè)有四種硬幣，它們的面值分別是二角五分、一角、五分和一分，現(xiàn)在找給某顧客四角七分錢，該如何找零使得所找錢的硬幣數(shù)最少？

從最大面值的幣種開始，按遞減的順序考慮各幣種，先盡量用大面值的幣種，當(dāng)不足大面值幣種的金額時(shí)才去考慮下一種較小面值的幣種。這就是在使用貪婪法：作出在當(dāng)前看來是最好的選擇，即貪心算法并不從整體最優(yōu)上考慮，而只考慮當(dāng)前（局部）最優(yōu)。貪心算法顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。圖的最小生成樹：Prim算法

從圖的一個(gè)指定的頂點(diǎn)出發(fā)，用V表示樹頂點(diǎn)集，初始只有那個(gè)指定的頂點(diǎn)；E表示最終最小生成樹中有的邊的集合，初始是空集。從V中的頂點(diǎn)出發(fā)，找到從這個(gè)頂點(diǎn)出發(fā)的權(quán)值最小的邊，如果這條邊不構(gòu)成回邊，那么選入最小生成樹，并將這條邊加到E集合中，邊的另一端結(jié)點(diǎn)加入到V集合中。這樣一直循環(huán)到V中的頂點(diǎn)為圖的所有頂點(diǎn)為止，最小生成樹就存在E集合里面了。Kruskal算法

從邊的角度出發(fā)，每一次將圖中的權(quán)值最小的邊取出來，在不是回邊，也就是說不構(gòu)成環(huán)的情況下，將邊加入最小生成樹中，重復(fù)這個(gè)過程，直到所有的圖中所有的點(diǎn)都加入到最小生成樹中結(jié)束。單起點(diǎn)最短路徑問題：Dijkstra算法：的輸入就是一個(gè)連通圖，再加上一個(gè)頂點(diǎn)s。輸出對于圖中所有頂點(diǎn)來說從起始頂點(diǎn)s到它們的最短路徑長度和路徑上的倒數(shù)第二個(gè)頂點(diǎn)。和最大在N行M列的正整數(shù)矩陣中，要求從每行中選出1個(gè)數(shù)，使得選出的總共N個(gè)數(shù)的和最大。

分析分析：要使總和最大，則每個(gè)數(shù)要盡可能大，自然應(yīng)該選每行中最大的那個(gè)數(shù)。因此，我們設(shè)計(jì)出如下算法:

讀入N,M,矩陣數(shù)據(jù)；

Total:=0;ForI:=1toNdobegin {對N行進(jìn)行選擇}

選擇第I行最大的數(shù),記為K；

Total:=Total+K；

End；輸出最大總和Total；小結(jié)從上例中我們可以看出，和遞推法相仿，貪心法也是從問題的某一個(gè)初始解出發(fā)，向給定的目標(biāo)遞推。但不同的是，推進(jìn)的每一步不是依據(jù)某一固定的遞推式，而是做一個(gè)局部的最優(yōu)選擇，即貪心選擇（在例中，這種貪心選擇表現(xiàn)為選擇一行中的最大整數(shù)），這樣，不斷的將問題歸納為若干相似的子問題，最終產(chǎn)生出一個(gè)全局最優(yōu)解。特別注意的是是，局部貪心的選擇是否可以得出全局最優(yōu)是能否采用貪心法的關(guān)鍵所在。對于能否使用貪心策略，應(yīng)從理論上予以證明。下面我們看看另一個(gè)問題。

部分背包問題

給定一個(gè)最大載重量為M的卡車和N種食品，有食鹽，白糖，大米等。已知第i種食品的最多擁有Wi公斤，其商品價(jià)值為Vi元/公斤，編程確定一個(gè)裝貨方案，使得裝入卡車中的所有物品總價(jià)值最大。

分析分析：因?yàn)槊恳粋€(gè)物品都可以分割成單位塊，單位塊的利益越大顯然總收益越大，所以它局部最優(yōu)滿足全局最優(yōu)，可以用貪心法解答，方法如下：先將單位塊收益按從大到小進(jìn)行排列，然后用循環(huán)從單位塊收益最大的取起，直到不能取為止便得到了最優(yōu)解。

因此我們非常容易設(shè)計(jì)出如下算法：問題初始化； {讀入數(shù)據(jù)}

按Vi從大到小將商品排序；

I:=1;repeatifM=0thenBreak; {如果卡車滿載則跳出循環(huán)}M:=M-Wi;ifM>=0then將第I種商品全部裝入卡車

else

將(M+Wi)重量的物品I裝入卡車;I:=I+1; {選擇下一種商品}until(M<=0)OR(I>=N)

在解決上述問題的過程中，首先根據(jù)題設(shè)條件，找到了貪心選擇標(biāo)準(zhǔn)(Vi)，并依據(jù)這個(gè)標(biāo)準(zhǔn)直接逐步去求最優(yōu)解小結(jié)利用貪心策略解題，需要解決兩個(gè)問題：首先，確定問題是否能用貪心策略求解；一般來說，適用于貪心策略求解的問題具有以下特點(diǎn)：①

可通過局部的貪心選擇來達(dá)到問題的全局最優(yōu)解。運(yùn)用貪心策略解題，一般來說需要一步步的進(jìn)行多次的貪心選擇。在經(jīng)過一次貪心選擇之后，原問題將變成一個(gè)相似的，但規(guī)模更小的問題，而后的每一步都是當(dāng)前看似最佳的選擇，且每一個(gè)選擇都僅做一次。小結(jié)②原問題的最優(yōu)解包含子問題的最優(yōu)解，即問題具有最優(yōu)子結(jié)構(gòu)的性質(zhì)。在背包問題中，第一次選擇單位質(zhì)量最大的貨物，它是第一個(gè)子問題的最優(yōu)解，第二次選擇剩下的貨物中單位重量價(jià)值最大的貨物，同樣是第二個(gè)子問題的最優(yōu)解，依次類推。其次，如何選擇一個(gè)貪心標(biāo)準(zhǔn)？正確的貪心標(biāo)準(zhǔn)可以得到問題的最優(yōu)解，在確定采用貪心策略解決問題時(shí)，不能隨意的判斷貪心標(biāo)準(zhǔn)是否正確，尤其不要被表面上看似正確的貪心標(biāo)準(zhǔn)所迷惑。在得出貪心標(biāo)準(zhǔn)之后應(yīng)給予嚴(yán)格的數(shù)學(xué)證明。

0-1背包問題

給定一個(gè)最大載重量為M的卡車和N種動(dòng)物。已知第i種動(dòng)物的重量為Wi，其最大價(jià)值為Vi，設(shè)定M，Wi，Vi均為整數(shù)，編程確定一個(gè)裝貨方案，使得裝入卡車中的所有動(dòng)物總價(jià)值最大。

分析對于N種動(dòng)物，要么被裝，要么不裝，也就是說在滿足卡車載重的條件下，如何選擇動(dòng)物，使得動(dòng)物價(jià)值最大的問題。即確定一組X1，X2，…，Xn，Xi∈{0,1}f(x)=max(∑Xi*Vi)其中，∑(Xi*Wi)≦W從直觀上來看，我們可以按照上例一樣選擇那些價(jià)值大，而重量輕的動(dòng)物。也就是可以按價(jià)值質(zhì)量比（Vi/Wi）的大小來進(jìn)行選擇?？梢钥闯觯孔鲆淮芜x擇，都是從剩下的動(dòng)物中選擇那些Vi/Wi最大的，這種局部最優(yōu)的選擇是否能滿足全局最優(yōu)呢？我們來看看一個(gè)簡單的例子：設(shè)N=3，卡車最大載重量是100，三種動(dòng)物A、B、C的重量分別是40，50，70，其對應(yīng)的總價(jià)值分別是80、100、150。1)情況A：按照上述思路，三種動(dòng)物的Vi/Wi分別為2,2,2.14。顯然，我們首先選擇動(dòng)物C，得到價(jià)值150，然后任意選擇A或B，由于卡車最大載重為100，因此卡車不能裝載其他動(dòng)物。2)情況B：不按上述約束條件，直接選擇A和B?？梢缘玫絻r(jià)值80+100=180，卡車裝載的重量為40+50=90。沒有超過卡車的實(shí)際載重，因此也是一種可行解，顯然，這種解比上一種解要優(yōu)化。問題出現(xiàn)在什么地方呢？我們看看圖圖23卡車裝載貨物情況分析從圖23中明顯可以看出，情況A，卡車的空載率比情況B高。也就是說，上面的分析，只考慮了貨物的價(jià)值質(zhì)量比，而沒有考慮到卡車的運(yùn)營效率，因此，局部的最優(yōu)化，不能導(dǎo)致全局的最優(yōu)化。因此，貪心不能簡單進(jìn)行，而需要全面的考慮，最后得到證明。地圖著色

要求相鄰的區(qū)域用不同的顏色，顏色盡量少地圖著色（2）要求給出最少的著色分組的地圖。著色最優(yōu)解問題。窮舉法或回溯法來解決地圖著色問題。對于小型地圖可以使用對于大型地圖，由于時(shí)間的指數(shù)上升，不可接受往往通過一些逼近方法來求近似最優(yōu)解地圖著色：貪心法用一種顏色給盡可能多的頂點(diǎn)著色選擇某未著色的頂點(diǎn)并用該新顏色上色掃描未著色的其他各頂點(diǎn)，考察它們是否有邊與該顏色著色的頂點(diǎn)相連，若沒有邊相連就用該顏色上色。換一種顏色重復(fù)前一步驟直到所有頂點(diǎn)全部著色為止貪心法近似解按1、2、3、4、5順序著色最優(yōu)解排隊(duì)打水問題

有N個(gè)人排隊(duì)到R個(gè)水龍頭去打水，他們裝滿水桶的時(shí)間為T1，T2，…，Tn為整數(shù)且各不相等，應(yīng)如何安排他們的打水順序才能使他們花費(fèi)的時(shí)間最少？

分析

由于排隊(duì)時(shí)，越靠前面的計(jì)算的次數(shù)越多，顯然越小的排在越前面得出的結(jié)果越?。梢杂脭?shù)學(xué)方法簡單證明，這里就不再贅述），所以這道題可以用貪心法解答，基本步驟：(1)

將輸入的時(shí)間按從小到大排序；(2)

將排序后的時(shí)間按順序依次放入每個(gè)水龍頭的隊(duì)列中；(3)

統(tǒng)計(jì)，輸出答案。哈夫曼編碼書上例題貪心算法的優(yōu)勢貪心算法所作的選擇可以依賴于以往所作過的選擇，但決不依賴于將來的選擇，也不依賴于子問題的解，因此貪心算法與其它算法相比具有一定的速度優(yōu)勢。如果一個(gè)問題可以同時(shí)用幾種方法解決，貪心算法應(yīng)該是最好的選擇之一。

貪心算法存在問題

1.不能保證求得的最后解是最佳的；

2.不能用來求最大或最小解問題；

3.只能求滿足某些約束條件的可行解的范圍。

區(qū)別1動(dòng)態(tài)規(guī)劃法先求子問題的解，然后通過求解子問題構(gòu)造原問題的解；而貪心算法是直接地解原問題。區(qū)別2動(dòng)態(tài)規(guī)劃法通過對若干局部最優(yōu)解的比較，去掉了次優(yōu)解，從而產(chǎn)生了更高一層次的局部最優(yōu)解。相當(dāng)于對較低層次的局部最優(yōu)解進(jìn)行貪心的選擇而得到高一級的局部最優(yōu)解，因而最終產(chǎn)生一個(gè)最高層次的局部最優(yōu)解。而貪心法每階段只作一個(gè)挑選，各階段的解一經(jīng)選出就固定不變了，后階段的局部最優(yōu)是基于前階段的挑選，所以往往只能求出次優(yōu)解