背景
有1元、5元、10元、20元、100元、200元的鈔票無窮多張?，F(xiàn)使用這些鈔票支付X元，最少需要多少張？
例如，X=628
我們應(yīng)該盡可能使用面值較大的鈔票，最佳支付方法：
3張200元的，1張20元的，1張5元的，3張1元的，共需要3+1+1+3=8張。
為何這么做一定是對的？
面額為1元、5元、10元、20元、100元、200元，任意面額是比自己小的面額的倍數(shù)關(guān)系。所以，當(dāng)使用一張較大面額鈔票時，若用較小面額鈔票替換，一定需要更多的其他面額的鈔票！
例如：
5=1+1+1+1+1
10=5+5
20=10+10
100=20+20+20+20+20
200=100+100
因此，當(dāng)前最優(yōu)解即為全局最優(yōu)解，貪心算法成立。
概述
貪心算法（greedy algorithm，貪婪算法）是尋找最優(yōu)解問題的常用方法。這種方法一般是將求解過程分成若干個步驟，在每個步驟都應(yīng)用貪心原則，選取當(dāng)前狀態(tài)下最好或者最優(yōu)的選擇（局部最優(yōu)的選擇），并以此希望最后堆疊出的結(jié)果也是最好或最優(yōu)的解。貪心法的每次決策都以當(dāng)前情況為基礎(chǔ)并根據(jù)某個最優(yōu)原則進行選擇，不從整體上考慮其他各種可能的情況。即貪心法是分階段執(zhí)行的，每一個階段都根據(jù)當(dāng)前的情況來判斷，而不考慮后續(xù)的發(fā)展。
一般來說，這種算法選出的解是局部最佳（local best）解。該算法預(yù)設(shè)了這樣一個前提，就是認(rèn)為全局最優(yōu)解可以由局部最優(yōu)解所推出。
貪心法是遵循某種規(guī)律，不斷貪心的選取當(dāng)前最優(yōu)策略的算法設(shè)計方法。即，貪心算法不追求最優(yōu)解，只找到滿意解。
貪心法VS分治法VS動態(tài)規(guī)劃：
貪心法和分治法、動態(tài)規(guī)劃一樣，都需要對問題進行分解，定義最優(yōu)的子結(jié)構(gòu)。但是，貪心法與其他方法最大的區(qū)別在于，貪心法每一步選擇完之后，局部最優(yōu)解就確定了，不再進行回溯處理，也就是說，每一個步驟的局部最優(yōu)解確定以后，就不再修改，直到算法結(jié)束。因為不進行回溯處理，貪心法只在很少情況下可以得到真正的最優(yōu)解，比如最短路徑問題、圖的最小生成樹問題。
條件
有待處理的問題必須滿足下列兩項條件，才能用貪婪算法求出最優(yōu)的解：
1、具備貪心選擇性質(zhì)（greedy?choice?property）
2、具備最優(yōu)子結(jié)構(gòu)（optimal?substructure）
貪心選擇性質(zhì)：該性質(zhì)意味著全局最優(yōu)解可以由局部最優(yōu)解（也就是在貪心策略下所選出的解）所推出。貪婪算法在針對當(dāng)前這一步做決定時，可以參考前面幾步的決定，但是不會依賴后續(xù)的步驟。它總是會選出局部最優(yōu)的解，并將原問題約簡為更小的問題，然后在更小的問題上繼續(xù)尋找其局部最優(yōu)解，并繼續(xù)約簡。
最優(yōu)子結(jié)構(gòu)：如果某個問題的最優(yōu)解可以由其各個子問題的最優(yōu)解所構(gòu)成，那么該問題就具備最優(yōu)子結(jié)構(gòu)。這意味著把子問題的解法拼合起來可以解決最初所要求解的那個大問題。
但是，要判斷一個問題是否具備上述兩種性質(zhì)，也就是說判斷一個問題是否可以通過貪心算法得到最優(yōu)解，是一件比較苦難的事情。這里需要比較復(fù)雜而嚴(yán)格的數(shù)學(xué)證明。因此，雖然貪心算法簡單容易實現(xiàn)，并且效率很高，但是使用貪心算法之前必須對問題本身進行深入而透徹地分析和證明，以保證使用貪心算法得到最優(yōu)解。
特點
優(yōu)點
直觀、易懂，實現(xiàn)簡單。算法一旦做出決定，就不用回過頭來去重新檢查前面計算過的那些值。
缺點
并非所有問題都能那么解決，對于很多問題，在某個小范圍內(nèi)所做的最優(yōu)決策，未必是整個問題的最優(yōu)決策。
應(yīng)用場景
貪心算法不是對所有問題都能得到整體的最優(yōu)解，但是實際應(yīng)用中許多問題都可以使用貪心算法得到最優(yōu)解。與此同時，即使使用貪心算法不能產(chǎn)生出問題的最優(yōu)解，但最終結(jié)果也就是最優(yōu)解的很好的近似解。因此在解決一般性問題時（并不一定要得到最優(yōu)解），我們大可不必過分要求使用貪心算法一定要得到最優(yōu)解，也沒有必要進行嚴(yán)格地推理證明，使用貪心算法是一種不錯的選擇。
