贪心策略，也称为贪婪策略 每一步都采取当前状态下的最优选择（局部最优），从而希望推导出全局最优解
贪心的应用： 哈夫曼树 最小生成树
题：有一批古董，每一件都价值连城，一旦打碎就失去了价值。 海盗船的载重量为W，每件古董的重量为wi，海盗们如何选古董才能尽可能多的达到最大价值？
比如：W为30，wi分别为：3、5、4、10、7、14、2、11 贪心策略：每一次都优先选择重量最小的古董
可以每次拿一个，然后计算目前拿到的古董总重量，与船的载重量相比； 也可以，每次拿一个，然后拿船的剩余载重量减去将要放进去的古董重量，看结果。
就是，一个加、一个减的过程，都一样。
package com.yz; import java.util.Arrays; public class Weight { public static void main(String[] args) { int[] weights = {3, 5, 4, 10, 7, 14, 2, 11}; Arrays.sort(weights); int capacity = 30; int weight = 0; int count = 0; for (int i = 0; i < weights.length && weight < capacity; i++) { int newWeight = weight + weights[i]; if (capacity >= newWeight) { weight = newWeight; count++; System.out.println(weights[i]); } } System.out.println("海盗可以拿" + count + "件古董"); } } 结果： 2 3 4 5 7 海盗可以拿5件古董假设有25分、10分、5分、1分的硬币，现要找给客户41分零钱，如何办到硬币个数最少？ 贪心策略：每一次都选择面值最大的硬币
根据前面的海盗问题，不难写出该问题的代码程序：
package com.yz; import java.util.Arrays; public class CoinChange { public static void main(String[] args) { int[] coins = {25, 20, 5, 1}; Arrays.sort(coins); int targetMoney = 41; int sum = 0; int count = 0; for (int i = coins.length - 1; i >= 0 && sum < targetMoney; i--) { int newSum = sum + coins[i]; if (newSum <= targetMoney) { sum = newSum; System.out.print(coins[i] + " "); count++; i++; } } System.out.println(count+"枚硬币"); } } 结果： 25 5 5 5 1 5枚硬币有个问题是，20 + 20 + 1只需要3枚硬币即可，而不是贪心策略算出的5枚硬币
也就是：贪心策略并不一定能得到全局最优解 贪心着眼于局部利益最大化，看不到长远的未来，因此，可能不是最优解。 贪心策略并不是暴力求解，不会把每一种情况都考虑到，这样是贪心策略不一定是最优解的原因。
优点：简单、高效、不需要穷举所有可能，通常作为其他算法的辅助算法来使用。
那么，零钱兑换的最优解法是什么呢？ 欢迎学习动态规划
有n件物品和一个最大承重为W的背包，每件物品的重量是wi，价值是vi 在保证总重量不超过W的前提下，将哪几件物品装入背包，可以使得背包的总价值最大？
注意：每个物品只有1件，也就是每个物品只能选择0件或者1件，因此称为0-1背包问题
假设背包最大承重150，7个物品如表格所示 如果采取贪心策略，有3种方案： 价值主导：优先选择价值最高的物品放入背包 重量主导：优先选择重量最轻的物品放入背包 价值密度主导：优先选择价值密度最高的物品放入背包（价值密度 = 价值 / 重量）
既然已经明确贪心策略，代码与之前相似。不同的地方是，可能需要建立一个对象，针对对象的属性进行比较、选择。
//建立物品对象 package Greedy; public class Article { public int weight; public int value; public double valueDensity; //构造方法 public Article(int weight, int value) { super(); this.weight = weight; this.value = value; valueDensity = value * 1.0 / weight;//乘1.0确保是小数 } @Override public String toString() { return "Article [weight=" + weight + ", value=" + value + ", valueDensity=" + valueDensity + "]"; } } --------- package Greedy; import java.util.Arrays; import java.util.Comparator; import java.util.LinkedList; import java.util.List; public class Knapsack { public static void main(String[] args) { //价值主导 select("价值主导", (Article a1, Article a2) -> { return a2.value - a1.value; }); //重量主导 select("重量主导", (Article a1, Article a2) -> { return a1.weight - a2.value; }); //价值密度主导 select("价值密度主导", (Article a1, Article a2) -> { return Double.compare(a2.valueDensity, a1.valueDensity); }); } //Comparator<Article> cmp 比较器 static void select(String title, Comparator<Article> cmp) { Article[] articles = new Article[] { new Article(35, 10), new Article(30, 40), new Article(60, 30), new Article(50, 50), new Article(40, 35), new Article(10, 40), new Article(25, 30) }; Arrays.sort(articles, cmp); int capacity = 150; int count = 0; int weight = 0; int value = 0; //建立一个动态数组，用来存放选中的东西 List<Article> selectedArticles = new LinkedList<>(); for (int i = 0; i < articles.length && weight < capacity; i++) { int newWeight = weight + articles[i].weight; if (newWeight <= capacity) { weight = newWeight; value += articles[i].value; count++; selectedArticles.add(articles[i]); } } //打印 System.out.println("使用" + title + "的总价值：" + value + "，物品个数为：" + count + "，物品总重量为：" + weight); for (Article article : selectedArticles) { System.out.println(article); } System.out.println("----------"); } } 结果： 使用价值主导的总价值：165，物品个数为：4，物品总重量为：130 Article [weight=50, value=50, valueDensity=1.0] Article [weight=30, value=40, valueDensity=1.3333333333333333] Article [weight=10, value=40, valueDensity=4.0] Article [weight=40, value=35, valueDensity=0.875] ---------- 使用重量主导的总价值：155，物品个数为：5，物品总重量为：140 Article [weight=35, value=10, valueDensity=0.2857142857142857] Article [weight=25, value=30, valueDensity=1.2] Article [weight=10, value=40, valueDensity=4.0] Article [weight=30, value=40, valueDensity=1.3333333333333333] Article [weight=40, value=35, valueDensity=0.875] ---------- 使用价值密度主导的总价值：170，物品个数为：5，物品总重量为：150 Article [weight=10, value=40, valueDensity=4.0] Article [weight=30, value=40, valueDensity=1.3333333333333333] Article [weight=25, value=30, valueDensity=1.2] Article [weight=50, value=50, valueDensity=1.0] Article [weight=35, value=10, valueDensity=0.2857142857142857] ----------