跳到主要内容

贪心

贪心算法适用于解决无后效性（或者可以证明后效性不会使方案更劣）、具有最优子问题结构（一个问题的最优解包含其子问题的最优解）的问题。

贪心算法和 DP 的思想有点相近。

不同的是，DP 会列举所有可能成为最优解的解，然后比较后得到最优解（状态转移）。DP 的时间复杂度往往比较大，多数为 $O(n^2)$ ，也有少数的 $O(n)$ 线性 DP；贪心算法会按照一定的策略选择最优解，不需要统计每种可能，复杂度较小，往往在 $O(n)$ 。

笔者的一点经验：如果一道题 DP 会超时，除了考虑降维，还可以考虑改成贪心。

证明贪心法正确常用的方法：

归纳法： 分类讨论，证明每种情况下贪心都正确。
反证法： 假设有更优解，证明更优解不存在。
调整法： 从贪心得到的解出发，做一些微调（例如交换 $i,j$ ），证明调整后都不会更优（当前方案不比调整后更劣）。
公式法： 推式子（一般是不等式），没什么好说的。

下面会介绍一些经典的题型。

排序类贪心

排序类贪心是指：为了最小化 / 最大化某个指标，我们需要设计一个排列，而我们通过设计一种排序方法来求出这个特定的排列。

其中一种有效的方法就是邻项交换排序，即我们讨论序列中相邻的两个项 $i,j$ ，考虑交换它们的影响，以及如何排列 $i,j$ 可以实现指标最大化 / 最小化。

Johnson 法则

Johnson 法则用于解决一类特化的排序类贪心问题，例如：P1248 加工生产调度。以 P1248 为例，我们可以按照如下法则对所有产品排序，使得总加工时长最短：

对于产品 $i$ ，令 $d_i= \begin{cases} -1 & A_i<B_i,\\ 0 & A_i=B_i,\\ 1 & A_i>B_i. \end{cases}$
$d_i\not=d_j$ 时，对所有产品以 $d_i$ 为关键字升序排序。
$d_i=d_j$ $d_{i} = d_{j}$ 时，
1. 若 $d\le0$ ，以 $A$ 升序排序；
2. 否则，以 $B$ 降序排序。

例题

P1080 国王游戏
P1248 加工生产调度（Johnson 法则）

另请参阅

排序类贪心