封面画师：Nengoro(ネんごろぅ) 封面ID：66081569

本文参考视频：小马哥教育(SEEMYGO) 2019年恋上数据结构与算法（第二季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

1. 基本含义

贪心，英文 Greedy，读音 [ˈɡriːdi]，形容词。

贪心策略，也称为贪婪策略。

在贪心策略下，每一步都采取当前状态下最优的选择（局部最优解），从而希望推导出全局最优解。

贪心的应用

哈夫曼树
最小生成树算法：Prim、Kruskal
最短路径算法：Dijkstra

2. 最优装载问题

2.1 问题描述

在北美洲的东南部，有一片神秘的海域，是海盗行为最活跃的加勒比海。

有一天，海盗们截获了一艘装满各种各样古董的货船，每一件古董都价值连城。海盗船的载重量为 W，每件古董的重量为 w_i，贪婪的海盗们应该如何把 尽可能多 的古董装上海盗船呢？

2.2 思路与实现

比如 W 为 30，w_i 分别为 3、5、4、10、7、14、2、11。

最优装载问题的解决可以使用贪心策略：每一次都优先选择重量最小的古董。比如：

选择重量为 2 的古董，剩重量 28
选择重量为 3 的古董，剩重量 25
选择重量为 4 的古董，剩重量 21
选择重量为 5 的古董，剩重量 16
选择重量为 7 的古董，剩重量 9
此时古董最小的总量是 10，超过海盗船剩余载重量，因此最多能装载 5 个古董

/**
 * @author mofan
 * @date 2022/11/12 14:24
 */
public class Pirate {
    public static void main(String[] args) {
        int[] weights = {3, 5, 4, 10, 7, 14, 2, 11};
        // 先排序
        Arrays.sort(weights);

        int capacity = 30, weight = 0, count = 0;

        for (int i = 0; i < weights.length && weight < capacity; i++) {
            int newWeight = weight + weights[i];
            if (newWeight <= capacity) {
                weight = newWeight;
                count++;
            }
        }

        System.out.println("选取的货物数量为: " + count); // 5
    }
}

3. 零钱兑换

3.1 问题描述与解决思路

假设现有若干枚 25 分、10 分、5 分、1 分的硬币，需要找给客户 41 分的零钱，如何使硬币个数最少？

同样可以使用贪心策略：每一次都优先选择面值最大的硬币。比如：

选择 25 分的硬币，剩 16 分
选择 10 分的硬币，剩 6 分
选择 5 分的硬币，剩 1 分
选择 1 分的硬币

最终的解是共 4 枚硬币，即 25 分、10 分、5 分、1 分硬币各一枚。

/**
 * @author mofan
 * @date 2022/11/12 14:37
 */
public class CoinChange {
    public static void main(String[] args) {
        coinChange(new Integer[]{25, 10, 5, 1}, 41);
    }

    static void coinChange(Integer[] faces, int money) {
        // 从大到小排序
        Arrays.sort(faces, (o1, o2) -> o2 - o1);

        int coins = 0, i = 0;

        while (i < faces.length) {
            if (money < faces[i]) {
                i++;
                continue;
            }

            money -= faces[i];
            coins++;
        }

        System.out.println("最终的硬币个数为: " + coins); // 4
    }
}

3.2 问题的变体

假设现有若干枚 25 分、20 分、5 分、1 分的硬币，需要找给客户 41 分的零钱，如何使硬币个数最少？

按照先前的思路，继续使用贪心策略：

选择 25 分的硬币，剩 16 分
选择 5 分的硬币，剩 11 分
选择 5 分的硬币，剩 6 分
选择 5 分的硬币，剩 1 分
选择 1 分的硬币

最终给客户的硬币是 1 枚 25 分、3 枚 5 分、1 枚 1 分的硬币，共 5 枚硬币。使用先前的程序测试一下：

public static void main(String[] args) {
    coinChange(new Integer[]{25, 10, 5, 1}, 41); // 4
    coinChange(new Integer[]{25, 20, 5, 1}, 41); // 5
}

但这是最优解吗？ 🤔

其实一眼就能看出来本题的最优解是：2 枚 20 分、1 枚 1 分的硬币，共 3 枚硬币。

另一种解题思路

结果与先前的思路无异，但或许更好理解。

同样先排序，只不过不在按照从大到小排，而是按照默认的从小到大排。

