贪心算法：当“短视”成为一种智慧 - 每日分享

你可能听过这样的说法：贪心算法目光短浅，只看眼前利益。但恰恰是这种“短视”，在特定问题里能稳定地给出全局最优解。这不矛盾吗？

我先亮出观点：贪心不是瞎选，它是在有数学结构保证的前提下，做出当前最有利的决策。 今天我们就用两个经典问题——活动选择和部分背包——来拆解这种“短视”背后的逻辑。

活动选择：为什么“结束最早”是唯一正确的贪心指标？

先看问题：给定一堆活动，每个有开始和结束时间，同一时间只能参加一个，怎么选最多？

直觉上你可能想选“开始最早的”或者“持续时间最短的”。但这两个策略都能被轻易推翻。

结束时间最早之所以正确，核心在于一个交换论证：假设最优解里第一个活动是 A，而贪心选的是结束最早的 B。由于 B 的结束时间不晚于 A，我把 A 换成 B，剩下的时间段只会更宽裕，不会更紧张。所以贪心选 B 不会比最优解差。

这个论证的关键在于：结束时间决定了你“什么时候能开始下一个”。结束越早，留给后续活动的空间越大。

看一个具体的例子：

活动：  A(1,3)  B(2,4)  C(3,5)  D(0,6)  E(4,7)  F(5,8)

按结束时间排序：A(3) → B(4) → C(5) → D(6) → E(7) → F(8)。

选 A（结束3），下一个从 ≥3 开始，选 C（3-5），再下一个从 ≥5 开始，选 F（5-8）。一共 3 个。

如果选 D（0-6），后面只剩 E(4-7) 冲突、F(5-8) 冲突，只能选 1 个。

代码实现的关键只有两步：

activities.sort(key=lambda x: x[1])  # 按结束时间排序
last_end = 0
for start, end in activities:
    if start >= last_end:  # 不冲突就选
        count += 1
        last_end = end

排序是 O(n log n)，遍历是 O(n)，干净利落。

有一道活动选择的题目，输入 n 个活动的起止时间，要求输出最多能安排的活动数。样例给了 11 个活动，答案是 4。你手动去试各种组合会发现，只有按结束时间贪心才能稳定得到这个结果。

部分背包：单位价值才是那把尺子

活动选择关注的是“时间不冲突”，部分背包关注的是“容量有限，怎么装最值钱”。

区别在于：物品可以切分。你可以拿半块黄金、三分之一袋米。这个“可切分”的性质，是贪心算法能生效的根本原因。

策略很直白：算每个物品的单位价值（价值 ÷ 重量），从高到低拿，装不下整个就切一部分。

为什么这样对？因为如果最优解里没有优先拿单位价值最高的物品，你可以用一小块高单位价值的物品替换掉等重量的低单位价值物品，总价值只会增加。反复替换，最终一定收敛到贪心解。

举个例子：黄金 10 斤值 600（单位 60），白银 20 斤值 800（单位 40），钻石 30 斤值 900（单位 30）。背包容量 50。

贪心：先拿黄金 10 斤（600），剩 40；再拿白银 20 斤（800），剩 20；钻石只能拿 20/30，价值 600。总价值 2000。

如果先拿钻石 30 斤（900），再拿黄金 10 斤（600），剩 10 斤拿白银一半（400），总价值 1900。少了 100。

关键代码就一个排序加一个循环：

items.sort(key=lambda x: x[1] / x[0], reverse=True)
for weight, value in items:
    if capacity >= weight:
        total_value += value
        capacity -= weight
    else:
        total_value += value * (capacity / weight)
        break

注意最后那个 fraction——这是部分背包和 0-1 背包的分水岭。0-1 背包里物品不可分，贪心会翻车，必须上动态规划。

一道采购牛奶的题：贪心藏在细节里

有一道 USACO 的题：你需要采购 N 加仑牛奶，有 M 个奶农，每人有单价 Pi 和最大供应量 Ai。总产量大于需求，求最小花费。

