一. 贪心算法定义

假设一个问题比较复杂，暂时找不到全局最优解，那么我们可以考虑把原问题拆成几个小问题，分别求每个小问题的最优解，再把这些“局部最优解”叠起来，就“当作”整个问题的最优解了。

1.1 怎么理解贪心

在每一步中，选择当前最优而不是全局最优，这就是贪心。

1.2 贪心思想和分治思想的区别

贪心和分治都是将问题进行拆分来降低求解的复杂度，不同的是，分治保证每个任务相对独立，不考虑最不最优问题；
而贪心子任务间往往存在关联关系，每次取舍之间都选择当前最优。

二. 贪心算法关键步骤

如何知道一个问题是否可以用贪心算法解决呢，分析问题和用贪心解决问题都可以参考一下步骤：

• 分析问题的最优解
• 分析子问题的最优解
• 分析子问题是否可叠加当成问题最优解

三. 经典应用-饼干问题

3.1 问题描述

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

3.2 根据贪心算法步骤拆解

• 分析问题最优解

显而易见，满足最多数量的孩子

• 分析子问题的最优解

对于每个孩子，应该选择可以满足这个孩子的胃口且尺寸最小的饼干

• 分析子问题是否可叠加当成问题最优解

从贪心的角度考虑，应该按照孩子的胃口从小到大的顺序依次满足每个孩子

3.3 推导公式

假设有 m 个孩子，胃口值分别是 g1 到 gm，有 n 块饼干，尺寸分别是 s1 到 sn
我们将两个数列由小到大排序，满足gi <= gi+1 和 sj <= sj+1

可以满足第 i 个孩子的胃口的最小的饼干是第 j 块饼干，即 sj是剩下的饼干中满足 sj >= gi的最小值，
最优解是将第 j 块饼干分配给第 i 个孩子

3.4 代码实现

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;
    }
复制代码

四. 贪心算法可能存在的问题

4.1 “全局最优”和“局部最优”

日常生活中很多情况，全局最优和局部最优有很大的区别，盲目追求全局最优有可能和预期结果大相径庭。

• 岔路问题

看上去短的路可能岔路多，每次选则最短的路可能会绕一圈

• 雪球问题

看上去雪多的路可能路比较短，不如雪粘、路途长的路积累的雪球大

• 打车软件离我最近

每次都是离乘客最近的车接单，那么有些地方的乘客可能永远打不到车

4.2 贪心算法存在的意义

既然贪心算法不能保证全局最优，我们为什么还要需要它呢？

• 当问题规模很大时，在合理的时间内找到全局最优几乎不可能，这时候我们往往会倾向于接受局部最优解，因为局部最优解的质量不一定都是差的。
• 在工程应用领域，有时最优解与局优解的精度相差很小，但为了搜索到全局最优解却需要耗费更长的时间，在权衡计算精度以及时间成本后，决策者往往也能接受局部最优解。

五. 贪心算法应用场景

• 根据前面的描述，我们可以知道贪心算法虽然不全局最优，但如果能保证局部最优极大程度趋近于全局最优，那我们也可以使用贪心算法。
• 如果可以证明决策既不受之前决策的影响，也不影响后续决策，则贪心算法就是确定的最优解算法。除此之外都不可以保证贪心算法是最优的。

好在前人的经验总结了一些条件可以参考：

• 问题有限制值和期望值
• 问题可以通过贪心步骤拆分
• 求全局最优解的数学模型难以建立或计算量过大
• 没有太大必要一定要求出全局最优解，“比较优”就可以

常见场景有：背包问题、分糖果、找零钱、区间覆盖等

六. 贪心算法的优缺点

其实在前文中已经都提到了，这里再总结一下。

• 优点：思路简单、易于实现、处理高效、权衡了最佳解决方案和复杂度。
• 缺点：需要甄别问题场景，对于局部最优和全局最优差异较大的，不能使用。

七. 如何证明贪心算法可以趋近最优解

证明一个场景可以满足“局部最优极大程度趋近于全局最优”往往难于使用贪心求解。
一般来说如果一个问题可以转化为拟阵，那就可以贪心求解。但不是所有可以贪心求解的问题都能转化成拟阵。
拟阵的推导涉及一些数学知识，有兴趣可以看看。拟阵与最优问题