如何判断能否使用贪心
可以按照下面的顺序分析：
- 明确问题模型。 写出输入、输出、约束和优化目标；
- 描述局部选择。 说明每一步究竟按什么指标选候选项；
- 先尝试构造反例。 用小规模数据检查局部最优是否可能导致糟糕的后续选择；
- 证明贪心选择性质。 常见方法包括交换论证和归纳证明；
- 证明剩余问题仍然成立。 说明做出选择后，剩余部分仍是同类的最优子问题；
- 检查边界条件。 确认排序、堆、并查集等辅助结构的使用要求。
“暂时没有找到反例”只能说明策略值得继续研究，不能代替正确性证明。
交换论证
交换论证的基本模板如下：
- 假设存在一个最优解
O，但它的第一步不是贪心选择； - 将
O中与贪心选择冲突的部分替换为贪心选择，得到O'； - 证明
O'仍然可行，且目标值不劣于O； - 因此存在一个以贪心选择开头的最优解；
- 对做出选择后的剩余子问题重复相同论证。
THM定理 · 交换论证的结论
如果每一步都能把任意最优解转换成一个包含当前贪心选择、且目标值不变差的最优解，并且剩余问题保持同类结构，那么重复该过程即可证明贪心算法正确。
活动选择问题中，“最早结束的活动”之所以安全，正是因为可以把某个最优方案的第一个活动替换成它，而不会减少后续可安排的活动数量。
归纳方法
对于逐步构造答案的贪心算法，也可以使用归纳法：
- 基础情况：证明算法在没有选择或只做出第一次选择时正确；
- 归纳假设：假设前
k步选择可以扩展为某个最优解； - 归纳步骤：证明第
k + 1步的贪心选择仍然可以安全加入一个最优解； - 结论：所有选择完成后，算法得到全局最优解。
反例构造
如果无法证明贪心选择安全，可以优先寻找反例。常用办法是：
- 让局部最优选择消耗关键资源；
- 让一个稍小的选择为后续留下更多空间；
- 使用最小规模输入，减少无关因素；
- 对比贪心解和穷举或动态规划得到的最优解。
找零面额 {1, 3, 4}、金额 6 就是典型反例：选择最大的 4 后，剩余金额 2 只能使用两枚 1，而一开始选择两个 3 才能得到最优解。
常见易错点
- 把“每次选择最大值”误认为贪心算法的通用定义；
- 只证明了最优子结构，却没有证明贪心选择性质；
- 把“没有找到反例”写成“算法已经证明正确”；
- 忽略 Dijkstra 的非负边权前提；
- 把分数背包的贪心规则直接套到 0-1 背包；
- 把特定面额集合成立的找零结论推广到任意面额集合；
- 只分析核心循环，遗漏排序、优先队列或并查集的代价。