一、貪心算法基本思想

1. 貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從
   整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇。

2. 我們希望貪心算法得到的最終結果也是整體最優的。雖然貪心算法不
   能對所有問題都得到整體最優解（Optimal Solution），但對許多問
   題它能產生整體最優解。如單源最短路經問題，最小生成樹問題等。

3. 某些情況下，即使貪心算法不能得到整體最優解，但通常能獲得近似
   最優解（Near-Optimal Solution）。

4. 貪心算法有兩個基本要素：
   貪心選擇性質
   最優子結構性質

二、簡單案例

2.1. 找零錢問題

【問題描述】找零錢時，每次盡可能地選取最大面額的鈔票
實例：
10元?3元=7元，找零：5 + 2
100元?3元=97元，找零：50 + 20 + 20 + 5 + 2
100元?14元=86元，找零：50 + 20 + 10 + 5 + 1 （沒有更優的找錢方案）

最優性證明：

1. 若x的值為1, 2, 5，那么所需的零錢為1張，這顯然是最少的。
2. 否則，所需的錢數至少為2張。算法對3, 4, 6, 7生成的找錢方案分別為 2+1, 2+2, 5+1, 5+2，這顯然也是最少的。
3. 若x的值為8 和 9，算法生成的找錢方案分別為5+2+1和5+2+2；而用 2 張鈔票不能找出8元或9元的零錢，因此算法的結果也是最少的。

如果將x的值擴大到100以內，并增加面值為50, 20和10元的鈔票，那么使用貪心算法仍然能夠得到最優的找零錢方案，即每次盡可能地選取最大面額的零鈔。

在找零問題每一步的貪心選擇中，在不超過應付款金額的條件下，只選擇面值最大的貨幣，而不去考慮在后面看來這種選擇是否合理，而且它還不會改變決定：一旦選出了一張貨幣，就永遠選定。

找零問題的貪心選擇策略是盡可能使付出的貨幣最快地滿足支付要求，其目的是使付出的貨幣張數最慢地增加，這正體現了貪心法的設計思想。

三、貪心算法

貪心算法：在問題求解的過程中采用“貪婪”的策略來構造目標解。
實現起來較為簡單，難點通常在于算法的正確性證明。

可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質：貪心選擇性質和最優子結構性質。

3.1. 貪心算法的基本要素

3.1.1.貪心選擇性質，與動態規劃的區別和共同點

所謂貪心選擇性質是指所求問題的整體最優解可以通過一系列局部最優的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態規劃算法的主要區別。

動態規劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規模更小的子問題。

對于一個具體問題，要確定它是否具有貪心選擇性質，必須證明每一步所作的貪心選擇最終導致問題的整體最優解。

3.1.2. 最優子結構性質

當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構性質。
問題的最優子結構性質是該問題可用動態規劃算法或貪心算法求解的關鍵特征。

貪心算法和動態規劃算法都要求問題具有最優子結構性質，這是兩類算法的一個共同點。

四、案例

4.1 背包問題

【0-1背包問題】

1. 給定n種物品和一背包。物品i的重量是wi，其價值為vi，背包的容量為C。
2. 問題：應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大
3. 物品i給要么裝入背包，要么不裝入背包。不能部分裝入、不能裝入多次。

【背包問題】
與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i
的一部分，而不一定要全部裝入背包，1≤i≤n 。

這兩類問題都具有最優子結構性質，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。

4.1.1用貪心算法解背包問題的基本步驟

首先計算每種物品單位重量的價值vi / wi；然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。

void Knapsack(int n,float M,float v[],float w[],float x[])
{Sort(n,v,w);int i;for (i=1;i<=n;i++) x[i]=0;float c=M;for (i=1;i<=n;i++) {if (w[i]>c) break;x[i]=1;c-=w[i];}if (i<=n) x[i]=c/w[i];
}

算法knapsack的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為O(nlogn)

為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質。

4.1.2 背包問題 示例

0-1背包問題：
有三種物品，背包容量為50公斤。物品1重10公斤，價值60元，物品2重20公斤，價值100元，物品3重30公斤，價值120元。因此，物品1每公斤價值6元，物品2每公斤價值5元，物品3每公斤價值4元。

若依貪心選擇策略，應首先物品1裝入背包，然后裝入物品2。然而從圖b的可以看出，最優選擇方案是選擇物品2和3裝入背包。首選物品1的方案不是最優的。

對于背包問題，貪心選擇最終可得到最優解，其選擇方案如圖c所示

分析：
對于0-1背包問題，貪心選擇之所以不能得到最優解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。

事實上，在考慮0-1背包問題時，應比較選擇該物品和不選擇該物品所導致的最終方案，然后再作出最好選擇。由此就導出許多互相重疊的子問題。這正是該問題可用動態規劃算法求解的另一重要特征。

實際上也是如此，動態規劃算法可以有效地解0-1背包問題。

背包問題示例
有一個背包，背包容量是M=150。有7個物品，物品的重量及價值見下表。物品可以分割成任意大小。
要求盡可能讓裝入背包中的物品總價值最大，但不能超過總容量。

如果分別采用以下貪心策略求解，是否可以得到最優解？
（1）每次挑選價值最大的物品裝入背包
（2）每次挑選所占重量最小的物品裝入背包
（3）每次選取單位重量價值最大的物品裝入背包

貪心算法是常見的算法之一，這是由于它簡單易行，構造貪心策略不是很困難。但是，它需要證明后才能真正運用到題目的算法中。

一般來說，貪心算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。（最優子結構性質）

4.2 活動安排問題

【問題描述】 活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合。

設有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結束時間fi,且si <fi。如果選擇了活動i，則它在半開時間區間[si, fi)內占用資源。若區間[si, fi)與區間[sj, fj)不相交，則稱活動i與活動j是相容的。也就是說，當si≥fj或sj≥fi時，活動i與活動j相容。

活動安排問題就是要在某一時間段安排盡可能多的活動。

活動安排問題是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。

貪心策略：每次選擇具有最早完成時間的相容活動，使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。

實例：設待安排的11個活動的開始時間和結束時間按結束時間的非減序排列如下

下圖中每行相應于一次迭代。陰影長條表示的活動是已選入集合的活動，而空白長條表示的活動是當前正在檢查相容性的活動。

貪心算法偽代碼：

void GreedySelector(int n, s[], f[], boolean a[])
{a[1]=true;int j=1;for (int i=2;i<=n;i++) {if (s[i]>=f[j]) {a[i]=true;j=i;}else a[i]=false;}
}

【算法正確性證明】
若被檢查的活動i的開始時間si小于最近選擇的活動j的結束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。

貪心算法并不總能求得問題的整體最優解。但對于活動安排問題，貪心算法greedySelector 卻總能求得的整體最優解，即它最終所確定的相容活動集合A的規模最大。這個結論可以用數學歸納法證明

【算法效率】
當輸入的活動已按結束時間的非減序排列，算法GreedySelector只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。

如果所給出的活動未按結束時間非減序排列，可以用O(nlogn)的時間先排序，然后再使用算法GreedySelector安排活動。

4.3 最大裝載問題

【問題描述】輸入：總重量限制W，以及n個物品的重量A = {a0, a1,… ,an?1}輸出：A的一個子集A*，其和不大于W，且元素數量盡可能大

每次盡可能地選取重量最小的物品

實例：
W = 1000, A = {400, 350, 300, 250, 240, 180, 150, 120}
選取 120 + 150 + 180 + 240 + 250

最大裝載問題貪心算法偽代碼：

Algorithm MaxLoad(int W; int A[])
beginSort(A); // 將物品按重量排序  O(nlogn)let i = 0;while (W>0) doif (A[i] ≤ W) then  // O(n)W <- W - A[i];i <- i + 1;return A[0..i];
end

4.4 哈夫曼編碼

解決數據壓縮問題（如何采取有效的數據壓縮技術來節省數據文件的存儲空間和傳輸時間）

在數據通信、數據壓縮問題中，需要將數據文件轉換成由二進制字符0、1組成的二進制串，稱之為編碼

如何設計有效的用于數據壓縮的二進制編碼？（一般等長編碼方案并不是最優的編碼方案。）

因為每個字符出現的頻率不同。如果在編碼時考慮字符出現的頻率，使頻率高的字符采用盡可能短的編碼，頻率低的字符采用稍長的編碼，則會獲得更好的空間效率。

考慮到解碼問題，若要設計長短不等的編碼，任何一個字符的編碼都不能是其它字符的編碼的前綴。這種編碼稱之為前綴碼。

反例：非前綴碼的例子
a: 001, b: 00, c: 010, d: 01
解碼存在歧義，例如字符串 0100001
解碼1: 01, 00, 001 可以解讀為 d, b, a
解碼2: 010, 00, 01 可以解讀為 c, b, d

4.4.1 前綴碼的二叉樹表示

示例：前綴碼：{00000, 00001, 0001, 001, 01,100,101,11}
給定字符集C={x1,x2 ,…,xn } 和每個字符的頻率f(xi) ，i=1,2,…,n。字符集C的一個前綴碼編碼方案對應于一顆二叉樹T。字符xi在樹T中的深度記為d(xi)，d(xi)稱為字符xi的前綴碼長。

該編碼方案的平均碼長定義為

平均碼長亦稱作平均傳輸位數

【問題】 給定字符集C={x1,x2 ,…,xn } 和每個字符的頻率f(xi) ，i=1,2,…,n. 。求關于C 的一個最優前綴碼（平均碼長最小）。

哈夫曼(Huffman)提出了構造最優前綴碼的貪心算法，由此產生的編碼方案稱為哈夫曼編碼。
哈夫曼算法以自底向上的方式構造表示最優前綴碼的二叉樹T。算法以|C|個葉結點開始，執行|C|－1次的“合并”運算后產生最終所要求的樹T。

哈夫曼算法偽碼：

示例：字符串C包含字符及出現次數為：a:45; b:13; c:12; d:16; e:9; f:5。

深度: a:1; b:3; c:3; d:3; e:4; f:4

0 - 左子樹
1 - 右子樹
碼對應一片樹葉

平均碼長: 4×(0.05+0.09)+3×(0.16+0.12+0.13)+1×0.45=2.24

哈夫曼編碼 正確性證明
【引理1】 設C是字符集，C中任一字符c的頻率為f?。假設x,y∈C,且f(x), f(y) 是頻率中最小的兩個, 那么存在最優二元前綴碼使得 x, y具有相同碼長且僅在最后一位編碼不同。

引理1的證明思路：設二叉樹T表示字符集C的一個最優前綴碼。如果對T做適當修改后得到一顆新的二叉樹T’，使得在新樹中，x和y 是最深葉子且為兄弟。同時，新樹T’表示的前綴碼也是C的最優前綴碼。如此即可證明引理1。

【引理2】 設T是字符集C的一個最優前綴碼的完全二叉樹。C中任一字符c的頻率為f?。假設x和y是C中樹T的兩個葉子且為兄弟, z是它們的父親。若將z看作是具有頻率f(z) =f(x)+ f(y) 的字符,則樹T’=T-{x, y}表示的字符集C’=C- {x, y}∪{z}的一個最優前綴碼。

4.5 單源最短路徑

【問題描述】 給定帶權有向圖G =(V,E,W)，其中每條邊e=<i,j>的權w(e)是非負實數，表示從i到j的距離。另外，給定V中的一個頂點s，稱為源。現在要計算從源s到所有其他各頂點的最短路徑。這個問題通常稱為單源最短路徑問題。

源點：1

Dijkstra算法是求解單源最短路徑問題的一個貪心算法。

【算法基本思想】：
設置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。

1. 初始時，S中僅含有源。
2. 設u是G的某一個頂點，把從源到u且中間只經過S中頂點的路稱為從源到u的特殊路徑，并用數組dist記錄當前每個頂點所對應的最短特殊路徑長度。
3. Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u
   添加到S中，同時對數組dist作必要的修改。
4. 一旦S包含了所有V中頂點，dist就記錄了從源到所有其他頂點之間
   的最短路徑長度。

輸入：有向圖G =(V,E,W)，V={1,2,…,n}, s=1
輸出：從源s到所有其他各頂點的最短路徑

【 Dijkstra算法設計思想】

1. 初始S={1}
2. 對于i∈V?S ， 計算1到i 的相對 S 的最短路，長度 dist [i]
3. 選擇 V?S 中的dist值最小的j，將j加入S，修改V?S中頂點的dist值
4. 繼續上述過程，直到 S=V

Dijkstra算法 偽碼：

輸入：有向圖G =(V,E,W)，V={1,2,3,4,5,6}, s=1



Dijkstra算法 正確性證明：
證明對于i∈V, dist[i]=short[i]

歸納法證明Dijkstra算法
首先證明第1步時，Dijkstra算法成立。接下來，假設Dijkstra算法進行到第k 步時命題成立，歸納證明k+1時命題也成立。

(1) k=1時，S={s}, dist [s]=short[s]=0。
(2) 假設Dijkstra算法進行到第k 步時命題成立，k+1步時選擇頂點v(邊<u,v>)。需要證明dist [v]=short[v]。若存在另一條 s-v 路徑 L ( 綠色) ，最后一次出 S 的頂點為x, 經過V?S 的第一個頂點 y，再由 y 經過一段在V?S中的路徑到達 v
在k+1步時選擇頂點v而不是y，則dist [v]≤ dist [y] 令y到v的路徑長度為d(y,v) ，則dist [y]+d(y,v)≤L于是dist [v] ≤L，即dist [v]=short[v]。

