贪心算法

贪心算法的表面动作是“现在就决定”，背后的证明图像却是“总能把一个最优解调整到同意这个决定”。若调整不会降低目标值，也不会破坏可行性，那么早期选择就没有封死通往最优解的道路。真正困难的部分不是找一个听起来合理的评分，而是发现问题中允许这种调整的结构。

动态规划通常保留多个可能影响未来的状态；贪心法只保留一条选择路径。少掉的那些状态必须由证明补回来：要么说明它们都可交换成当前路径，要么说明当前路径在每个前缀都不落后。没有这一步，简洁只是少搜索，并不意味着答案正确。

无权区间调度要求选择最多个两两不重叠的区间。按结束时间从早到晚扫描，每次接受与已选区间兼容的第一个候选。设贪心首选区间为 $g$，任取一个最优解并记其最早结束的区间为 $o$。因为 $g$ 的结束时间不晚于 $o$，用 $g$ 替换 $o$ 不会挤掉最优解中的后续区间，于是至少有一个最优解包含 $g$。删去与 $g$ 冲突的候选后，同一论证可继续应用，这才完成正确性主线。

局部规则稍换就可能失败。硬币面额为 $\{1,3,4\}$ 时，若目标是用最少硬币凑出 $6$，“每次取不超过余额的最大面额”得到 $4+1+1$，而最优解是 $3+3$。这个反例不是说所有硬币系统都不能贪心，而是说明面额集合没有自动提供所需交换结构。

若算法只写“选最小权候选”，却没有说明何时跳过会破坏可行性的候选，它还不是完整算法。若论证只展示若干输入成功，则只是测试；贪心正确性需要覆盖每一步和所有合法实例的结构证明。

设计贪心算法时，可以先用小实例攻击候选规则：让最早、最短、最便宜或收益最高的选择互相竞争，观察某个局部决定是否阻断更好的组合。规则经得住反例后，再寻找交换映射或前缀不变量；这个顺序常比先写伪代码更快暴露错误。

最小生成树公理库最小生成树Minimum spanning tree · MST连通加权图中总边权最小的生成树及其算法问题。的安全边由割性质证明，拟阵贪心公理库拟阵贪心算法Matroid greedy algorithm按权重依次加入仍保持独立的元素以求最大权拟阵基的算法。则刻画一类对所有权重都能由贪心获得最优解的可行集系统。另一些问题只有可量化的近似保证，例如集合覆盖按单位新增覆盖成本选择集合。它们共享不可回溯的选择方式，却必须分别说明保证是精确最优还是近似比公理库近似比Approximation ratio近似算法解值与最优值之间的最坏情形乘法保证。。