这本质上就是部分背包——你的“背包容量”是需要采购的牛奶总量，每个奶农的牛奶“单位价值”就是单价（越低越好）。贪心策略：按单价从低到高排序，优先买便宜的，买够了就停。

样例：需要 100 加仑，5 个奶农：

单价 5，产量 20
单价 9，产量 40
单价 3，产量 10
单价 8，产量 80
单价 6，产量 30

按单价排序：3(10) → 5(20) → 6(30) → 8(80) → 9(40)。

买 3 元的 10 加仑（花 30），买 5 元的 20 加仑（花 100），买 6 元的 30 加仑（花 180），此时已有 60 加仑，还需 40 加仑，从 8 元的奶农那里买 40 加仑（花 320）。总计 30+100+180+320 = 630。

和样例输出一致。

这题和部分背包的代码结构几乎一样，只是“价值”变成了“成本”，排序方向反过来。贪心的本质不变：每一步都选当前性价比最高的选项。

贪心的边界在哪里

贪心算法有一个容易被忽略的前提：问题必须具有贪心选择性质和最优子结构。

贪心选择性质：每一步的局部最优选择能导致全局最优。
最优子结构：原问题的最优解包含子问题的最优解。

活动选择满足这两条，因为结束时间早的活动不会“堵死”后面的路。部分背包也满足，因为物品可切分意味着你可以随时“微调”选择。

但 0-1 背包不满足贪心选择性质。比如容量 50，物品 A(30斤, 60元, 单位2)、B(20斤, 100元, 单位5)、C(20斤, 90元, 单位4.5)。贪心先拿 B 和 C，总价值 190，但拿 A 和 B 能得到 160？等等，190 > 160，这个例子贪心是对的。换一个：容量 10，物品 A(6斤, 12元, 单位2)、B(5斤, 11元, 单位2.2)、C(5斤, 10元, 单位2)。贪心拿 B（11元），剩 5 斤，再拿 C（10元），总 21。但最优是 A+C = 22。贪心翻车了。

原因就在于：0-1 背包里，你没法把 A 切一半来填补 B 留下的空隙，所以局部最优不保证全局最优。

写代码时容易踩的坑

活动选择按开始时间排序。这是最常见的错误。开始早的活动可能结束很晚，直接堵死后面所有安排。
部分背包按总价值排序。总价值高不代表单位价值高，钻石总价值可能比黄金高，但每斤的价值未必。
忘记处理“装不下整个物品”的情况。部分背包最后一种物品往往只能装一部分，代码里必须有 fraction 的计算，不能直接 += value。
把 0-1 背包当部分背包做。看到“背包”两个字就上贪心，这是条件反射式的错误。先确认物品是否可分割。

进阶方向

贪心的思想远不止这两个问题。哈夫曼编码用贪心构建最优前缀码，Prim 和 Kruskal 用贪心求最小生成树，Dijkstra 用贪心求单源最短路。它们的共同点是：每一步都做一个不可撤销的局部最优决策，且这个决策被数学证明不会损害全局最优性。

建议你学完贪心后，立刻去对比动态规划。同样是背包问题，0-1 背包的 DP 解法会让你更深刻地理解：贪心的“短视”之所以有效，是因为问题结构允许它短视。一旦结构不满足，就必须用 DP 来“记住”之前的决策。

最后留一个思考题：如果活动可以中途退出（参加一半就走），还能用结束时间最早的贪心策略吗？试着构造一个反例，或者证明它仍然成立。

关于作者

我是赵老师，持有 NOI 信息学奥赛教练证书，拥有 15 年以上的软件开发经验，从事信息学少儿编程教学已有 8 年时间。

这些年累计帮助多名学生通过编程特长升入自己心仪的目标学校。

如果你在编程学习上有任何疑问，欢迎联系我：18620372957（微信同号）