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

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

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

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

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

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

Total:=0;ForI:=1toNdobegin {對N行進行選擇}

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

Total:=Total+K；

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

部分背包問題

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

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

因此我們非常容易設計出如下算法：問題初始化； {讀入數(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ù)題設條件，找到了貪心選擇標準(Vi)，并依據(jù)這個標準直接逐步去求最優(yōu)解小結利用貪心策略解題，需要解決兩個問題：首先，確定問題是否能用貪心策略求解；一般來說，適用于貪心策略求解的問題具有以下特點：①

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

0-1背包問題

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

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

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

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

分析

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

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

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

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

貪心算法存在問題

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

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

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

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