算法核心-贪心算法

分析&回答

贪心算法就是遵循某种既定原则，不断地选取当前条件下最优的选择来构造每一个子步骤的解决方案，直到获得问题最终的求解。在对问题求解时，总是做出在当前看最好的选择。也就是说，不从整体最优上考虑，所做的仅是在某种意义上的局部最优解。

利用贪心算法解题，需要解决两个问题:

• 问题是否适合用贪心算法求解所求问题是否具有贪心选择性质
  • 贪心选择性质：是指应用同一种规则F，将原问题变为一个相似但规模更小的子问题，后面的每一步都是当前看来最佳的选择。这种选择依赖于已作出的选择，但不依赖与未作出的选择。从全局看，运用贪心策略解决的问题在程序的运行过程中无回溯过程。
• 问题是否具有局部最优解问题具有局部最优解，从而选择一个贪心标准，得到问题的最优解
  解题思路：
  1. 建立对问题精确描述的数学模型，包括定义最优解的模型
  2. 将问题分成一系列子问题，同时定义子问题的最优解结构
  3. 应用贪心算法可以确定每个子问题局部最优，并根据最优模型，用子问题的局部最优解堆叠出全局最优解

贪心算法解决问题 （种花问题）

假设有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花不能种植在相邻的地块上，它们会争夺水源，两者都会死去。

给你一个整数数组  flowerbed 表示花坛，由若干 0 和 1 组成，其中 0 表示没种植花，1 表示种植了花。另有一个数 n ，能否在不打破种植规则的情况下种入 n 朵花？能则返回 true ，不能则返回 false。

class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int count = 0;
        int m = flowerbed.length;
        int prev = -1;
        for (int i = 0; i < m; i++) {
            if (flowerbed[i] == 1) {
                if (prev < 0) {
                    count += i / 2;
                } else {
                    count += (i - prev - 2) / 2;
                }
                if (count >= n) {
                    return true;
                }
                prev = i;
            }
        }
        if (prev < 0) {
            count += (m + 1) / 2;
        } else {
            count += (m - prev - 1) / 2;
        }
        return count >= n;
    }
}

贪心算法解决问题 （分发饼干）

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int numOfChildren = g.length, numOfCookies = s.length;
        int count = 0;
        for (int i = 0, j = 0; i < numOfChildren && j < numOfCookies; i++, j++) {
            while (j < numOfCookies && g[i] > s[j]) {
                j++;
            }
            if (j < numOfCookies) {
                count++;
            }
        }
        return count;
    }
}

题目代码出自LeetCode，请自行查阅。

反思&扩展

其他应用

• 硬币找零问题
• 活动安排问题
• 课程表
• 哈夫曼编码