【算法時間復雜度分析】
對于具有n個頂點和e條邊的帶權有向圖，如果用帶權鄰接矩陣表示這個圖，那么Dijkstra算法的主循環體需要O(n)時間。這個循環需要執行n-1次，所以完成循環需要O(n2)時間。算法的其余部分所需要時間不超過O(n2)。

4.6 最小生成樹

【問題描述】
設G =(V,E)是無向連通帶權圖，即一個網絡。E中每條邊(v,w)的權為c[v][w]。如果G的子圖G’是一棵包含G的所有頂點的樹，則稱G’為G的生成樹。生成樹上各邊權的總和稱為該生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。

Prim算法和Kruskal算法都是應用貪心策略獲得最小生成樹的例子。
盡管這2個算法做貪心選擇的方式不同，但它們都利用了下面的最小生成樹性質：

設G=(V,E)是連通帶權圖，U是V的真子集。如果(u,v)∈E，且u∈U，v∈V ? U，且在所有這樣的邊中，(u,v)的權c[u][v]最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。

最小生成樹 Prim算法：

Prim算法的基本思想：
首先置S={1}，
然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件i∈S，j∈V-S，且c[i][j]最小的邊，將頂點j添加到S中。
這個過程一直進行到S=V時為止。
在這個過程中選取到的所有邊恰好構成G的一棵最小生成樹。

Prim算法 偽代碼：

實例：如圖所示的帶權圖，按Prim算法選取邊的過程如下所示。


在Prim算法中，還應當考慮如何有效地找出滿足條件i∈S, j∈V?S，且權c[i][j]最小的邊(i,j)

實現這個目的的較簡單的辦法是設置2個數組closest和lowcost。
對于每一個j∈V?S，closest[j]是j在S中的鄰接頂點，它與j在S中的其它鄰接頂點k相比較有c[j][closest[j]]≤c[j][k]。lowcost[j]的值就是c[j][closest[j]]。

在Prim算法執行過程中，先找出V ? S中使lowcost值最小的頂點j，然后根據數組closest選取邊(j,closest[j])，最后將j添加到S中，并對closest和lowcost作必要的修改。

用這個辦法實現的Prim算法，算法步驟執行O(n)次，每次找連接S與V-S的最短邊用時O(n)，因此所需的計算時間為O(n2)。

最小生成樹 Kruskal算法

Kruskal算法的基本思想：
首先將G的n個頂點看成n個孤立的連通分支。將所有的邊按權從小到大排序

然后從第一條邊開始，依邊權遞增的順序查看每一條邊，并按下述方法連接2個不同的連通分支：當查看到第k條邊(v,w)時，

1. 如果端點v和w分別是當前2個不同的連通分支T1和T2中的頂點時，就用邊(v,w)將T1和T2連接成一個連通分支，然后繼續查看第k+1條邊；
2. 如果端點v和w在當前的同一個連通分支中，就直接再查看第k+1條邊。
3. 這個過程一直進行到只剩下一個連通分時為止。

Kruskal算法偽代碼：

例如對于如圖所示的帶權圖，按Kruskal算法選取邊的過程如下圖所示。

4.7 多機調度問題

**【問題描述】**多機調度問題要求給出一種作業調度方案，使所給的n個作業在盡可能短的時間內由m臺機器加工處理完成。

約定：每個作業均可在任何一臺機器上加工處理，但未完工前不允
許中斷處理。作業不能拆分成更小的子作業。

這個問題是NP完全問題，到目前為止還沒有有效的解法。對于這一類問題，用貪心選擇策略有時可以設計出較好的近似算法。

1. 當n≤m 時，只要將機器i的[0, ti]時間區間分配給作業i即可，算法只需要O(1)時間
2. 當n>m時，首先將n個作業依其所需的處理時間從大到小排序。然后依此順序將作業分配給空閑的處理機。算法所需的計算時間為O(nlogn)

【示例】設7個獨立作業{1,2,3,4,5,6,7}由3臺機器M1，M2和M3加工處理。各作業所需的處理時間分別為{2,14,4,16,6,5,3}。按貪心算法產生的作業調度如下圖所示，所需的加工時間為17。

五、總結

1. 貪心法適用于組合優化問題。
2. 求解過程是多步判斷過程，最終的判斷序列對應于問題的最優解。
3. 判斷依據某種“短視的”貪心選擇性質，性質的好壞決定了算法的正確性。貪心性質的選擇往往依賴于直覺或者經驗。
4. 貪心法的優勢：算法簡單，時間和空間復雜性低。

貪心法正確性證明方法：
(1) 直接計算優化函數，貪心法的解恰好取得最優值
(2) 數學歸納法（對算法步數或者問題規模歸納）

證明貪心策略不對：舉反例