贪心（一）——从动态规划到贪心 算法设计与分析 国科大
区间调度问题
- 输入：n 个活动
，每个活动
对应时间区间
（占用资源的时段）和收益
（选择该活动的价值）。
- 输出：选择一组兼容活动（即区间无重叠的活动，同一时间资源仅能被一个活动占用），使得总收益最大。
- 前提条件：所有活动已按结束时间升序排序—— 此排序是后续动态规划高效求解的基础。
下面看一个具体的例子
对于图中，我们要选择一组时间不冲突的集合，使其收益最大化。该问题可以由之前讲过的动态规划求解
直接求解 n 个活动的问题是比较复杂的，因此将解决过程转化为 “决策序列”（每一步决定是否选择某个活动）。假设已得到最优解，第一个决策聚焦于最后一个活动是否被选择：
若选择，则需从在
开始时间
前结束的活动中选择兼容活动 —— 对应一个更小的子问题（仅考虑这些前置活动）。
若放弃，则原问题简化为 “从
中选择兼容活动以最大化收益”—— 对应另一个更小的子问题（仅考虑前 n-1 个活动）。
最优子结构
基于上述子问题拆分，定义最优子结构与递推公式：
- 子问题定义：设
为 “从
中选择兼容活动的最大收益”。
- 最优子结构性质：原问题的最优解可由子问题的最优解组合得到，递推公式为：
其中
表示最后一个在
的开始时间
前结束的活动的索引
下面看实际的例子
- 解的表示：将解定义为数组
X = [x₁, x₂, ..., x₉]，其中xᵢ = 1表示选择活动Aᵢ，xᵢ = 0表示不选择。 - 决策过程：
- 以第 9 个活动
A₉的决策为第一步：决策节点p₀对应 “未确定x₉” 的状态（X中x₉为?）； - 需枚举两种决策选项：
x₉ = 1（选择A₉，对应节点p₁，X中x₉ = 1）、x₉ = 0（不选择A₉，对应节点p₂，X中x₉ = 0）。
- 以第 9 个活动
- 核心意义：由于无法提前判断 “选 / 不选
A₉” 哪个更优，动态规划需枚举关键决策的所有可能，再通过子问题的最优解组合得到全局最优。
可能有同学会有疑问，为什么要以是否选择最后一个事件作为首次决策呢？不能以选择任意活动为首次决策吗？实际上这样，子问题会变成：若选择，则子问题为从移除
及与其时间冲突的所有活动后的集合中，选择兼容活动以最大化收益。不同于之前是/否的二元决策，以该例来说，第一步就有十种选择，导致子问题数量大幅增加。因此，这种决策并不是一个好的选择。其实际执行与最优子结构如下，不再过多赘述
基础区间调度
下面看一个更简化的问题
它和之前的问题基本一致，不同在于它去掉了权重，最优解仅以集合中包含的事件个数决定。例如：
相较于之前的问题，其除了保留最优子结构的性质外，还有贪心选择的性质，是贪心算法最经典的例子。其求解依赖于下面定理：
设是结束时间最早的活动，则
必然包含在某个最优解中。证明如下：
- 假设前提：设最优解
，且O中首个活动
（即假设最优解不包含
）。
- 兼容性分析：由于
是结束时间最早的活动，其结束时间早于
，因此
与O中后续活动
均兼容。
- 交换构造：构造新集合
。
- 最优性验证：
的活动数量与O相同（
），因此
也是最优解，且
包含
。
至此即证明：不包含最早结束活动的最优解可转化为包含
的最优解”，验证了 “最早结束活动必然在最优解中。下面借助该思想，即可完成贪心算法的编写：
代码维护变量previous_finish_time用于记录当前选中活动的结束时间，初始化为-∞，然后不断选择活动结束时间最早，且兼容的活动，每进行一次选择，就更新变量previous_finish_time，直至所有活动都被遍历。
具体执行过程
步骤如下，应该是很容易看明白的：
- Step 1：在所有活动中选择结束时间最早的活动（活动 1），随后排除与活动 1 时间冲突的所有活动（图中蓝色框内的活动）。
- Step 2：在剩余活动中，继续选择结束时间最早的活动（活动 3），排除与活动 3 冲突的活动。
- Step 3：重复上述逻辑，选择剩余活动中结束时间最早的活动（活动 5），排除冲突活动。
- Step 4：选择最后剩余的活动（活动 8），完成选择。
对比动态规划与贪心
二者均是解决优化问题的经典算法，核心共性包括：
- 适用场景：都针对优化问题（目标是最大化 / 最小化某一指标）。
- 核心性质：都依赖最优子结构性质（原问题的最优解可由子问题的最优解组合得到）。
- 算法关联：贪心算法的背后，几乎总能找到一个更繁琐的动态规划解法。
但是二者的决策逻辑存在本质区别：
- 决策方式：
- 动态规划：在每个决策步骤中，需枚举所有可能的选项，且决策需等子问题求解完成后才能确定。
- 贪心算法：无需枚举所有选项，直接做出局部最优的贪心决策，且决策无需依赖子问题的求解结果。
- 贪心需求的性质更加严格，对于同一个问题，如果可以用贪心和动态规划解决，贪心的效率往往比动态规划高得多。
- 补充说明：
- 贪心的 “局部” 是指：基于已构造的部分最优解的信息，即可做出当前决策。
- 部分贪心算法缺乏严格的理论证明，需通过大量实验结果验证其效率。
下篇文章将详细介绍如何设计一个贪心算法。