illegalCreed

中文

English

中文

English

Appearance

入门：局部最优与全局最优的赌博 ​

基于通用算法概念 · 核于 2026-07

速查 ​

  • 定义：贪心算法在每一步都做出「当前看来最好」的选择，不回退、不枚举所有可能，期望局部最优叠加成全局最优——它的核心是「只看眼前」。
  • 成立两条件（缺一不可）：①贪心选择性质（Greedy-choice property）——全局最优解可以由局部最优（贪心）选择组成，即「每步贪心选择都安全」；②最优子结构（Optimal substructure）——做出贪心选择后，剩下的子问题的最优解 + 这个选择 = 原问题最优解。两者都成立贪心才正确。
  • 与 DP 的核心区别：DP 枚举所有子问题择优（会回退、考虑所有分支）；贪心一条路走到底（每步只选当前最优，不回头）。代价：DP 给最优解但慢，贪心快但不一定对——能用贪心的前提是能证明「贪心选择性质」。
  • 贪心不一定正确（最大陷阱）：「每步选当前最优」在直觉上很自然，但没有证明就贸然用往往出错。典型反例：非标准币制找零（币制 1/3/4，凑 6：贪心 4+1+1=3 枚，最优 3+3=2 枚）、0-1 背包用单位价值贪心。
  • 正确策略的两步套路：①排序（按某种「优先级」排序，这是贪心策略的灵魂）；②逐个选择（遍历排序后的元素，按规则选或不选）。几乎所有贪心题都是「排序 + 一个 for」。
  • 排序键决定成败：活动选择按结束时间排序正确（选最多不重叠），按开始时间或按时长最短排序都错——排序键选错整个策略崩。
  • 证明方法：①交换论证（Exchange argument，最常用）——假设最优解与贪心解不同，把最优解逐步「交换」成贪心解且不劣化；②数学归纳；③反证法。
  • 贪心 vs DP 的取舍口诀：能证明局部最优 ⇒ 全局最优用贪心（快）；证明不了或反例存在用 DP（保底最优）。工程上贪心优先尝试，错了再上 DP。
  • 经典问题清单：活动选择 / 区间调度（按结束时间）、跳跃游戏（最远可达）、分发糖果（双向扫描）、Huffman 编码（优先队列）、找零（标准币制成立）、Dijkstra / Prim / Kruskal（本质贪心）。
  • 复杂度：典型贪心 = 排序 O(n log n) + 扫描 O(n) = O(n log n)；空间 O(1) 或 O(n)（排序）——远快于 DP。
  • 本质是图最优化思想：贪心把「全局最优化」降级为「一系列局部最优化的叠加」，牺牲通用性换取速度——它对的问题极快，错的问题彻底错。
  • 进阶顺序：贪心策略与正确性证明 → 经典贪心问题 → 参考。

一、核心思想：只看眼前的赌博 ​

贪心算法的心智模型可以用一句话概括：「每一步都做当前最好的选择，并且绝不反悔」。

全局最优 = 第1步局部最优 + 第2步局部最优 + ... + 第n步局部最优  （前提：可证明）

它和暴力枚举、DP 的根本区别在于不回退、不分叉：

  • 暴力枚举：把所有可能的组合都试一遍，选最优——O(2ⁿ)，必然正确但慢到无法接受。
  • DP：把大问题拆成子问题，枚举每个子问题的所有选择择优（记忆化避免重复）——多项式时间，给最优解。
  • 贪心：每个子问题只做一个选择（当前最优），不枚举其他可能——O(n log n)，但正确性需要单独证明。
枚举：  A → B → C → ...      （所有分支）
        A → B → D → ...
        A → E → F → ...      （指数级）
DP：    A → {B,E} → ...      （每步枚举所有选择，择优）
贪心：  A →（只选最优）→ 一条路走到底   （线性，但不保证对）

贪心之所以快，是因为它放弃了「比较所有可能」；贪心之所以危险，也是因为它放弃了「比较所有可能」——这个取舍必须靠「贪心选择性质」的证明来兜底。

二、成立两条件：缺一不可 ​

一个最优化问题能用贪心正确求解，必须同时满足两个性质：

条件一：贪心选择性质（Greedy-choice property） ​

全局最优解可以由局部最优（贪心）选择组成——换句话说，「每一步做出贪心选择，都不会偏离最优解」。

  • 直觉：存在一个最优解，它在第一步就做了贪心选择。
  • 这是贪心区别于 DP 的关键：DP 的最优解不一定包含「当前最优」的子选择（可能要为全局让步）；贪心要求「当前最优」一定被某个最优解采纳。
  • 例：活动选择问题中，「结束最早的活动」一定被某个「选最多活动」的最优方案采纳——这就是贪心选择性质。

