一、什么是貪心算法
貪心算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。(局部最優解，而不是整體最優解)
貪心算法沒有固定的算法框架，算法設計的關鍵是貪心策略的選擇。必須注意的是，貪心算法不是對所有問題都能得到整體最優解，選擇的貪心策略必須具備無后效性(即某個狀態以后的過程不會影響以前的狀態，只與當前狀態有關。)所以，對所采用的貪心策略一定要仔細分析其是否滿足無后效性。
二、貪心算法基本思路
把求解的問題分成若干個子問題
對每個子問題求解，得到子問題的局部最優解(不能保證求得的最后解是最佳的)
把子問題的解局部最優解合成原來問題的一個解
可以看出貪心算法和動態規劃非常相似，但是兩者存在部分區別
1)貪心算法每一步的最優解一定包含上一步的最優解，上一步之前的最優解則不作保留。而動態規劃全局最優解中一定包含某個局部最優解，但不一定包含前一個局部最優解，因此需要記錄之前的所有的局部最優解。
2)貪心算法只能求滿足某些約束條件的可行解的范圍。
3)貪心不能保證求得的最后解是最佳的，一般復雜度低。而動態規劃本質是窮舉法，可以保證結果是最佳的，復雜度高。
三、經典例題
1)指定幣值和相應的數量，用最少的數量湊齊某金額
思路：優先選擇面值大的錢幣，以此類推，直到湊齊總金額
public int[] getCoinNum(int sum, int[] values, int[] counts) { int[] result = new int[values.length]; int add = 0; for (int i = values.length - 1; i >= 0; i--) { int num = (sum - add) / values[i]; if (num > counts[i]) { num = counts[i]; } add = add + num * values[i]; result[i] = num; } return result;}2)部分背包問題，物品可以不完全放入包中，求價值最大的方案
思路：選擇單位重量價值最高的物品，將盡可能多的該物品裝入背包，直到背包裝滿為止。
public float getNum(float M, float[] w, float[] v) { float max = 0; float weight = 0; for (int i = 0; i < w.length; i++) { if (v[i] / w[i] > max) { max = v[i] / w[i]; weight = w[i]; } } float num = M / weight; return num;}
