贪心 • CoderXL's Blog

贪心（Greedy）算法用于解决最优化问题，它的时间复杂度低于动态规划，但不保证解的最优性（一般情况下只能找到次优解）。

流程#

贪心适用于这样的问题：问题的解由一系列选择构成，而每一步都做“当前看起来最优”的选择，希望局部最优最终能导向全局最优。

对于一系列优化问题，比如最大化收益、最小化代价、最少步骤、最短时间、最优方案等等，贪心就是：

从当前状态出发
立即做一个最优决策
做完后不反悔
继续处理剩余问题

这通常与人类的决策方式接近。

一个栗子：找零钱#

给定不同面值的硬币无限枚，要求用最少的硬币数量凑出特定的金额。

容易想到的贪心方式是，优先使用面值最大的硬币凑剩余金额，再使用面值较小的。

第一种情况：

面值：1, 5, 10

目标：28

这种情况下贪心策略能导向最优解： $28 = 10 + 10 + 5 + 1 + 1 + 1$ ，共 6 枚。

在所有可能的组合中，这确实是硬币数量最少的方式。

第二种情况：

面值：1, 3, 4

目标：6

贪心的结果是： $6 = 4 + 1 + 1$ ，共 3 枚。

但使用两枚 $3$ 面值的硬币更优。

由此可知，贪心虽然符合直觉且时间复杂度低，但其正确性不能自然保证。

正确性#

实际上，贪心算法只有在问题满足特定性质时才能保证正确。

贪心选择性质#

一个有多阶段选择的问题，如果在任何阶段，当前看来局部最优的选择，一定包含于某个全局最优解中，那么这个问题就具有贪心选择性质。这意味着，当前“短视”的选择，不会导致未来最好的结果变差。这允许我们大胆地贪。

最优子结构#

对于最优子结构的额外分析，可以参考这篇 ↗。

如果一个问题包含子问题，且原问题的最优解包含子问题的最优解，那么该问题就具有最优子结构。这意味着我们可以由小到大，自下而上地最优化每个小问题，然后自然就能得到大问题的最优解。

正确性的论证#

如果可以论证某个问题具有贪心选择性质和最优子结构，那么贪心就是正确的。但这样的证明往往难以想出，因此我们通常使用一些导出的证明方法。一个问题如果满足这些证明，本质上就说明了该问题具有贪心选择性质和最优子结构。

交换论证#

首先假设在某一步中，最优解的选择和贪心的选择不同。

然后证明：把这一步的选择替换成贪心的选择，不会让解变差。

于是就存在一个最优解包含贪心选择。

数学归纳#

证明最后一步贪心选择是正确的，然后证明去掉最后一步，剩余的问题与原问题面临的选择一样。

选择独立性#

如果可以证明，问题的多个选择之间是互不影响的，那么整体最优自然就是每一步最优。

基于贪心的经典算法#

Huffman 编码#

每次合并权值和最小的两棵树，最终可以得到总权值最小的一棵树。

Kruskal 最小生成树#

每次选最小的且不成环的边，最终可以得到边权和最小的一棵树。

Dijkstra 最短路#

每次选择距离起点最近的还未被处理过的点，并由它延伸到更远的点，最终可以求得每个点距离起点的最短路径长度。

一些题目#

贪心的思想很凝炼，但其应用方式十分多样，需要就题论题。

P1080 [NOIP 2012 提高组] 国王游戏 ↗#

给定一列二元正整数数对 $(a_i,b_i)$ ，要求重新排列这列数对，使得 $\displaystyle{\max_i {\prod_{k=1}^{i-1} a_k \over b_i}}$ 最小（约定 $\prod_{k=1}^0 a_k = 1$ ）。

令 $p_i = \displaystyle{\prod_{k=1}^{i-1} a_k \over b_i}$ ，观察可以知道，交换原序列中相邻的数对 $(a_{i-1}, b_{i-1})$ 和 $(a_i, b_i)$ ，只会改变 $p_{i-1}$ 和 $p_i$ 的值，而不会影响剩余的 $p$ .

由此，令 $A = \prod_{k=1}^{i-2}a_k$ ，有 $\displaystyle{p_{i-1}=A {1 \over b_{i-1}},\ p_i = A {a_{i-1} \over b_i}}$ .

而交换之后 $p'_{i-1} = \displaystyle{A {1 \over b_i}}$ ， $p'_i = \displaystyle{A {a_i \over b_{i-1}}}$ .

如果交换能使答案变小，那么必有 $\max\{p'_{i-1}, p'_i\} < \max\{p_{i-1},p_i\}$ .

又因为 $p_{i-1} < p'_i \le \max\{p'_{i-1}, p'_i\}$ ，因此上式要成立，必然有 $\max\{p'_{i-1}, p'_i\} < p_i$ . 此外， $p'_{i-1} < p_i$ 自然满足，因此只需要 $p'_i < p_i$ 即可。

也就是说，只要满足 $a_{i-1}b_{i-1} > a_ib_i$ ，交换 $(a_{i-1}, b_{i-1})$ 和 $(a_i, b_i)$ 就能让 $\max\{p_{i-1}, p_i\}$ 减小，且不改变其它 $p$ .

现在一种贪心的方式就呼之欲出了：所有 $(a_i,b_i)$ 按照 $a_ib_i$ 的值从小到大排序。

使用交换论证容易证明其正确性：假设有一种最优解里面存在 $a_{i-1}b_{i-1} > a_ib_i$ 的情况，那么采用我们的贪心策略交换 $(a_{i-1}, b_{i-1})$ 和 $(a_i, b_i)$ ，一定不会让解变得更差（这里是变好了）。因此贪心是正确的。

P2887 [USACO07NOV] Sunscreen G ↗#

想要把防晒霜分配给最多的奶牛，乍一看似乎存在很多贪心方法。比如说，把防晒霜从小到大排序，再把奶牛按照下限从小到大排序，然后依次尽可能分配。

然而，这样贪心是不对的。比如奶牛 1 的范围是 $[1,5]$ ，奶牛 2 的范围是 $[2,3]$ ，防晒霜有 $2,4$ 两瓶。按照当前的贪心策略，第一瓶分配给奶牛 1 之后，奶牛 2 就被迫没有防晒霜可用了。但实际上具有更好的解。

正确的贪心方式是，将奶牛按照上界从小到大排序，防晒霜从小到大排序，然后给每个奶牛分配可能的最小的防晒霜。

使用交换论证容易证明其正确性：假设有一种最优的分配方式，其中的奶牛按照上界从小到大排序之后，存在某个最靠前的奶牛 $i$ ，使得它对应的防晒霜 $s_i$ 不是他那种情况下的可能的最小的防晒霜 $s^*$ （即 $s_i>s^*$ ），那么分类讨论： ① 如果 $s^*$ 没有分配给任何奶牛，此时把 $s^*$ 分配给奶牛 $i$ 而放弃 $s_i$ ，不会让解变差； ② 如果 $s^*$ 分配给了某个奶牛 $j$ ，则 $j>i$ （否则 $s^*$ 不可能是奶牛 $i$ 的合法选项），因此 $j$ 的上界大于 $i$ 的上界，因此可以把 $s_i$ 分配给 $j$ ，而把 $s^*$ 分配给 $i$ ，同样不会导致结果变差。

综上，贪心是正确的。