条件二：最优子结构（Optimal substructure） ​

做出贪心选择后，剩下的子问题的最优解 + 这个贪心选择 = 原问题的最优解。

  • 这是贪心和 DP 共享的性质：子问题独立、最优解可组合。
  • 例：选了结束最早的活动后，剩下的「在该活动结束后能选的最多活动数」是一个规模更小的同类子问题——它的最优解加上已选的活动就是原问题最优解。

记忆点：贪心选择性质 = 「第一步贪心安全」；最优子结构 = 「之后每步都安全地递归下去」。两个都成立，贪心才正确。DP 只需要最优子结构（不要求贪心选择性质，因为它枚举所有选择）。

三、与 DP 的区别：一条路 vs 枚举所有 ​

维度贪心DP
决策方式每步只选当前最优，不回退枚举每个子问题的所有选择择优
前提条件贪心选择性质 + 最优子结构最优子结构 + 重叠子问题
正确性不一定对（需证明）一定给最优解
时间复杂度O(n log n)（排序 + 扫描）O(n²) ~ O(n³)，常偏大
空间O(1) ~ O(n)O(n²)（状态表）
典型场景活动选择、Huffman、Dijkstra背包、最长公共子序列、编辑距离

取舍口诀：「能证明局部最优推全局最优 → 贪心（快）；证明不了或有反例 → DP（保底）」。工程实践里，贪心常作为「第一尝试」——对了就省事，错了（举出反例）再上 DP。

四、贪心不一定正确：最危险的陷阱 ​

「每步选当前最优」在直觉上极其自然，但没有证明就贸然使用，往往是错的。看两个经典反例：

反例一：非标准币制找零 ​

币制 {1, 3, 4}，凑金额 6，求最少硬币数。

  • 贪心策略（每次选不超余题认可的最大面值）：6 → 选 4（剩 2）→ 选 1（剩 1）→ 选 1（剩 0）= 3 枚 {4,1,1}。
  • 真实最优：6 → 选 3（剩 3）→ 选 3（剩 0）= 2 枚 {3,3}。

贪心给出 3 枚，但最优是 2 枚——贪心失效。原因：贪心选择性质不成立（选最大的 4 反而偏离最优）。这种问题必须用 DP（零钱兑换）。

反过来，标准币制（如 {1,5,10,25} 美分）找零贪心成立——因为币制设计满足「大面值是小面值的倍数关系」，可证明贪心选择性质。所以「找零能用贪心吗」答案取决于币制。

反例二：0-1 背包按单位价值贪心 ​

背包容量 50，物品：A（价值 60，重量 10，单位 6）、B（价值 100，重量 20，单位 5）、C（价值 120，重量 30，单位 4）。

  • 贪心策略（按单位价值降序，能装就装）：先装 A（60，剩容量 40）→ 装 B（100，剩容量 20）→ C 装不下 = 总价值 160。
  • 真实最优：装 B + C = 100 + 120 = 220。

贪心给出 160，最优是 220——贪心失效。原因：0-1 背包物品不可分割，贪心选择性质不成立，必须用 DP（0-1 背包）。注意分数背包（物品可分割）贪心成立——这正是贪心与 DP 的分水岭之一。

五、贪心的两步套路 ​

几乎所有贪心问题都可以归结为「排序 + 一个 for 循环」：

1. 设计排序键（优先级）—— 贪心策略的灵魂
2. 按排序键排序
3. 遍历排序后的元素，按规则「选或不选」

以活动选择为例：n 个活动各有开始/结束时间，选最多不重叠活动。

js
function activitySelection(acts) {
  // 1. 排序键：按结束时间升序（这是策略的灵魂，证明见后）
  acts.sort((a, b) => a.end - b.end);
  // 2. 贪心选择：第一个（结束最早）必选，之后每个不与上一个冲突就选
  const selected = [acts[0]];
  let lastEnd = acts[0].end;
  for (let i = 1; i < acts.length; i++) {
    if (acts[i].start >= lastEnd) {       // 不冲突
      selected.push(acts[i]);
      lastEnd = acts[i].end;
    }
  }
  return selected;                        // 返回最多不重叠活动
}

复杂度：排序 O(n log n) + 扫描 O(n) = O(n log n)——远快于 DP 的 O(n²)。但这一切的前提是：「按结束时间排序」这个贪心策略被证明了正确（用交换论证，见下一节）。

下一步 ​

理解了贪心的核心思想与成立条件后，下一步要解决两个关键问题：怎么设计贪心策略（排序键怎么选）和怎么证明它对（交换论证），见贪心策略与正确性证明。