贪心策略，也称为贪婪策略，每一步都采取当前状态下最优的选择（局部最优解），从而希望推导出全局最优解。
应用：
哈夫曼树
最小生成树算法：Prim、Kruskal
最短路径算法：Dijkstra
练习1：最优装载问题（加勒比海盗）
在北美洲东南部，有一片神秘的海域，是海盗最活跃的加勒比海。有一天，海盗们截获了一艘装满各种各样古董的货船，每一件古董都价值连城，一旦打碎就失去了它的价值，海盗船的载重量为W，每件古董的重量为i，海盗们该如何把尽可能多数量的古董装上海盗船？
比如W为30，i分别为3、5、4、10、7、14、2、11
贪心策略：每一次都优先选择重量最小的古董
①选择重量为2的古董，剩重量28
②选择重量为3的古董，剩重量25
③选择重量为4的古董，剩重量21
④选择重量为5的古董，剩重量16
⑤选择重量为7的古董，剩重量9
最多能装载5个古董。
代码实现：
int[]weights={3,5,4,10,7,14,2,11}; //升序排序Arrays.sort(weights);intcapacity=30,weight=0;intcount=0;for(inti=0;iweights.lengthweightcapacity;i++){intnewWeight=weight+weights;if(newWeight=capacity){weight=newWeight;count++;}}System.out.printf("一共选择了%d件古董",count);
练习2：零钱兑换
假设有25分、10分、5分、1分的硬币，现要找给客户41分的零钱，如何办到硬币个数最少？
贪心策略：每一次都优先选择面值最大的硬币
①选择25分的硬币，剩16分
②选择10分的硬币，剩6分
③选择5分的硬币，剩1分
④选择1分的硬币
最终的结果是共4枚硬币
25分、10分、5分、1分硬币各一枚
代码实现：
int[]faces={25,10,5,1};Arrays.sort(faces);intmoney=41,coins=0;for(inti=faces.length-1;i=0money0;i--){while(faces=money){money-=faces;coins++;}}System.out.printf("一共使用了%d硬币",coins);
零钱兑换的另一个例子
假设有25分、20分、5分、1分的硬币，现要找给客户41分的零钱，如何办到硬币个数最少？
贪心策略：每一步都优先选择面值最大的硬币
①选择25分的硬币，剩16分
②选择5分的硬币，剩11分
③选择5分的硬币，剩6分
④选择5分的硬币，剩1分
⑤选择1分的硬币
最终的解是1枚25分、3枚5分、1枚1分的硬币，共5枚硬币
实际上本题的最优解是：2枚20分、1枚1分的硬币，共3枚硬币
注意：
贪心策略并不一定能得到全局最优解，因为一般没有测试所有可能的解，容易过早做决定，所以没法达到最佳解，贪图眼前局部的利益最大化，看不到长远未来，走一步看一步
优点：简单、高效、不需要穷举所有可能，通常作为其他算法的辅助算法来使用
缺点：鼠目寸光，不从整体上考虑其他可能，每次采取局部最优解，不会再回溯，因此很少情况会得到最优解
练习3：0-1背包
有n件物品和一个最大承重为W的背包，每件物品的重量是i、价值是i
在保证总重量不超过W的前提下，将哪几件物品装入背包，可以使得背包的总价值最大？
注意：每个物品只有1件，也就是每个物品只能选择0件或者1件，因此称为0-1背包问题
如果采取贪心策略，有3个方案
①价值主导：优先选择价值最高的物品放进背包
②重量主导：优先选择重量最轻的物品放进背包
③价值密度主导：优先选择价值密度最高的物品放进背包（价值密度=价值÷重量）
代码实现：
1）定义一个类：
publicclassArticle{publicintweight;publicintvalue;publicdoublevalueDensity;publicArticle(intweight,intvalue){this.weight=weight;this.value=value;this.valueDensity=value*1.0/weight;}
OverridepublicStringtoString(){return"Article{"+"weight="+weight+",value="+value+",valueDensity="+valueDensity+};}}2）实现：
publicstaticvoidselectedArticles(Stringtype,intcapacity,ComparatorArticlec){Article[]articles=newArticle[]{newArticle(35,10),newArticle(30,40),newArticle(60,30),newArticle(50,50),newArticle(40,35),newArticle(10,40),newArticle(25,30)};Arrays.sort(articles,c);ListArticleselectedArticles=newLinkedList();intweight=0,value=0;for(inti=0;iarticles.lengthweightcapacity;i++){intnewWeight=weight+articles.weight;if(newWeight=capacity){weight=newWeight;value+=articles.value;selectedArticles.add(articles);}}System.out.println("-----------------------------------------------------------------------");System.out.printf("%s总价值:%d\n",type,value);selectedArticles.forEach(System.out::println);}
publicstaticvoidmain(String[]args){intcapacity=;selectedArticles("价值主导",capacity,(a1,a2)-a2.value-a1.value);selectedArticles("重量主导",capacity,(a1,a2)-a1.weight-a2.weight);selectedArticles("价值密度主导",capacity,(a1,a2)-Double.