形式陈述

贪心算法按某个局部规则逐步扩展部分解，每一步作当下最优或最安全的选择，并且不回溯此前决定。它是一种设计范式而非自动正确的算法。正确性通常需要证明贪心选择性质：存在某个最优解包含当前选择；以及选择后剩余问题仍具有最优子结构。常用证明形式包括交换论证、领先不变量、割性质和拟阵性质。

直觉

希望每次不可逆地锁定一个不会损害全局最优性的决定。算法的简洁来自“未来无需后悔”，真正困难在于证明这种无后悔性。

例子与边界

区间调度按结束时间最早选择可兼容区间可得到最多区间；按持续时间最短或开始最早则可能失败。Dijkstra 与最小生成树算法也依赖特定非负性或割性质。对 0–1 背包按价值密度贪心不保证最优，而分数背包中该规则正确，说明相似目标的可交换结构可能不同。

推论与应用

贪心法常给线性或近线性算法，并可作为近似算法的骨架。遇到候选规则时，应先构造小反例攻击，再寻找交换引理或结构定理，而不是把“局部最优看起来合理”当作证明。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Part III, greedy algorithms and matroid-style proofs。
• Jon Kleinberg and Éva Tardos, Algorithm Design, Pearson, 2005，Ch. 4, greedy algorithms and exchange arguments。