为了使枚数最少，同样得先选取最大面额的硬币，只不过此时最大面额的硬币是在排序后的数组末位。选取硬币之后，检查剩下未找零的钱是否比当前选取的硬币面额大，如果面额比选取的硬币大，证明还能再选一枚相同的硬币，反之以后再也不选取当前选择的硬币，而是选取稍小于当前选取硬币面额的硬币。重复这个操作，直到找零完成。

static void coinChange(Integer[] faces, int money) {
    // 默认从小到大排
    Arrays.sort(faces);
    int coins = 0, idx = faces.length - 1;

    while (idx >= 0) {
        while (money >= faces[idx]) {
            money -= faces[idx];
            coins++;
        }
        idx--;
    }
    System.out.println(coins);
}

3.3 贪心策略的注意事项

贪心策略不一定能得到全局最优解。贪心策略没有尝试所有可能的解，容易过早做决定，所以没法达到最佳解。

贪心策略的优点：简单、高效、无需穷举所有可能，通常作为其他算法的辅助算法来使用。

贪心策略的缺点：不从整体上考虑其他可能，每次采取局部最优解，不会再回溯，因此难以得到最优解。

4. 0 - 1 背包

现有 n 件物品和一个最大承重为 W 的背包，每件物品的重量是 w_i、价值是 v_i。在保证总重量不超过 W 的前提下，将哪几件物品装入背包，可以使得背包的总价值最大？

注意：每个物品只有 1 件，也就是每个物品要么放入背包，要么不放入背包，即只能选择 0 件或者 1 件，因此称为 0 - 1 背包问题。

如果采取贪心策略，有 3 个方案：

价值主导：优先选择价值最高的物品放进背包
重量主导：优先选择重量最轻的物品放进背包
价值密度主导：优先选择价值密度最高的物品放进背包（价值密度 = 价值 ÷ 重量）

实例分析

假设背包最大承重为 150，共有 7 个物品如下表所示：

编号	1	2	3	4	5	6	7
总量	35	30	60	50	40	10	25
价值	10	40	30	50	35	40	30
价值密度	0.29	1.33	0.5	1.0	0.88	4.0	1.2

使用给出的三种方案进行选择：

价值主导：放入背包的物品编号是 4、2、6、5，总重量 130，总价值 165；
重量主导：放入背包的物品编号是 6、7、2、1、5，总重量 140，总价值 155；
价值密度主导：放入背包的物品编号是 6、2、7、4、1，总重量 150，总价值 170。

显然，价值密度主导是三种方案中最优的。

编码实现

首先定义物品类，拥有价值、重量、价值密度三个字段：

/**
 * @author mofan
 * @date 2022/11/12 16:02
 */
public class Article {
    public int weight;
    public int value;
    public double valueDensity;

    public Article(int weight, int value) {
        this.weight = weight;
        this.value = value;
        this.valueDensity = value * 1.0 / weight;
    }

    @Override
    public String toString() {
        return "Article{" +
                "weight=" + weight +
                ", value=" + value +
                ", valueDensity=" + valueDensity +
                '}';
    }
}

使用给出的三种方案，求出对应方案下选择的总价值：

/**
 * @author mofan
 * @date 2022/11/12 16:04
 */
public class Knapsack {
    public static void main(String[] args) {
        select("价值主导", (o1, o2) -> o2.value - o1.value);
        select("重量主导", Comparator.comparingInt(o -> o.weight));
        select("价值密度主导", (o1, o2) -> Double.compare(o2.valueDensity, o1.valueDensity));
    }

    static void select(String title, Comparator<Article> comparator) {
        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, comparator);

        int capacity = 150, weight = 0, value = 0;
        List<Article> selectedArticles = new ArrayList<>();

        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;
                selectedArticles.add(articles[i]);
            }
        }

        System.out.println("[" + title + "]");
        System.out.println("总价值为: " + value);
        selectedArticles.forEach(System.out::println);
        System.out.println("----------------------------------");
    }
}

运行代码后有：

总价值为: 165
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
Article{weight=10, value=40, valueDensity=4.0}
Article{weight=25, value=30, valueDensity=1.2}
Article{weight=30, value=40, valueDensity=1.3333333333333333}
Article{weight=35, value=10, valueDensity=0.2857142857142857}
Article{weight=40, value=35, valueDensity=0.875}
----------------------------------
[价值密度主导]
总价值为: 170
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}
----------------------------------