貪心法（ Greedy algorithm）咖城，又稱貪心算法姐呐，是一種在每一步選擇中都采取在當前狀態(tài)下最好或最優(yōu)（即最有利）的選擇漱挎，從而希望導致結(jié)果是最好或最優(yōu)的算法。
1. 基本概念
貪心算法與動態(tài)規(guī)劃的不同在于它每對每個子問題的解決方案都做出選擇睬澡，不能回退固额。動態(tài)規(guī)劃則會保存以前的運算結(jié)果，并根據(jù)以前的結(jié)果對當前進行選擇煞聪，有回退功能斗躏。
所謂貪心算法是指，在對問題求解時昔脯，總是做出在當前看來是最好的選擇啄糙。也就是說，不從整體最優(yōu)上加以考慮云稚，他所做出的僅是在某種意義上的局部最優(yōu)解隧饼。
貪心算法沒有固定的算法框架，算法設(shè)計的關(guān)鍵是貪心策略的選擇静陈。必須注意的是燕雁，貪心算法不是對所有問題都能得到整體最優(yōu)解，選擇的貪心策略必須具備無后效性鲸拥，即某個狀態(tài)以后的過程不會影響以前的狀態(tài)拐格，只與當前狀態(tài)有關(guān)。所以對所采用的貪心策略一定要仔細分析其是否滿足無后效性崩泡。
貪心法可以解決一些最優(yōu)化問題禁荒，如：求圖中的最小生成樹、求哈夫曼編碼……對于其他問題角撞，貪心法一般不能得到我們所要求的答案呛伴。一旦一個問題可以通過貪心法來解決，那么貪心法一般是解決這個問題的最好辦法谒所。由于貪心法的高效性以及其所求得的答案比較接近最優(yōu)結(jié)果热康，貪心法也可以用作輔助算法或者直接解決一些要求結(jié)果不特別精確的問題。
2. 適用范圍
貪心策略適用的前提是：局部最優(yōu)策略能導致產(chǎn)生全局最優(yōu)解劣领。
實際上姐军，貪心算法適用的情況很少。一般尖淘，對一個問題分析是否適用于貪心算法奕锌，可以先選擇該問題下的幾個實際數(shù)據(jù)進行分析，就可做出判斷村生。
3. 貪心法的步驟
1. 建立數(shù)學模型來描述問題惊暴。
2. 把求解的問題分成若干個子問題。
**3. **對每一子問題求解趁桃，得到子問題的局部最優(yōu)解辽话。
4. 把子問題的解局部最優(yōu)解合成原來解問題的一個解肄鸽。
4. 實現(xiàn)步驟
從問題的某一初始解出發(fā)；while （能朝給定總目標前進一步）{ 利用可行的決策油啤，求出可行解的一個解元素典徘；}由所有解元素組合成問題的一個可行解；
5. 典型問題
（1）0-1背包問題
（2）馬踏棋盤
具體實現(xiàn)參見：http://baike.baidu.com/view/298415.htm?fromtitle=%E8%B4%AA%E5%BF%83%E6%B3%95
