最優裝載貪心演算法

1. 貪心演算法及其應用

求解一個問題時有多個步驟，每個步驟都選擇當下最優的那個解，而不用考慮整體的最優解。通常，當我們面對的問題擁有以下特點的時候，就可以考慮使用貪心演算法。

比如，我們舉個例子，倉庫裡面總共有五種豆子，其對應的重量和總價值如下，現在我們有一個可以裝100KG重量的袋子，怎麼裝才能使得袋子中的豆子價值最大？

我們首先看看這個問題是否符合貪心演算法的使用場景？限制值是袋子100KG，期望值是袋子裡面的價值最高。所以是符合的。那麼我們嘗試著應用下貪心演算法的方法，每一個步驟都尋找當下的最優解，怎麼做呢？

把倉庫裡面的每種豆子價值除以重量，得出每種豆子的單價，那麼當下的最優解，肯定是盡可能最多地裝單價最貴的，也就是先把20KG的黃豆都裝上，然後再把30KG的綠豆都裝上，再裝50KG的紅豆，那麼此時正好裝滿袋子，總價值將是270元，這就是通過貪心演算法求解的答案。

貪心演算法的應用在這個問題上的求解是否是最優解需要一個很復雜的數學論證，我們不用那樣，只要心裡舉幾個例子，驗證下是否比它更好即可，如果舉不出例子，那麼就可以認為這就是最優解了。

雖然貪心演算法雖然在大部分實踐場景中都能得到最優解，但是並不能保證一定是最優解。比如在如下的有向帶權圖中尋找從S到T的最短路徑，那麼答案肯定就是S->A->E->T，總代價為1+4+4=9；

然而，實際上的最短路徑是S->B->D->T，總代價為6。

所以，不能所有這類問題都迷信貪心演算法的求解，但其作為一種演算法指導思想，還是很值得學習的。

除了以上袋子裝豆子的問題之外，還有很多應用場景。這種問題能否使用貪心演算法來解決的關鍵是你能否將問題轉換為貪心演算法適用的問題，即找到問題的限制值和期望值。

我們有m個糖果要分給n個孩子，n大於m，註定有的孩子不能分到糖果。其中，每個糖果的大小都不同，分別為S1,S2,S3...,Sm，每個孩子對糖果的需求也是不同的，為N1,N2,N3...,Nn，那麼我們如何分糖果，才能盡可能滿足最多數量孩子的需求？

這個問題中，限制值是糖果的數量m，期望值滿足最多的孩子需求。對於每個孩子，能用小的糖果滿足其需求，就不要用大的，避免浪費。所以我們可以給所有孩子的需求排個序，從需求最小的孩子開始，用剛好能滿足他的糖果來分給他，以此來分完所有的糖果。

我們有1元、5元、10元、20元、50元、100元紙幣各C1、C5、C10、C20、C50、C100張，現在要購買一個價值K元的東西，請問怎麼才能適用最少的紙幣？

這個問題應該不難，限制值是各個紙幣的張數，期望值是適用最少的紙幣。那麼我們就先用面值最大的100元去付錢，當再加一張100元就超過K時，就更換小面額的，直至正好為K元。

對於n個區間[L1,R1],[L2,R2]...[Ln,Rn]，我們怎麼從中選出盡可能多的區間，使它們不相交？

我們需要把這個問題轉換為符合貪心演算法特點的問題，假設這么多區間的最左端點是Lmin，最右端點是Rmax，那麼問題就是在[Lmin,Rmax]中，選擇盡可能多的區間往裡面塞，並且保證它們不相交。這里，限制值就是區間[Lmin,Rmax]，期望值就是盡可能多的區間。

我們的解決辦法就是每次從區間中選擇那種左端點>=已經覆蓋區間右邊端點的，且該區間右端點盡可能高小的。如此，我們可以讓未覆蓋區間盡可能地大，才能保證可以塞進去盡可能多的區間。

貪心演算法最重要的就是學會如何將要解決的問題抽象成適合貪心演算法特點的模型，找到限制條件和期望值，只要做好這一步，接下來的就比較簡單了。在平時我們不用刻意去記，多多練習類似的問題才是最有效的學習方法。

2. 裝載問題的貪心選擇性質如何證明

設箱子重量從小到大（x1,x2,...,xn），若集合A是最優裝載問題的一個最優解。A中第一個箱子為k。若k=1，A就是一個滿足貪心性質的最優解。假如當k>1，令B=A-{k}+{1},因為Wk>=W1,則B中的總重量小於等於A中的總重量，A是最優解，則B也是最優解，而B是選擇以箱子1為開始的最優解。可知總存在以貪心選擇開始的最優解。

3. 貪心演算法的最優裝載問題

