Skip to Content

第一部分：经典活动安排问题 (Unweighted Activity Selection)

这是最基础的版本，也被称为“区间调度问题”。

1. 问题描述

  • 输入：一个包含 n 个活动的集合 S = {a₁, a₂, ..., aₙ}。每个活动 aᵢ 都有一个开始时间 sᵢ 和一个结束时间 fᵢ，其中 0 ≤ sᵢ < fᵢ。
  • 约束：一个资源（例如一个会议室、一个处理器）在同一时间只能执行一个活动。如果两个活动 aᵢ 和 aⱼ 的时间区间 [sᵢ, fᵢ) 和 [sⱼ, fⲓ) 不重叠，则称它们是兼容的。
  • 目标：从集合 S 中选出一个由相互兼容的活动组成的子集 A，使得子集 A 中的活动数量最大。

2. 核心思想：贪心算法 (Greedy Algorithm)

解决这个问题的直觉是“每次都做出在当前看来是最好的选择”。但“最好”的标准是什么呢？

  • 错误想法1：选择持续时间最短的活动？

    • 反例：一个持续时间很短的活动可能正好位于两个较长但不重叠的活动的中间，选择它会使我们失去选择另外两个的机会。
    • 例如：A(4,7), B(1,5), C(6,10)。最短的是 A，但选择 A 后就不能选 B 和 C。最优解是选择 B 和 C。

  • 错误想法2：选择开始时间最早的活动？

    • 反例：一个开始很早的活动可能持续时间非常长，从而阻塞了之后大量的活动。
    • 例如：A(1,10), B(2,3), C(4,5), D(6,7)。最早开始的是 A，选择它就结束了。但最优解是选择 B, C, D。

  • 正确策略：选择结束时间最早的活动

    • 直觉：选择一个能最快结束的活动，可以为后续的活动留下尽可能多的可用时间。
    • 这个策略是正确的，也是这个问题的贪心算法核心。

3. 算法步骤

  1. 排序：将所有 n 个活动按其结束时间 fᵢ 从小到大进行排序。
  2. 选择： a. 选择排序后的第一个活动 a₁ (它具有最早的结束时间)，并将其加入到解集 A 中。 b. 记录下 a₁ 的结束时间 last_finish_time = f₁。
  3. 迭代： a. 从第二个活动 a₂ 开始，依次遍历所有排好序的活动 aᵢ。 b. 对于每个活动 aᵢ，如果它的开始时间 sᵢ 大于或等于 last_finish_time（即与上一个选中的活动不冲突），则： i. 将 aᵢ 加入到解集 A 中。 ii. 更新 last_finish_time = fᵢ。
  4. 返回：返回解集 A。

4. 示例

假设有以下活动 (start, finish)： a1(1,4), a2(3,5), a3(0,6), a4(5,7), a5(3,9), a6(5,9), a7(6,10), a8(8,11), a9(8,12), a10(2,14), a11(12,16)

  1. 按结束时间排序： a1(1,4), a2(3,5), a3(0,6), a4(5,7), a5(3,9), a6(5,9), a7(6,10), a8(8,11), a9(8,12), a10(2,14), a11(12,16)

  2. 选择与迭代：

    • 选 a1(1,4)。解集 A = {a1}。last_finish_time = 4。
    • a2(3,5): s₂=3 < 4，冲突，跳过。
    • a3(0,6): s₃=0 < 4，冲突，跳过。
    • 选 a4(5,7): s₄=5 >= 4，不冲突。解集 A = {a1, a4}。last_finish_time = 7。
    • a5(3,9): s₅=3 < 7，冲突，跳过。
    • a6(5,9): s₆=5 < 7，冲突，跳过。
    • a7(6,10): s₇=6 < 7，冲突，跳过。
    • 选 a8(8,11): s₈=8 >= 7，不冲突。解集 A = {a1, a4, a8}。last_finish_time = 11。
    • a9(8,12): s₉=8 < 11，冲突，跳过。
    • a10(2,14): s₁₀=2 < 11，冲突，跳过。
    • 选 a11(12,16): s₁₁=12 >= 11，不冲突。解集 A = {a1, a4, a8, a11}。last_finish_time = 16。

  3. 最终结果：最优解集为 {a1, a4, a8, a11}，共 4 个活动。

5. 算法正确性证明

贪心算法的证明通常分为两步：

  1. 贪心选择性质 (Greedy Choice Property)：证明总存在一个最优解，它包含了我们做出的第一个贪心选择。
    • 假设 a₁ 是结束时间最早的活动。我们做的贪心选择就是它。
    • 假设存在一个最优解 O，它不包含 a₁。设 O 中第一个（按结束时间排序）活动是 aⱼ。
    • 因为 a₁ 是所有活动中结束时间最早的，所以 f₁ ≤ fⱼ。
    • 我们可以用 a₁ 替换 O 中的 aⱼ 得到一个新的解 O'。由于 f₁ ≤ fⱼ，a₁ 不会与 O 中 aⱼ 之后的任何活动冲突。
    • O' 的活动数量与 O 相同，所以 O' 也是一个最优解，并且它包含了我们的贪心选择 a₁。
  2. 最优子结构 (Optimal Substructure)：当做出一个贪心选择后，原问题就简化为了一个规模更小的、形式相同的子问题。
    • 我们选择了 a₁ 后，问题就变成了：在所有与 a₁ 不冲突（即开始时间晚于 f₁）的活动中，寻找一个最优解。
    • 这个子问题的解与 a₁ 组合起来，就构成了原问题的最优解。

6. 复杂度分析

  • 时间复杂度：O(N log N)，瓶颈在于对活动按结束时间排序。遍历过程是线性的 O(N)。
  • 空间复杂度：O(1) 或 O(N)，取决于是否需要额外空间存储排序后的结果和解集。

