[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背包问题，贪心算法之所以没有拿到最优解是因为在这种情况下，它无法保证最终能将背包背满，部分闲置的背包空间使每千克背包空间的价值降低了。 > 如果对于整个背包单位重量的价值最大，则背包价值一定达到最大，即就是最优解。 > 贪心算法中作出的每步贪心决策都无法改变，因为贪心策略是由上一步的最优解推导下一步的最优解，而上一部之前的最优解则不作保留，贪心算法每一步的最优解一定包含上一步的最优解。动态规划算法中全局最优解中一定包含某个局部最优解，但不一定包含前一个局部最优解，因此需要记录之前的所有最优解。