有人说贪心算法是最简单的算法，原因很简单：你我其实都很贪，根本不用学就知道怎么贪。
有人说贪心算法是最复杂的算法，原因也很简单：这世上会贪的人太多了，那轮到你我的份？贪心算法详解贪心算法思想：顾名思义，贪心算法总是作出在当前看来最好的选择。
也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
当然，希望贪心算法得到的最终结果也是整体最优的。
虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。
如单源最短路经问题，最小生成树问题等。
在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。
贪心算法的基本要素：1.贪心选择性质。
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。
这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。
动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。
2. 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。
问题的最优子结构性质是该问题可用动态规划算法或贪心算法求解的关键特征。
贪心算法的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。
当达到算法中的某一步不能再继续前进时，算法停止。
该算法存在问题：1. 不能保证求得的最后解是最佳的；2. 不能用来求最大或最小解问题；3. 只能求满足某些约束条件的可行解的范围。
实现该算法的过程：从问题的某一初始解出发；while 能朝给定总目标前进一步do求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；用背包问题来介绍贪心算法：背包问题：有一个背包，背包容量是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种贪心策略，都是无法成立（无法被证明）的，解释如下：贪心策略：选取价值最大者。
反例：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，则答案错误。
但是果在条件中加一句当遇见单位价值相同的时候,优先装重量小的,这样的问题就可以解决.所以需要说明的是，贪心算法可以与随机化算法一起使用，具体的例子就不再多举了。
（因为这一类算法普及性不高，而且技术含量是非常高的，需要通过一些反例确定随机的对象是什么，随机程度如何，但也是不能保证完全正确，只能是极大的几率正确）。
网上对于这个装包问题的描述就就只有这些,但是在这里我还是要写一下,假设条件是什么?假设条件是上述几种反例的情况不存在的时候该如何求解:[cpp]view plain copyprint?1.#include <iostream>ing namespace std;3.4.struct Node5.{6.float weight;7.float value;8.bool mark;9.char char_mark;10.float pre_weight_value;11.};12.13.int main(int argc, char* argv[])14.{15.float Weight[7] = {35,30,60,50,40,15,20};16.float Value [7] = {10,40,30,50,35,40,30};17. Node array[7];18.for(int i=0; i<7; i++)19. {20. array[i].value = Value[i];21. array[i].weight = Weight[i];22. array[i].char_mark = 65 + i;23. array[i].mark = false;24. array[i].pre_weight_value = Value[i] / Weight[i];25. }26.27.for(i=0;i<7;i++)28. cout<<array[i].pre_weight_value<<" ";29. cout<<endl;30.31.float weight_all=0.0;32.float value_all = 0.0;33.float max = 0.0;34.char charArray[7];35.int flag,n = 0;36.37.while(weight_all <= 150)38. {39.for(int index=0;index < 7; ++index)40. {41.if(array[index].pre_weight_value > max && array[index].mark == false)42. {43. max = array[index].pre_weight_value ;44. flag = index;45. }46. }47.48. charArray[n++] = array[flag].char_mark;49. array[flag].mark = true;50. weight_all += array[flag].weight;51. value_all += array[flag].value;52. max = 0.0;53. }54.55.for(i=0;i<n-1;i++)56. cout<<charArray[i]<<" ";57. cout<<endl;58. cout<<"weight_all:"<<weight_all- array[n-1].weight<<endl;59. cout<<"value_all:"<<value_all<<endl;60.61. system("pause");62.return 0;63.}下面我要说的是，这个算法里面就是采用的贪心第三方案，一般这个方案是成功率最大的，其他两个方案我在这里没有考虑，在这里得到的结果是利用了115容量装了价值195的东西，但是这明显不是最优结果，分明还可以装一个A进去！刚好满足150重量，由于在算法中我单纯的利用第三种贪心方法求解，当剩余的包裹中最优的再加进来的时候已经超过了，所以这个时候可以选择剩余包裹中次优的（如这里选择A），再不行就次次优的，尽量把包裹装满，这样得到的结果就很接近了（不保证一定为最优），但是我们一般不这样来求解，下一文章会介绍动态规划算法来解决这个问题，动态规划很好的弥补了贪心算法的不足！详见下一章！！还需要说明的是，如果包裹是可以拆分的，那这个问题就得到了整体最优解，前面不变，就是当最后一次装进去已经超过容量的时候可以选择只装她的一部分！很多编程题一般是这种情况！经自己总结的贪心算法几大经典问题：1：活动时间安排的问题设有N个活动时间集合，每个活动都要使用同一个资源，比如说会议场，而且同一时间内只能有一个活动使用，每个活动都有一个使用活动的开始si和结束时间fi，即他的使用区间为（si,fi）,现在要求你分配活动占用时间表，即哪些活动占用该会议室，哪些不占用，使得他们不冲突，要求是尽可能多的使参加的活动最大化，即所占时间区间最大化！上图为每个活动的开始和结束时间，我们的任务就是设计程序输出哪些活动可以占用会议室！[cpp]view plain copyprint?1.#include <iostream>ing namespace std;3.4.void GreedyChoose(int len,int *s,int *f,bool *flag);5.6.int main(int argc, char* argv[])7.{8.int s[11] ={1,3,0,5,3,5,6,8,8,2,12};9.int f[11] ={4,5,6,7,8,9,10,11,12,13,14};10.11.bool mark[11] = {0};12.13. GreedyChoose(11,s,f,mark);14.for(int i=0;i<11;i++)15.if(mark[i])16. cout<<i<<" ";17. system("pause");18.return 0;19.}20.21.void GreedyChoose(int len,int *s,int *f,bool *flag)22.{23. flag[0] = true;24.int j = 0;25.for(int i=1;i<len;++i)26.if(s[i] >= f[j])27. {28. flag[i] = true;29. j = i;30. }31.}得出结果是0 3 7 10，也就是对应的时间段值得说明一下，虽然贪心算法不是一定可以得到最好的解，但是对于这种活动时间的问题，他却得到的总是最优解，这点可以用数学归纳法证明，在这里，体现出来的贪心策略是：每一个活动时间的挑选总是选择最优的，就是刚好匹配的，这样得出的结果也就是最优的了！由于这个算法很简单，在这里就没有注释了！类似这种题还有个区间覆盖问题，就是说很多个区间，其中有些是相互覆盖着的，要求去除多余的区间，使剩下的区间占用长度最大，实际就是这个题，只是问法变换了而已！接下来让我们看线性覆盖的问题，跟上面的相反！2.贪心实例之线段覆盖（lines cover）题目大意：在一维空间中告诉你N条线段的起始坐标与终止坐标，要求求出这些线段一共覆盖了多大的长度。