第二部分：带权活动安排问题 (Weighted Activity Selection)

这是经典问题的扩展，难度大大增加。

1. 问题描述

  • 输入：与经典问题相同，但每个活动 aᵢ 还额外关联一个权重（或价值）wᵢ。
  • 目标：从集合 S 中选出一个由相互兼容的活动组成的子集 A，使得子集 A 中所有活动权重之和最大。

2. 为什么贪心算法失效？

我们之前“选择结束时间最早”的贪心策略在这里不再适用。

  • 反例：
    • A(1, 10, w=100)
    • B(2, 4, w=10)
    • C(5, 7, w=10)
  • 按结束时间排序后是 B, C, A。
  • 贪心算法会先选择 B (权重10)，然后选择 C (权重10)，总权重为 20。
  • 但最优解是只选择 A，总权重为 100。

结论：这个问题的决策具有“后效性”，即当前的选择会影响未来的选择，且无法仅通过局部最优信息（如结束时间、权重大小）来保证全局最优。这正是动态规划（Dynamic Programming）的用武之地。

3. 核心思想：动态规划 (Dynamic Programming)

  1. 排序：同样，我们首先将所有活动按结束时间 fᵢ 从小到大排序。这是DP能够顺利进行的关键步骤。

  2. 定义子问题：

    • 设 dp[i] 表示只考虑前 i 个活动（按结束时间排序后）所能获得的最大权重。
    • 我们的最终目标是 dp[n]。

  3. 建立递推关系 (Recurrence Relation)： 对于第 i 个活动 aᵢ，我们有两种选择：

    • 不选择 aᵢ：如果我们不选择 aᵢ，那么只考虑前 i 个活动的最大权重就等于只考虑前 i-1 个活动的最大权重。即 dp[i-1]。
    • 选择 aᵢ：如果我们选择 aᵢ，我们就能获得其权重 wᵢ。但我们还必须加上与 aᵢ 兼容的其他活动的最大权重。哪些活动是兼容的呢？所有在 aᵢ 开始之前就已经结束的活动。
      • 我们需要找到在 aᵢ 之前（索引小于 i）的最后一个与 aᵢ 兼容的活动 aⱼ。也就是说，j 是满足 fⱼ ≤ sᵢ 的最大索引。我们称这个 j 为 p(i)。
      • 如果选择了 aᵢ，那么总权重就是 wᵢ + dp[p(i)]。（如果不存在这样的 j，则 p(i)=0，我们设 dp[0]=0）。

    综合这两种选择，dp[i] 的值就是二者中的较大者： dp[i] = max( dp[i-1], wᵢ + dp[p(i)] )

4. 算法步骤

  1. 排序：将 n 个活动按结束时间 fᵢ 升序排序。
  2. 预计算 p(i)：为每个活动 aᵢ (从 i=1 到 n) 计算 p(i)。p(i) 是索引 j < i 中满足 fⱼ ≤ sᵢ 的最大 j。
    • 这一步可以通过对每个 i 向前线性扫描来完成（总复杂度 O(N²))，或者使用二分查找（总复杂度 O(N log N)）来优化。
  3. DP 计算： a. 初始化 dp 数组，dp[0] = 0。 b. 从 i=1 到 n，根据递推公式计算 dp[i] = max(dp[i-1], wᵢ + dp[p(i)])。
  4. 返回：dp[n] 就是最终答案。

5. 示例

使用上面的反例： B(2, 4, w=10), C(5, 7, w=10), A(1, 10, w=100)

  1. 排序（按结束时间）：

    1. a₁ = B(2, 4, w=10)
    2. a₂ = C(5, 7, w=10)
    3. a₃ = A(1, 10, w=100)

  2. 计算 p(i)：

    • p(1) (for B): 不存在，p(1)=0。
    • p(2) (for C): C开始于5。B结束于4。f₁ ≤ s₂。所以 p(2)=1。
    • p(3) (for A): A开始于1。之前没有活动结束于1之前。所以 p(3)=0。

  3. DP 计算：

    • dp[0] = 0
    • dp[1] (for B): max(dp[0], w₁ + dp[p(1)]) = max(0, 10 + dp[0]) = 10。
    • dp[2] (for C): max(dp[1], w₂ + dp[p(2)]) = max(10, 10 + dp[1]) = max(10, 10 + 10) = 20。
    • dp[3] (for A): max(dp[2], w₃ + dp[p(3)]) = max(20, 100 + dp[0]) = max(20, 100 + 0) = 100。

  4. 最终结果：dp[3] = 100，这与最优解相符。

6. 复杂度分析

  • 时间复杂度：
    • 排序：O(N log N)。
    • 计算所有 p(i)：使用二分查找为 O(N log N)，线性扫描为 O(N²)。
    • DP计算：O(N)。
    • 总复杂度为 O(N log N)。
  • 空间复杂度：O(N)，用于存储 dp 数组和 p 数组。

总结与对比

特性经典活动安排问题带权活动安排问题
目标最大化活动数量最大化活动权重之和
核心思想贪心算法 (Greedy)动态规划 (Dynamic Programming)
关键决策总是选择结束时间最早的兼容活动在“选或不选当前活动”之间做出最优决策
算法性质具有贪心选择性质和最优子结构只有最优子结构，不满足贪心选择性质
时间复杂度O(N log N) (瓶颈在排序)O(N log N) (瓶颈在排序和预计算)
空间复杂度O(1) 或 O(N)O(N)

这两个问题完美地展示了贪心和动态规划的联系与区别。当局部最优选择能够确保全局最优时（如经典活动安排），可以使用更简单、高效的贪心算法。当局部最优无法保证全局最优，需要考虑所有可能性并从中选择时，就需要动用更强大的动态规划。

Last updated on
Map