一、基本概念
所謂貪心算法是指弓柱，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說笙各，不從整體最優(yōu)上加以考慮唱蒸，它所做出的僅僅是在某種意義上的局部最優(yōu)解邦鲫。
貪心算法沒有固定的算法框架，算法設(shè)計的關(guān)鍵是貪心策略的選擇神汹。必須注意的是庆捺，貪心算法不是對所有問題都能得到整體最優(yōu)解，選擇的貪心策略必須具備無后效性（即某個狀態(tài)以后的過程不會影響以前的狀態(tài)屁魏，只與當前狀態(tài)有關(guān)滔以。）
所以，對所采用的貪心策略一定要仔細分析其是否滿足無后效性氓拼。
二你画、貪心算法的基本思路
- 建立數(shù)學模型來描述問題
- 把求解的問題分成若干個子問題
- 對每個子問題求解，得到子問題的局部最優(yōu)解
- 把子問題的解局部最優(yōu)解合成原來問題的一個解
三桃漾、該算法存在的問題
- 不能保證求得的最后解是最佳的
- 不能用來求最大值或最小值的問題
- 只能求滿足某些約束條件的可行解的范圍
四坏匪、貪心算法適用的問題
貪心策略適用的前提是：局部最優(yōu)策略能導致產(chǎn)生全局最優(yōu)解。
實際上撬统，貪心算法適用的情況很少适滓。一般對一個問題分析是否適用于貪心算法，可以先選擇該問題下的幾個實際數(shù)據(jù)進行分析恋追，就可以做出判斷凭迹。
五罚屋、貪心選擇性質(zhì)
所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，換句話說嗅绸，當考慮做何種選擇的時候脾猛，我們只考慮對當前問題最佳的選擇而不考慮子問題的結(jié)果。這是貪心算法可行的第一個基本要素鱼鸠。貪心算法以迭代的方式作出相繼的貪心選擇尖滚，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個具體問題瞧柔，要確定它是否具有貪心選擇性質(zhì)漆弄，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。
當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時造锅，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)撼唾。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心算法求解的關(guān)鍵特征。
六哥蔚、貪心算法的實現(xiàn)框架
從問題的某一初始解出發(fā)：
while (朝給定總目標前進一步)
{
利用可行的決策倒谷，求出可行解的一個解元素。
}
由所有解元素組合成問題的一個可行解糙箍；
五渤愁、例題分析
【背包問題】有一個背包，容量是M=150深夯，有7個物品抖格，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價值最大咕晋，但不能超過總?cè)萘俊?br> 物品：A B C D E F G
重量：35 30 60 50 40 10 25
價值：10 40 30 50 35 40 30
分析：
目標函數(shù)： ∑pi最大
約束條件是裝入的物品總質(zhì)量不超過背包容量：∑wi<=M( M=150)
（1）根據(jù)貪心的策略雹拄，每次挑選價值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)掌呜？
（2）每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解滓玖？
（3）每次選取單位重量價值最大的物品，成為解本題的策略
值得注意的是质蕉，貪心算法并不是完全不可以使用势篡，貪心策略一旦經(jīng)過證明成立后，它就是一種高效的算法模暗。比如禁悠，求最小生成樹的Prim算法和Kruskal算法都是漂亮的貪心算法。
貪心算法還是很常見的算法之一汰蓉，這是由于它簡單易行绷蹲，構(gòu)造貪心策略不是很困難棒卷。
可惜的是顾孽，它需要證明后才能真正運用到題目的算法中祝钢。
一般來說，貪心算法的證明圍繞著：整個問題的最優(yōu)解一定由在貪心策略中存在的子問題的最優(yōu)解得來的若厚。
對于例題中的3種貪心策略拦英，都是無法成立（無法被證明）的，解釋如下：
貪心策略：選取價值最大者测秸。反例：
W=30
物品：A B C
重量：28 12 12
價值：30 20 20
根據(jù)策略疤估，首先選取物品A，接下來就無法再選取了霎冯，可是铃拇，選取B、C則更好沈撞。
（2）貪心策略：選取重量最小慷荔。它的反例與第一種策略的反例差不多。
（3）貪心策略：選取單位重量價值最大的物品缠俺。反例：
W=30
物品：A B C
重量：28 20 10
價值：28 20 10
根據(jù)策略显晶，三種物品單位重量價值一樣，程序無法依據(jù)現(xiàn)有策略作出判斷壹士，如果選擇A磷雇，則答案錯誤。但是果在條件中加一句當遇見單位價值相同的時候,優(yōu)先裝重量小的,這樣的問題就可以解決.
所以需要說明的是躏救，貪心算法可以與隨機化算法一起使用唯笙，具體的例子就不再多舉了。（因為這一類算法普及性不高盒使，而且技術(shù)含量是非常高的睁本，需要通過一些反例確定隨機的對象是什么，隨機程度如何忠怖，但也是不能保證完全正確呢堰，只能是極大的幾率正確）。
