贪心算法的正确性

贪心算法（Greedy Algorithm）是一类在每一步都做出当前最优选择，期望通过局部最优达到全局最优的算法。

正确性判定的核心思想

贪心算法并不总是正确，只有满足特定条件时才可用。判断贪心算法正确性的常用方法有：

1. 最优子结构

• 问题的最优解包含其子问题的最优解。
• 例：最短路径、区间调度。

2. 无后效性

• 某一步的选择不会影响后续状态，只与当前状态有关。
• 例：活动选择问题。

3. 贪心选择性质

• 通过局部最优选择能得到全局最优解。
• 例：找零问题、哈夫曼编码。

常见证明方法

1. 反证法：假设贪心解不是最优解，构造矛盾。
2. 归纳法：证明每一步贪心选择后，剩下的子问题仍满足贪心性质。
3. 交换法：将最优解中的非贪心选择与贪心选择交换，最终可变为贪心解且不劣于原解。

典型例题

1. 区间选点/区间调度

• 每次选择右端点最小的区间，能保证全局最优。
• 证明：交换法或反证法。

2. 找零问题

• 每次优先用面值最大的硬币。
• 只有当硬币面值满足特定条件（如完全背包、标准币种）时贪心才正确。

3. 哈夫曼编码

• 每次合并权值最小的两个节点。
• 归纳法证明其最优性。

反例：贪心不正确的情况

• 有些问题贪心不能保证最优，如背包问题（0-1背包）、部分图最短路等。

总结

• 贪心算法正确性需严格证明，不能凭直觉。
• 常用最优子结构、无后效性、贪心选择性质三大标准。
• 证明方法以反证法、归纳法、交换法为主。

---

参考：

• OI Wiki: 贪心