贪心算法方法论 ​

贪心算法的核心思想：每一步都选择当前看起来最优的方案。

什么是贪心算法？ ​

贪心算法通过一系列局部最优选择，希望达到全局最优。

关键特性：

• 不回溯，一旦做出选择就不更改
• 每一步只考虑当前状态
• 希望局部最优能累积成全局最优

贪心的适用条件 ​

贪心能得到全局最优解需要满足两个条件：

1. 贪心选择性质 ​

每一步的贪心选择都能导向全局最优解。

找零问题：用最少硬币凑出金额
硬币 = [1, 5, 10, 25]

贪心策略：优先用大面额

41 分 = 25 + 10 + 5 + 1 = 4 枚 ✓

但如果硬币 = [1, 3, 4]：
6 分贪心：4 + 1 + 1 = 3 枚
6 分最优：3 + 3 = 2 枚 ✗

2. 最优子结构 ​

问题的最优解包含子问题的最优解。

活动选择问题：
选了一个活动后，剩余时间的活动选择
仍然是相同类型的子问题

贪心 vs 动态规划 ​

常见贪心策略 ​

1. 排序 + 贪心 ​

// 区间调度：按结束时间排序
intervals.sort((a, b) => a[1] - b[1]);

2. 优先队列贪心 ​

// 每次取最大/最小元素
const heap = new MinHeap();
while (!heap.isEmpty()) {
  const min = heap.pop();
  // 处理...
}

3. 逐位/逐元素贪心 ​

// 每个位置选最优
for (let i = 0; i < n; i++) {
  // 选择对位置 i 最优的选项
}

贪心算法模板 ​

function greedy(input: Input): Result {
  // 1. 预处理（通常是排序）
  const sorted = preprocess(input);
  
  // 2. 初始化结果
  let result = initialValue;
  
  // 3. 贪心选择
  for (const item of sorted) {
    if (canChoose(item, result)) {
      result = choose(item, result);
    }
  }
  
  return result;
}

证明贪心正确性 ​

贪心算法的难点不在实现，而在证明。以下是两种常用证明方法。

交换论证法（Exchange Argument） ​

核心思想：假设存在一个最优解与贪心解不同，证明可以通过"交换"操作将其调整为贪心解，且不会变差。

详细步骤：

1. 假设最优解 OPT 与贪心解 G 不同
2. 找到 OPT 与 G 第一个不同的位置 i
3. 在位置 i，交换 OPT 的选择为 G 的选择
4. 证明交换后的解仍是有效解
5. 证明交换后的解不比 OPT 差
6. 重复此过程，直到 OPT 变成 G

示例：活动选择问题

问题：给定若干活动的开始和结束时间，选择最多的不重叠活动。

贪心策略：每次选择结束时间最早的活动。

证明：

设 OPT = {a1, a2, ..., ak} 是最优解（按结束时间排序）
设 G = {g1, g2, ..., gm} 是贪心解

假设 g1 ≠ a1（在第一个位置不同）

因为贪心选择结束最早的，所以 g1.end ≤ a1.end

将 OPT 中的 a1 替换为 g1：
- g1 结束更早，不会与 a2 冲突
- 替换后活动数量不变
- 新解仍是最优解

重复此过程，最终 OPT 变成 G
所以 G 也是最优解 ✓

归纳法（Induction） ​

核心思想：证明每一步贪心选择都保持最优性。

详细步骤：

1. 基础情况：证明第一步贪心选择不会排除最优解
2. 归纳假设：假设前 k 步贪心选择构成的解可以扩展为最优解
3. 归纳步骤：证明第 k+1 步贪心选择后仍可扩展为最优解

示例：分数背包问题

问题：物品可以分割，求最大价值。

贪心策略：按单位价值（价值/重量）排序，优先装单位价值高的。

归纳证明：

基础：选择单位价值最高的物品 x，假设存在最优解不包含 x
      那么用 x 替换最优解中的部分物品，总价值只会更高
      所以最优解一定包含 x（或 x 的一部分）

归纳：假设前 k 个选择构成的部分解 S 可以扩展为最优解
      对于第 k+1 个选择，同样的论证说明它也应该被选择
      所以 S ∪ {第 k+1 个选择} 仍可扩展为最优解

什么时候不能用贪心 ​

识别贪心失效的场景同样重要：

1. 选择之间有复杂依赖

   • 当前选择会影响后续可选项的价值
   • 例：0-1 背包问题

2. 需要全局信息

   • 必须考虑整个输入才能做出正确决策
   • 例：最短路径（Dijkstra 是特殊情况）

3. 存在"回头更优"的情况

   • 当前看起来差的选择，后续可能更优
   • 例：某些找零问题

判断技巧：尝试构造反例。如果能找到贪心策略失效的输入，就需要用 DP。

经典贪心问题 ​

1. 区间调度：选择最多不重叠区间
2. 跳跃游戏：能否到达终点
3. 分发糖果：最少糖果满足约束
4. 加油站：能否绕一圈
5. 任务调度：最少等待时间

后续章节将逐一实战这些问题。