算法策略 - 贪心

目录

贪心（Greedy）

练习1 – 最优装载问题（加勒比海盗）

问题

思路

代码实现

练习2 – 零钱兑换

问题

思路

代码实现

贪心策略中存在的问题

注意:

练习3 – 0-1背包

问题

思路

实例分析

代码实现

---

贪心（Greedy）

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

贪心的应用:
哈夫曼树
最小生成树算法：Prim、Kruskal
最短路径算法：Dijkstra

练习1 – 最优装载问题（加勒比海盗）

问题

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

思路

贪心策略：每一次都优先选择重量最小的古董

1. 选择重量为 2 的古董, 剩重量 28
2. 选择重量为 3 的古董, 剩重量 25
3. 选择重量为 4 的古董, 剩重量 21
4. 选择重量为 5 的古董, 剩重量 16
5. 选择重量为 7 的古董, 剩重量 9

最多能装载 5 个古董

代码实现

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(weights[i]);
            }
        }
        
        System.out.println("一共选了" + count + "件古董");
    }
}

练习2 – 零钱兑换

问题

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

思路

贪心策略：每一次都优先选择面值最大的硬币

1. 选择25分的硬币, 剩16分
2. 选择10分的硬币, 剩6分
3. 选择5分的硬币, 剩1分
4. 选择1分的硬币

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

代码实现

 static void coinChange(Integer[] faces, int money) {
    // 1 5 20 25
    Arrays.sort(faces);
    int coins = 0, idx = faces.length - 1;
    while (idx >= 0) {
        while (money >= faces[idx]) {
            System.out.println(faces[idx]);
            money -= faces[idx];
            coins++;
        }
        idx--;
    }
    System.out.println(coins);
}

贪心策略中存在的问题

假设有 25 分、20 分、5 分、1 分的硬币，现要找给客户 41 分的零钱，如何办到硬币个数最少？
贪心策略：每一步都优先选择面值最大的硬币

1. 选择 25 分的硬币，剩 16 分
2. 选择 5 分的硬币，剩 11 分
3. 选择 5 分的硬币，剩 6 分
4. 选择 5 分的硬币，剩 1 分
5. 选择 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) 价值主导：优先选择价值最高的物品放进背包
(2) 重量主导：优先选择重量最轻的物品放进背包
(3) 价值密度主导：优先选择价值密度最高的物品放进背包（价值密度 = 价值 ÷ 重量）

实例分析

假设背包最大承重150, 7个物品如表格所示

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

代码实现

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.weight;
        });
        select("价值密度主导", (Article a1, Article a2) -> {
            return Double.compare(a2.valueDensity, a1.valueDensity);
        });
    }
    
    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, weight = 0, 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;
                selectedArticles.add(articles[i]);
            }
        }
        
        System.out.println("【" + title + "】");
        System.out.println("总价值：" + value);
        for (int i = 0; i < selectedArticles.size(); i++) {
            System.out.println(selectedArticles.get(i));
        }
        System.out.println("-----------------------------");
    }
}

public class Article {
    public int weight;
    public int value;
    public double valueDensity;
    public Article(int weight, int value) {
        this.weight = weight;
        this.value = value;
        valueDensity = value * 1.0 / weight;
    }
    @Override
    public String toString() {
        return "Article [weight=" + weight + ", value=" + value + ", valueDensity=" + valueDensity + "]";
    }
}

控制台输出: