概念簡介
貪婪算法（Greedyalgorithm）是一種對某些求最優解問題的更簡單、更迅速的設計技術。用貪婪法設計算法的特點是一步一步地進行，常以當前情況為基礎根據某個最佳化測度作最優選擇，而不考慮各種可能的整體情況，它省去了為找最優解要窮盡所有可能而必須耗費的大量時間，它採用自頂向下，以疊代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為一個規模更小的子問題，通過每一步貪心選擇，可得到問題的一個最優解，雖然每一步上都要保證能獲得局部最優解，但由此產生的全局解有時不一定是最優的，所以貪婪法不要回溯。
貪婪算法是一種改進了的分級處理方法。其核心是根據題意選取一種量度標準。然後將這多個輸入排成這種量度標準所要求的順序，按這種順序一次輸入一個量。如果這個輸入和當前已構成在這種量度意義下的部分最佳解加在一起不能產生一個可行解，則不把此輸入加到這部分解中。這種能夠得到某種量度意義下最優解的分級處理方法稱為貪婪算法。
對於一個給定的問題，往往可能有好幾種量度標準。初看起來，這些量度標準似乎都是可取的，但實際上，用其中的大多數量度標準作貪婪處理所得到該量度意義下的最優解並不是問題的最優解，而是次優解。因此，選擇能產生問題最優解的最優量度標準是使用貪婪算法的核心。
一般情況下，要選出最優量度標準並不是一件容易的事，但對某問題能選擇出最優量度標準後，用貪婪算法求解則特別有效。最優解可以通過一系列局部最優的選擇即貪婪選擇來達到，根據當前狀態做出在當前看來是最好的選擇，即局部最優解選擇，然後再去解做出這個選擇後產生的相應的子問題。每做一次貪婪選擇就將所求問題簡化為一個規模更小的子問題，最終可得到問題的一個整體最優解。
特性
貪婪算法可解決的問題通常大部分都有如下的特性：
⑴有一個以最優方式來解決的問題。為了構造問題的解決方案，有一個候選的對象的集合：比如不同面值的硬幣。
⑵隨著算法的進行，將積累起其它兩個集合：一個包含已經被考慮過並被選出的候選對象，另一個包含已經被考慮過但被丟棄的候選對象。
⑶有一個函式來檢查一個候選對象的集合是否提供了問題的解答。該函式不考慮此時的解決方法是否最優。
⑷還有一個函式檢查是否一個候選對象的集合是可行的，也即是否可能往該集合上添加更多的候選對象以獲得一個解。和上一個函式一樣，此時不考慮解決方法的最優性。
⑸選擇函式可以指出哪一個剩餘的候選對象最有希望構成問題的解。
⑹最後，目標函式給出解的值。
為了解決問題，需要尋找一個構成解的候選對象集合，它可以最佳化目標函式，貪婪算法一步一步的進行。起初，算法選出的候選對象的集合為空。接下來的每一步中，根據選擇函式，算法從剩餘候選對象中選出最有希望構成解的對象。如果集合中加上該對象後不可行，那么該對象就被丟棄並不再考慮；否則就加到集合里。每一次都擴充集合，並檢查該集合是否構成解。如果貪婪算法正確工作，那么找到的第一個解通常是最優的。
算法思想
貪心算法——從問題的某一個初始解出發逐步逼近給定的目標，以儘可能快的地求得更好的解。當達到某算法中的某一步不能再繼續前進時，算法停止。
該算法存在問題：
1.不能保證求得的最後解是最佳的；
2.不能用來求最大或最小解問題；
3.只能求滿足某些約束條件的可行解的範圍。
實現該算法的過程：
從問題的某一初始解出發；
while能朝給定總目標前進一步do
求出可行解的一個解元素；
由所有解元素組合成問題的一個可行解；
例題分析
例題1、
[0-1背包問題]有一個背包，背包容量是M=150。有7個物品，物品不可以分割成任意大小。
要求儘可能讓裝入背包中的物品總價值最大，但不能超過總容量。
物品 A B C D E F G
重量 35kg 30kg 6kg 50kg 40kg 10kg 25kg
價值 10$ 40$ 30$ 50$ 35$ 40$ 30$
分析：
目標函式：∑pi最大
約束條件是裝入的物品總重量不超過背包容量：∑wi<=M(M=150）
⑴根據貪心的策略，每次挑選價值最大的物品裝入背包，得到的結果是否最優？
⑵每次挑選所占重量最小的物品裝入是否能得到最優解？
⑶每次選取單位重量價值最大的物品，成為解本題的策略。
值得注意的是，貪心算法並不是完全不可以使用，貪心策略一旦經過證明成立後，它就是一種高效的算法。
貪心算法還是很常見的算法之一，這是由於它簡單易行，構造貪心策略不是很困難。
可惜的是，它需要證明後才能真正運用到題目的算法中。
一般來說，貪心算法的證明圍繞著：整個問題的最優解一定由在貪心策略中存在的子問題的最優解得來的。
對於例題中的3種貪心策略，都是無法成立（無法被證明）的，解釋如下：
⑴貪心策略：選取價值最大者。
反例：
W=30
物品：A B C
重量：28 12 12
價值：30 20 20
根據策略，首先選取物品A，接下來就無法再選取了，可是，選取B、C則更好。
⑵貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。
⑶貪心策略：選取單位重量價值最大的物品。
反例：
W=30
物品：A B C
重量：28 20 10
價值：28 20 10
根據策略，三種物品單位重量價值一樣，程式無法依據現有策略作出判斷，如果選擇A，則答案錯誤。
【注意：如果物品可以分割為任意大小，那么策略3可得最優解】
對於選取單位重量價值最大的物品這個策略，可以再加一條最佳化的規則：對於單位重量價值一樣的，則優先選擇重量小的！這樣，上面的反例就解決了。
但是，如果題目是如下所示，這個策略就也不行了。
W=40
物品：A B C
重量：25 20 15
價值：25 20 15
附：本題是個DP問題，用貪心法並不一定可以求得最優解，以後了解了動態規划算法後本題就有了新的解法。
例題2、
馬踏棋盤的貪心算法
123041-23 XX
【問題描述】
馬的遍歷問題。在8×8方格的棋盤上，從任意指定方格出發，為馬尋找一條走遍棋盤每一格並且只經過一次的一條最短路徑。
【初步設計】
首先這是一個搜尋問題，運用深度優先搜尋進行求解。算法如下：
⒈輸入初始位置坐標x,y；
⒉步驟 c:
如果c>64輸出一個解，返回上一步驟c--
（x,y) ← c
計算(x,y）的八個方位的子結點，選出那些可行的子結點
循環遍歷所有可行子結點，步驟c++重複2
顯然⑵是一個遞歸調用的過程，大致如下：
C++程式：
Pascal程式：
這樣做是完全可行的，它輸入的是全部解，但是馬遍歷當8×8時解是非常之多的，用天文數字形容也不為過，這樣一來求解的過程就非常慢，並且出一個解也非常慢。
怎么才能快速地得到部分解呢？
【貪心算法】
其實馬踏棋盤的問題很早就有人提出，且早在1823年，J.C.Warnsdorff就提出了一個有名的算法。在每個結點對其子結點進行選取時，優先選擇‘出口’最小的進行搜尋，‘出口’的意思是在這些子結點中它們的可行子結點的個數，也就是‘孫子’結點越少的越優先跳，為什麼要這樣選取，這是一種局部調整最優的做法，如果優先選擇出口多的子結點，那出口少的子結點就會越來越多，很可能出現‘死’結點（顧名思義就是沒有出口又沒有跳過的結點），這樣對下面的搜尋純粹是徒勞，這樣會浪費很多無用的時間，反過來如果每次都優先選擇出口少的結點跳，那出口少的結點就會越來越少，這樣跳成功的機會就更大一些。這種算法稱為為貪心算法，也叫貪婪算法或啟發式算法，它對整個求解過程的局部做最優調整，它只適用於求較優解或者部分解，而不能求最優解。這樣的調整方法叫貪心策略，至於什麼問題需要什麼樣的貪心策略是不確定的，具體問題具體分析。實驗可以證明馬遍歷問題在運用到了上面的貪心策略之後求解速率有非常明顯的提高，如果只要求出一個解甚至不用回溯就可以完成，因為在這個算法提出的時候世界上還沒有計算機，這種方法完全可以用手工求出解來，其效率可想而知。
備註
貪心算法當然也有正確的時候。求最小生成樹的Prim算法和Kruskal算法都是漂亮的貪心算法。
貪心法的套用算法有Dijkstra的單源最短路徑和Chvatal的貪心集合復蓋啟發式
所以需要說明的是，貪心算法可以與隨機化算法一起使用，具體的例子就不再多舉了。其實很多的智慧型算法（也叫啟發式算法），本質上就是貪心算法和隨機化算法結合——這樣的算法結果雖然也是局部最優解，但是比單純的貪心算法更靠近了最優解。例如遺傳算法，模擬退火算法。
數學套用
如把3/7和13/23分別化為三個單位分數的和
【貪心算法】
設a、b為互質正整數，a
步驟一：用b除以a，得商數q1及餘數r1。（r1=b-a*q1）
步驟二：把a/b記作：a/b=1/(q1+1）+(a-r1)/b(q1+1）
步驟三：重複步驟2，直到分解完畢
3/7=1/3+2/21=1/3+1/11+1/231
13/23=1/2+3/46=1/2+1/16+1/368
以上其實是數學家斐波那契提出的一種求解埃及分數的貪心算法，準確的算法表述應該是這樣的：
設某個真分數的分子為a，分母為b;
把b除以a的商部分加1後的值作為埃及分數的某一個分母c；
將a乘以c再減去b，作為新的a；
將b乘以c，得到新的b；
如果a大於1且能整除b，則最後一個分母為b/a；算法結束；
或者，如果a等於1，則，最後一個分母為b；算法結束；
否則重複上面的步驟。
備註：事實上，後面判斷a是否大於1和a是否等於1的兩個判斷可以合在一起，及判斷b%a是否等於0，最後一個分母為b/a，顯然是正確的。
代碼實例
Java原始碼
1packagemain;
2
3importjava.util.ArrayList;
4importjava.util.Collections;
5importjava.util.Comparator;
6importjava.util.List;
7importjava.util.Random;
8
9publicclassMain{
10
11/**
12*測試
13*/
14publicstaticvoidmain(String[]args){
15//1.隨機構造一批任務
16List>inputList=newArrayList>();
17Randomrand=newRandom();
18for(intn=0;n<20;++n){
19Integerleft=rand.nextInt(100);
20Integerright=left+rand.nextInt(100)+1;
21Pairpair=newPair(left,right);
22inputList.add(pair);
23}
24//將任務列表按結束時間排序(也就是根據right欄位進行排序)
25sortByRight(inputList);
26printPairList(inputList);
27//執行算法
28List>outputList=algorithm(inputList);
29System.out.println();
30printPairList(outputList);
31}
32
33/**
34*貪心算法
35*@paraminputList
36*@return使數量最多的任務方案
37*/
38publicstatic>List>algorithm(List>inputList){
39if(null==inputList||inputList.size()==0||inputList.size()==1){
40returninputList;
41}
42sortByRight(inputList);
43List>outputList=newArrayList>();
44intlast=0;
45outputList.add(inputList.get(last));
46intintputSize=inputList.size();
47for(intm=1;m
48PairnextPair=inputList.get(m);
49TnextLeft=nextPair.getLeft();
50PairlastOutPair=inputList.get(last);
51TlastRight=lastOutPair.getRight();
52intflag=nextLeft.compareTo(lastRight);
53if(flag>=0){
54outputList.add(nextPair);
55last=m;
56}
57}
58
59returnoutputList;
60}
61
62/**
63*對傳入的List>對象進行排序，使Pair根據right從小到大排序。
64*@paraminputList
65*/
66privatestatic>voidsortByRight(List>inputList){
67CompareByRightcomparator=newCompareByRight();
68Collections.sort(inputList,comparator);
69}
70
71/**
72*列印一個List>對象。
73*@paraminputList
74*/
75privatestatic>voidprintPairList(List>inputList){
76for(Pairpair:inputList){
77System.out.println(pair.toString());
78}
79}
80}
81
82/**
83*根據Pair.right比較兩個Pair。用於Conlections.sort()方法。
84*@param
85*/
86classCompareByRight>implementsComparator>{
87@Override
88publicintcompare(Pairo1,Pairo2){
89Tr1=o1.getRight();
90Tr2=o2.getRight();
91intflag=r1.compareTo(r2);
92returnflag;
93}
94}
95
96/**
97*代表一個任務對象。有點裝逼用模板來寫了。left表示開始時間，right表示結束時間。
98*@param
99*/
100classPair>{
101privateTleft;
102privateTright;
103
104publicPair(Tleft,Tright){
105this.left=left;
106this.right=right;
107}
108
109@Override
110publicStringtoString(){
111return"[left="+left.toString()+','+"right="+right.toString()+']';
112}
113
114publicTgetLeft(){
115returnleft;
116}
117
118publicvoidsetLeft(Tleft){
119this.left=left;
120}
121
122publicTgetRight(){
123returnright;
124}
125
126publicvoidsetRight(Tright){
127this.right=right;
128}
129}
