贪心算法

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

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

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

采用半开区间 $[s,f)$、要求 $s<f$，相邻端点允许衔接。对候选 $[0,3),[1,2),[2,4),[4,5)$，结束时间排序后先选 $[1,2)$，跳过仍与它冲突的 $[0,3)$，再选 $[2,4),[4,5)$，共三个。维护的状态只需“上次接受的结束时刻”，下一项满足 $s\ge f_{\mathrm{last}}$ 才接受。选最早开始的 $[0,3)$ 则最多得到两个，说明候选规则的具体含义决定成败。

若要求安排全部区间、把资源数降到最少，目标便变成区间分配。完美图理路完美图Perfect graph每个顶点诱导子图的色数都等于最大团大小；区间图可用资源分配与同时重叠证书证明这一性质。中的区间实例按开始时刻处理，用最小堆复用最早释放的资源；每次必须新增资源时，同时重叠的区间就给出匹配的下界。这与此处按结束时刻选择最大兼容子集是两种不同的贪心证明。

若区间带收益，目标改成总收益最大，原交换便不能保证目标不降：收益 $100$ 的 $[0,3)$ 可能被收益仅 $1$ 的 $[1,2)$ 替换掉。结束更早只保证留出空间，不保证补偿损失的收益，因此带权版本需要新的论证或动态规划。

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

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

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

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