贪心算法

贪心算法在每一步做出当前看来最优的选择，选定后不再撤回。这种策略之所以有效，并非因为“局部最优等于全局最优”（这通常是错的），而是因为特定问题的结构保证了：存在一个全局最优解，它恰好包含了这个局部选择。

设计流程

1. 定义问题：明确什么是可行解，目标函数是什么（最大化还是最小化）。
2. 制定规则：确定局部选择准则（Greedy Choice），并明确选择后剩余子问题的形态。
3. 证明安全性：证明该局部选择是“安全”的，即它必然属于某个最优解。
4. 验证子问题结构：证明剩余子问题与原问题具有相同的结构（递归性质）。
5. 分析复杂度：根据选择策略和数据结构更新操作推导时间复杂度。

常见证明模式

• 交换论证 (Exchange Argument)：假设存在一个最优解 $O$ 与贪心解 $G$ 不同。通过逐步将 $O$ 中的元素替换为 $G$ 中的元素，证明替换过程不会使解变差，最终 $O$ 变为 $G$。
• 保持领先 (Stays Ahead)：定义一个度量指标，证明在算法执行的每一步（前缀），贪心算法的当前状态在该指标上都不劣于任何其他竞争算法。
• 割性质 (Cut Property)：常用于图论。如果一条边是横跨某个割（Cut）的权重最小的边，那么这条边一定属于某个最小生成树（MST）。
• 数学归纳法：证明第一步选择安全后，假设前 $k$ 步选择安全，进而证明第 $k+1$ 步选择也安全，从而覆盖整个序列。

代表性问题

问题	安全选择策略	依赖的结构性质
活动选择	选择结束时间最早的活动	区间兼容性，目标是最大化活动数量
分数背包	选择单位价值密度最高的物品	物品可分割，价值与重量呈线性关系
Huffman 编码	合并频率最低的两个节点	构建二叉前缀码，目标是最小化加权路径长度
最小生成树 (MST)	选择横跨割的最小权重边	加权无向图，连通性
Dijkstra 算法	确定当前临时距离最小的顶点	边权非负，单源最短路径

注意：贪心策略在任意实例上并不总是有效。例如，贪心找零（每次选最大面额）、追求即时利润最大化或即时成本最小化，在缺乏特定结构约束时往往会失败。一个看似合理的贪心规则，在没有证明或已知结构定理支持之前，仅仅是一个猜想。

贪心与动态规划

• 动态规划 (DP)：保存可复用子问题的结果，并比较不同选择，适用于子问题重叠且贪心选择无法保证全局最优的情况。
• 贪心算法：利用“安全选择定理”直接坍缩选择空间，无需回溯。

当问题的交换性质（Exchange Property）不成立时，意味着贪心选择可能排除掉全局最优解，此时可能需要保留更多状态，用动态规划或其他适合问题的算法比较备选方案。

失败的规则留下了什么状态

面额 1、3、4 可无限使用时，大面额优先把 6 凑成 4+1+1，但 3+3 更省硬币。局部规则没有有效交换论证，却丢掉了后者：把两枚 3 换成一枚 4，余数还要两枚硬币。

动态规划保留 dp[t]，表示恰好凑出 t 的最少硬币数，并考虑每种最后一枚硬币：在不超过 t 的面额 c 中取 dp[t] = min(1+dp[t-c])。初始化 dp[0]=0，不可达金额为无穷大。金额 0..6 的表为 [0,1,2,1,1,2,2]。在此正整数、无限使用模型下，目标 T、面额数 k 对应 O(Tk) 时间和 O(T) 空间。贪心失败并不意味着所有问题都必须用 DP；穷举或其他结构性算法也可能更合适。

来源

• MIT OpenCourseWare: Greedy Algorithms

我的阅读 · 打开过的笔记会记在当前浏览器里。