本篇文章是利用了简单的例题，对贪心算法进行理解，并没有用到特别难的题，只是单独的利用了贪心算法，后续会对贪心算法进行例题式详解

含义： 贪心策略，也称为贪婪策略 每一步都采取当前状态下最优的选择（局部最优解），从而希望推导出全局最优解
贪心的应用：
哈夫曼树
最小生成树算法：Prim、Kruskal
最短路径算法：Dijkstra

最优装载问题（加勒比海盗）

题目：
在北美洲东南部，有一片神秘的海域，是海盗最活跃的加勒比海 有一天，海盗们截获了一艘装满各种各样古董的货船，每一件古董都价值连城，一旦打碎就失去了它的价值
海盗船的载重量为 W，每件古董的重量为 𝑤i，海盗们该如何把尽可能多数量的古董装上海盗船？
比如 W 为 30，𝑤i 分别为 3、5、4、10、7、14、2、11

贪心策略：每一次都优先选择重量最小的古董
① 选择重量为 2 的古董，剩重量 28
② 选择重量为 3 的古董，剩重量 25
③ 选择重量为 4 的古董，剩重量 21
④ 选择重量为 5 的古董，剩重量 16
⑤ 选择重量为 7 的古董，剩重量 9
最多能装载 5 个古董 

  1. public static void main(String[] args) {
  2.         int[] weights = {3, 5, 4, 10, 7, 14, 2, 11};
  3.         Arrays.sort(weights);
  4.         int capacity = 30, weight = 0, count = 0;
  6.         for (int i = 0; i < weights.length && weight < capacity; i++) {
  7.             int newWeight = weight + weights[i];
  8.             if (newWeight <= capacity) {
  9.                 weight = newWeight;
  10.                 count++;
  11.                 System.out.println(weights[i]);
  12.             }
  13.         }
  15.         System.out.println("一共选了" + count + "件古董");
  16.     }

零钱兑换

题目：
假设有 25 分、10 分、5 分、1 分的硬币，现要找给客户 41 分的零钱，如何办到硬币个数最少？

贪心策略：每一次都优先选择面值最大的硬币
① 选择 25 分的硬币，剩 16 分
② 选择 10 分的硬币，剩 6 分
③ 选择 5 分的硬币，剩 1 分
④ 选择 1 分的硬币
最终的解是共 4 枚硬币 25 分、10 分、5 分、1 分硬币各一枚

  1. public static void main(String[] args) {
  2.         int[] a={25,5,10,1};
  3.         Arrays.sort(a);
  4.         int money=50;
  5.         int coins=0;
  6.         for(int i=a.length-1;i>=0;i--){
  7.             if(money<a[i]){
  8.                 continue;
  9.             }
  10.             money-=a[i];
  11.             i++;
  12.             coins++;
  13.         }
  14.         System.out.println(coins);
  15.     }

另一种方式的零钱兑换

题目：
假设有 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 枚硬币

注意

贪心策略并不一定能得到全局最优解
因为一般没有测试所有可能的解，容易过早做决定，所以没法达到最佳解
贪图眼前局部的利益最大化，看不到长远未来，走一步看一步 优点：简单、高效、不需要穷举所有可能，通常作为其他算法的辅助算法来使用
缺点：鼠目寸光，不从整体上考虑其他可能，每次采取局部最优解，不会再回溯，因此很少情况会得到最优解
其实我们多数关于贪心算法的题解并不是单单只用了贪心算法，多数都会搭配上动态规划来进行配合解题
**

0-1背包

问题：
有 n 件物品和一个最大承重为 W 的背包，每件物品的重量是 𝑤i、价值是 𝑣i
在保证总重量不超过 W 的前提下，将哪几件物品装入背包，可以使得背包的总价值最大？
注意：每个物品只有 1 件，也就是每个物品只能选择 0 件或者 1 件，因此称为 0-1背包问题

如果采取贪心策略，有3个方案
① 价值主导：优先选择价值最高的物品放进背包
② 重量主导：优先选择重量最轻的物品放进背包
③ 价值密度主导：优先选择价值密度最高的物品放进背包（价值密度 = 价值 ÷ 重量）
image.png
因为不是在leetcode中直接做题，所以我们做题前需要实现一个实体类

示例：

  1. //存储物品的实体类    
  2. public class Article {
  3.     public int weight;
  4.     public int value;
  5.     public double valueDensity;
  6.     public Article(int weight, int value) {
  7.         this.weight = weight;
  8.         this.value = value;
  9.         valueDensity = value * 1.0 / weight;
  10.     }
  11.     @Override
  12.     public String toString() {
  13.         return "Article [weight=" + weight + ", value=" + value + ", valueDensity=" + valueDensity + "]";
  14.     }
  15. }
  17. //实现类
  18. public class Knapsack {
  19.     public static void main(String[] args) {
  20.         select("价值主导", (Article a1, Article a2) -> {
  21.             return a2.value - a1.value;
  22.         });
  23.         select("重量主导", (Article a1, Article a2) -> {
  24.             return a1.weight - a2.weight;
  25.         });
  26.         select("价值密度主导", (Article a1, Article a2) -> {
  27.             return Double.compare(a2.valueDensity, a1.valueDensity);
  28.         });
  29.     }
  31.     static void select(String title, Comparator<Article> cmp) {
  32.         Article[] articles = new Article[] {
  33.             new Article(35, 10), new Article(30, 40),
  34.             new Article(60, 30), new Article(50, 50),
  35.             new Article(40, 35), new Article(10, 40),
  36.             new Article(25, 30)
  37.         };
  38.         Arrays.sort(articles, cmp);
  40.         int capacity = 150, weight = 0, value = 0;
  41.         List<Article> selectedArticles = new LinkedList<>();
  42.         for (int i = 0; i < articles.length && weight < capacity; i++) {
  43.             int newWeight = weight + articles[i].weight;
  44.             if (newWeight <= capacity) {
  45.                 weight = newWeight;
  46.                 value += articles[i].value;
  47.                 selectedArticles.add(articles[i]);
  48.             }
  49.         }
  51.         System.out.println("【" + title + "】");
  52.         System.out.println("总价值：" + value);
  53.         for (int i = 0; i < selectedArticles.size(); i++) {
  54.             System.out.println(selectedArticles.get(i));
  55.         }
  56.         System.out.println("-----------------------------");
  57.     }
  58. }

我们在实现类中用到了选择器，既然说到了，我们学习一下（有空肯定补）

本文代码均可进行复制粘贴到编译器，后进行debug，来了解代码运行过程
有问题可进行留言，博主看后回复