动态规划总是在追求全局最优的解，但是有时候，这样有点费时。贪心算法，在求解过程中，并不追求全局最优解，而是追求每一步的最优，所以贪心算法也不保证一定能够获得全局最优解，但是贪心算法在很多问题却额可以求得最优解。
一、基本概念
在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。必须注意的是，贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以，对所采用的贪心策略一定要仔细分析其是否满足无后效性。
二、基本思路
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。
三、贪心算法适用的问题
贪心策略适用的前提是：局部最优策略能导致产生全局最优解。实际上，贪心算法适用的情况很少。一般，对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可做出判断。
四、贪心算法的实现框架
从问题的某一初始解出发；while（能朝给定总目标前进一步）{利用可行的决策，求出可行解的一个解元素；}由所有解元素组合成问题的一个可行解；
五、贪心策略的选择
因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，因此，一定要注意判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。
六、例题分析——[背包问题]
有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
分析：
目标函数： ∑pi最大 约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？（2）每次挑选所占重量最小的物品装入是否能得到最优解？（3）每次选取单位重量价值最大的物品，成为解本题的策略。
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
（1）贪心策略：选取价值最大者。反例：
W=30 物品：A B C 重量：28 12 12 价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
（3）贪心策略：选取单位重量价值最大的物品。反例：
W=30 物品：A B C 重量：28 20 10 价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
背包问题以后找个时间再好好分析研究：
七、纸币找零问题
假设1元、2元、5元、10元、20元、50元、100元的纸币，张数不限制，现在要用来支付K元，至少要多少张纸币？
很显然，我们很容易就想到使用贪心算法来解决，并且我们所根据的贪心策略是，每一步尽可能用面值大的纸币即可。当然这是正确的，代码如下：
public static void greedyGiveMoney(int money) {System.out.println("需要找零: " + money);int[] moneyLevel = {1, 5, 10, 20, 50, 100};for (int i = moneyLevel.length - 1; i >= 0; i--) {//取商int num = money/ moneyLevel[i];//取余数int mod = money % moneyLevel[i];money = mod;if (num > 0) {System.out.println("需要" + num + "张" + moneyLevel[i] + "块的");}if(mod==0) {break;}}}
（1）如果不限制纸币的金额，那这种情况还适合用贪心算法么。比如1元，2元，3元，4元，8元，15元的纸币，用来支付K元，至少多少张纸币？
经我们分析，这种情况是不适合用贪心算法的，因为我们上面提供的贪心策略不是最优解。比如，纸币1元，5元，6元，要支付10元的话，按照上面的算法，至少需要1张6元的，4张1元的，而实际上最优的应该是2张5元的。
（2）如果限制纸币的张数，那这种情况还适合用贪心算法么。比如1元10张，2元20张，5元1张，用来支付K元，至少多少张纸币？
同样，仔细想一下，就知道这种情况也是不适合用贪心算法的。比如1元10张，20元5张，50元1张，那用来支付60元，按照上面的算法，至少需要1张50元，10张1元，而实际上使用3张20元的即可；
（3）所以贪心算法是一种在某种范围内，局部最优的算法。
八、活动选择问题
假定一个有n个活动(activity)的集合S={a1,a2,….,an}，这些活动使用同一个资源（例如同一个阶梯教室），而这个资源在某个时刻只能供一个活动使用。每个活动ai都有一个开始时间si和一个结束时间fi，其中0<=si
f1<=f2<=f3<=f4<=...<=fn-1<=fn
考虑如下活动集合
| 活动i | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| si | 1 | 3 | 0 | 5 | 3 | 5 | 6 | 8 | 8 | 2 | 12 |
| fi | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 |
可以看到，{a3,a9,a11}是由相互兼容的活动组成。但它不是一个最大集，{a1,a4,a8,a11}更大，是一个最大集，最大集可以有多个不同的,比如{a2,a4,a9,a11}。
假设：Sij表示在ai结束之后，在aj开始之前的活动的集合。Aij表示Sij的一个最大相互兼容的活动子集。那么只要Sij非空，则Aij至少会包含一个活动，假设为ak。那么可以将Aij分解为：Aij = Aik+ak+Akj。假设Cij为Aij的大小，那么有Cij=cik+ckj+1。但是我们并不知道具体是k等于多少的时候，可以让ak一定位于Aij中，所以我们采用动态规划的方式，遍历所有可能的k值，来取得。于是有：
接下来，如果按照动态规划的方式，就可以采用自底向上的递归来求解最优的解。
但是贪心算法却要简单许多，贪心算法直接在每一步选择当前看来最好的选择。比如在一开始的时候，我们要选择在Aij中的第一个活动，我们选择活动结束时间最早的那个活动，这样能够给其他活动尽可能的腾出多余的时间。而后每一步都在剩下的活动中选取，也遵循类似的原则。由于获取已经按照fi排序好，所以这里第一个选择的活动就是a1。但是问题来了，我们能否确定a1一定在Aij中呢，在这个问题中，答案是肯定的，可以给出简单的证明：
假设Aij是Sij的某个最大兼容活动集，假设Aij中，最早结束的活动是an，分两种情况：
①如果an=a1，则得证
②如果an不等于a1，则an的结束时间一定会晚于a1的结束时间，我们用a1去替换Aij中的an，于是得到A，由于a1比an结束的早，而Aij中的其他活动都比an的结束时间开始 的要晚，所以A中的其他活动 都与a1不想交，所以A中的所有活动是兼容的，所以A也是Sij的一个最大兼容活动集。
于是证明了命题。
根据上面的结论，我们可以给出贪心算法在解决这个问题的两种方式：递归和迭代方式，两种算法都是按照自顶向下来求解问题的。
Java实现两种贪心算法策略:
public class Activity {/*** 递归找寻最大兼容的活动* @param activiy 可以同时进行的活动* @param si 活动i的开始使劲* @param fi 活动i的结束时间* @param index 活动开始下标因为已经按结束时间排序，所以开始是0* @param i 兼容活动的下标*/private static void recursiveActivitySelector(int[] activiy,int[] si,int[] fi,int index,int i) {//获取第二个活动int m = index+1;int n =si.length;//寻找活动的活动开始时间晚于上一个活动的活动结束时间，那么第二个活动就是可以进行的while(m<n&&si[m]<=fi[index]) {//继续寻找m++;}//到这里若是m还没有大于n就表明找到了if(m<n) {//活动下标记录的是活动的序号，从1开始activiy[i]=m+1;recursiveActivitySelector(activiy,si,fi,m,i+1);}}/*** 迭代方式* @param activiy 可以同时进行的活动* @param si 活动i的开始使劲* @param fi 活动i的结束时间*/private static void GreedyActiivtySelector(int[] activiy,int[] si,int[] fi) {//选择活动1int start=0;int index = 0;int n = si.length;activiy[start++]=index+1;//从第二个开始for(int m=1;m<n;m++) {if(si[m]>=fi[index]) {//活动m的开始时间晚于上一个活动的结束时间，活动有效activiy[start++]=m+1;//然后再以该活动开始寻找index=m;}}}public static void main(String[] args) {//活动i已经按fi的时间排序，排序的时间复杂度为O(nlogn)int[] si=new int[]{1,3,0,5,3,5,6,8,8,2,12};int[] fi=new int[]{4,5,6,7,8,9,10,11,12,13,14};int[] activity = new int[si.length];int[] activity2 = new int[si.length];//默认第一个活动activity[0]=1;System.out.println("递归贪心算法求出的最大相互兼容活动子集：");recursiveActivitySelector(activity,si,fi,0,1);for (int i = 0; i < activity.length; i++) {if(activity[i]!=0) {System.out.print(activity[i]+";");}}System.out.println();System.out.println("迭代贪心算法求出的最大相互兼容活动子集：");GreedyActiivtySelector(activity2,si,fi) ;for (int i = 0; i < activity2.length; i++) {if(activity2[i]!=0) {System.out.print(activity2[i]+";");}}}}
运行结果如下
递归贪心算法求出的最大相互兼容活动子集：1;4;8;11;迭代贪心算法求出的最大相互兼容活动子集：1;4;8;11;
这里迭代的代码更加简洁！
假设实现活动已经按照fi的升序排列好了的话，会发现实际上贪心算法在处理这个问题的时候只做了一次遍历，所以算法复杂度为O(n)。
