[TOC] # 參考資料 百度百科：[貪心算法](http://baike.baidu.com/link?url=h6shYXRmcKjzP1uYkJdUKFqkS-xUUp7N8055v8s11FUJELiQqeqV_-3t1xWpwaA0_SPvj9g4j0lV1Ak8ao8jlq) 五大常用算法：[貪心算法](http://www.cnblogs.com/steven_oyj/archive/2010/05/22/1741375.html) [貪心算法](http://blog.csdn.net/column/details/lf-algoritnote.html) # Introduction 貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，他所做出的是在某種意義上的局部最優解。 貪心算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態以前的過程不會影響以后的狀態，只與當前狀態有關。 ### 算法基本要素 * 貪心選擇的性質 ：所求問題的整體最優解，可以通過一系列局部最優的選擇來達到。 在動態規劃中，每步所做的選擇往往依賴于相關子問題的解。因而只有在解出相關子問題后，才能做出選擇。而在貪心算法中，僅在當前狀態下做出最優解，即局部最優選擇。然后再去解做出這個選擇后產生的相應子問題。 貪心算法所做的貪心選擇可以依賴于以往所做過的選擇，但決對不依賴于將來所做的選擇，也不依賴于子問題的解。正是由于這種差別，動態規劃算法通常以自底向上的方式求解各個子問題，而貪心算法通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每做一次貪心選擇就將所求的問題簡化為規模更小的子問題。 * 最優子結構性質：當一個問題的最優解包含其子問題的最優解時，稱此問題具有最優子結構的性質。 ### 動態規劃 VS 貪心算法 #### 0-1背包問題 **問題描述**： 給定n中物品和一個背包。物品i的重量為Wi，其價值為Vi，背包的容量為C。問應該如何選擇裝入背包中的物品，使得裝入背包中的物品價值最大。 在選擇轉入背包的物品時，對每種物品i只有兩種選擇，即裝入和不裝入。不能講物品i裝入背包多次（不重復），也不能只裝入部分i。 此問題的形式化描述是，給定C>0，Wi>0,Vi>0,1<=i<=n，要求找出一個n元0-1向量(x1,x2,...,xn)，xi∈{0,1}，1<=i<=n，使得w1\*x1+w2\*x2+...+wn\*xn<=c,而且v1\*x1+v2\*x2+...+vn\*xn 達到最大。 #### 背包問題 **問題描述**： 給定n中物品和一個背包。物品i的重量為Wi，其價值為Vi，背包的容量為C。問應該如何選擇裝入背包中的物品，使得裝入背包中的物品價值最大。 在選擇轉入背包的物品時，對每種物品i只有兩種選擇，即裝入和不裝入。不能講物品i裝入背包多次（不重復），也不能只裝入部分i。 此問題的形式化描述是，給定C>0，Wi>0,Vi>0,1<=i<=n，要求找出一個n元0-1向量(x1,x2,...,xn)，0<=xi<=1，1<=i<=n，使得w1\*x1+w2\*x2+...+wn\*xn<=c,而且v1\*x1+v2\*x2+...+vn\*xn 達到最大。 #### 分析 其中，01背包不能使用貪心算法，但背包問題可以使用。基本步驟是，首先計算每種物品單位重量的價值vi/wi，然后從高到低開始放入，直到背包滿。 對于0-1背包問題，貪心算法之所以沒有拿到最優解是因為在這種情況下，它無法保證最終能將背包背滿，部分閑置的背包空間使每千克背包空間的價值降低了。 > 如果對于整個背包單位重量的價值最大，則背包價值一定達到最大，即就是最優解。 > 貪心算法中作出的每步貪心決策都無法改變，因為貪心策略是由上一步的最優解推導下一步的最優解，而上一部之前的最優解則不作保留，貪心算法每一步的最優解一定包含上一步的最優解。動態規劃算法中全局最優解中一定包含某個局部最優解，但不一定包含前一個局部最優解，因此需要記錄之前的所有最優解。