void loading(W[],X[],c,n)
{
for(i=1,i<n,i++)

1.void loading(int W[],int X[],int c,int n)
2.沒有定義i;
3.for（;;）是冒號，非逗號

4. 貪心演算法的本質

1. 貪心法（Greedy Algorithm）定義

求解最優化問題的演算法通常需要經過一系列的步驟，在每個步驟都面臨多種選擇；

貪心法就是這樣的演算法：它在每個決策點作出在當時看來最佳的選擇，即總是遵循某種規則，做出局部最優的選擇，以推導出全局最優解（局部最優解->全局最優解）

2. 對貪心法的深入理解

（1）原理：一種啟發式策略，在每個決策點作出在當時看來最佳的選擇

（2）求解最優化問題的兩個關鍵要素：貪心選擇性質+最優子結構

①貪心選擇性質：進行選擇時，直接做出在當前問題中看來最優的選擇，而不必考慮子問題的解；

②最優子結構：如果一個問題的最優解包含其子問題的最優解，則稱此問題具有最優子結構性質

（3）解題關鍵：貪心策略的選擇

貪心演算法不是對所有問題都能得到整體最優解的，因此選擇的貪心策略必須具備無後效性，即某個狀態以前的過程不會影響以後的狀態，只與當前狀態有關。

（4）一般步驟：

①建立數學模型來描述最優化問題；

②把求解的最優化問題轉化為這樣的形式：對其做出一次選擇後，只剩下一個子問題需要求解；

③證明做出貪心選擇後：

1°原問題總是存在全局最優解，即貪心選擇始終安全；

2°剩餘子問題的局部最優解與貪心選擇組合，即可得到原問題的全局最優解。

並完成2°

3. 貪心法與動態規劃

最優解問題大部分都可以拆分成一個個的子問題，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，大部分情況下這是不可行的。貪心演算法和動態規劃本質上是對子問題樹的一種修剪，兩種演算法要求問題都具有的一個性質就是子問題最優性(組成最優解的每一個子問題的解，對於這個子問題本身肯定也是最優的)。動態規劃方法代表了這一類問題的一般解法，我們自底向上構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，並且以其中的最優值作為自身的值，其它的值舍棄。而貪心演算法是動態規劃方法的一個特例，可以證明每一個子樹的根的值不取決於下面葉子的值，而只取決於當前問題的狀況。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。由於貪心演算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優的路，一直走到底就可以了。

5. 如何證明最優裝載問題具有貪心選擇性質

設某種貨幣系統為(1,5,10,25)四種幣值(單位:元)，要用最少的幣數找出 n元錢，
問:能否用貪心演算法進行求解，並證明。(不要求寫演算法) 參考解答:貪心性質(最大面額優先選最多)證明:
對 n<=25的情況，易由窮舉得證。
當 n>25時，設 n=1*a1+5*a2+10*a3+25*a4
為了使 a1+a2+a3+a4最小，易知:
a1<5，若 a1>=5，可將 5個 1元兌換為 1個 5元，幣數減少。
a2<2，若 a2>=2，可將 2個 5元兌換為 1個 10元，幣數減少。
當 a2=0時，a3<3，若 a3>=3，可將 3個 10元兌換為 1個 5元和 1個 25元，幣數減 少。
當 a2>0時，a3<2，若 a2>=2，可將 1個 5元和 2個 10元兌換為 1個 25元，幣數減 少。
即，為了使 a1+a2+a3+a4最小，所使用的 1、5、10元幣的幣數的上限為: a1=4,a2=0,a3=2或 a1=4,a2=1,a3=1
則所使用的 1、5、10元幣的幣值上限為:
4*1+0*5+2*10=24或 4*1+1*5+1*10=19
均不超過 25，因此，為了使 a1+a2+a3+a4最小，應使 a4達到最大。貪心選擇性質得 證。
最優子結構性質證明:
當 a4的值確定後，為了使 a1+a2+a3+a4達到最小，須使 a1+a2+a3達到最小，仍為同 型的最優問題。

6. 貪心演算法——最優裝載

•貪心演算法的特點是每個階段所作的選擇都是局部最優的，它期望通過所作的局部最優選擇產生出一個全局最優解。

貪心與動態規劃： 與動態規劃不同的是，貪心是 鼠目寸光 ；動態規劃是 統攬全局 。

–動態規劃：每個階段產生的都是全局最優解

•第i階段的「全局」： 問題空間為(a1, … , ai)

•第i階段的「全局最優解」：問題空間為 (a1, … , ai)時的最優解

–貪心：每個階段產生的都是局部最優解

•第i階段的「局部」：問題空間為按照貪心策略中的優先順序排好序的第i個輸入ai

•第i階段的「局部最優解」： ai

•貪心選擇性質：所求問題的全局最優解可以通過一系列局部最優的選擇（即貪心選擇）來達到。

–這是貪心演算法與動態規劃演算法的主要區別。

•最優子結構性質：當原問題的最優解包含子問題的最優解時，稱此問題具有最優子結構性質。

最優子結構性質是該問題可用動態規劃演算法或貪心演算法求解的關鍵特徵

首先證明該問題具有貪心選擇性質和最優子結構性質

1.最輕者先裝一定是整體最優解，滿足貪心選擇

2.該問題的子問題仍是最優解，滿足最優子結構