习题 15.1-1：活动选择的动态规划算法

题目

基于递推式 (15.2)，给出活动选择问题的动态规划算法，同时计算 $c[i,j]$ 的值并输出最大兼容活动子集。

递推式回顾

设 $S_{ij}$ 为在活动 $a_i$ 结束后开始、在活动 $a_j$ 开始前结束的所有活动的集合。$c[i,j]$ 表示 $S_{ij}$ 中最大兼容子集的大小。
递推式为：
c[i,j]={0若 Sij=∅max⁡ak∈Sij{c[i,k]+c[k,j]+1}若 Sij≠∅c[i,j] = \begin{cases} 0 & \text{若 } S_{ij} = \emptyset \\ \max_{a_k \in S_{ij}} \{ c[i,k] + c[k,j] + 1 \} & \text{若 } S_{ij} \ne \emptyset \end{cases}c[i,j]={0maxak​∈Sij​​{c[i,k]+c[k,j]+1}​若 Sij​=∅若 Sij​=∅​
用人话说：枚举 $S_{ij}$ 中每一个可能的"中间活动" $a_k$，把问题拆成两个子问题，取最大值。

理解思路

想象活动选择就像在时间轴上"插旗子"：

时间轴:  0----1----2----3----4----5----6----7
活动 a1:      [=====]
活动 a2:           [=====]
活动 a3:                     [=====]

$c[i,j]$ 的含义：在 $a_i$ 结束后、$a_j$ 开始前，最多能插多少面旗？
动态规划的做法：从小区间开始算，逐步扩展到大区间。

算法流程

1. 在活动序列首尾各加虚拟活动 a0（结束时间=0）和 a_{n+1}（开始时间=正无穷）
2. 初始化所有 c[i,j] = 0
3. 按区间长度从小到大枚举所有 (i,j)
4. 对每个 (i,j)，枚举所有满足 f_i <= s_k < f_k <= s_j 的活动 a_k
5. 用递推式更新 c[i,j] 并记录选择 act[i,j]=k
6. 最终答案是 c[0, n+1]，通过 act 数组回溯输出具体活动

C++ 完整实现

#include <vector>
#include <algorithm>
#include <iostream>
#include <climits>
using namespace std;
struct Activity {
    int s; // 开始时间
    int f; // 结束时间
    int id;
};
// 输出最优解：通过 act 回溯表还原选中的活动
void printSolution(const vector<vector<int>>& act,
                   const vector<Activity>& acts,
                   int i, int j) {
    if (act[i][j] == -1) return; // 此区间为空，无活动可选
    int k = act[i][j];
    printSolution(act, acts, i, k);           // 递归输出左半部分
    cout << "a" << acts[k].id << " ";        // 输出当前选中的活动
    printSolution(act, acts, k, j);           // 递归输出右半部分
}
void dpActivitySelector(vector<Activity>& acts) {
    int n = acts.size();
    // 按结束时间排序（题目假设已排好，这里保险起见再排一次）
    sort(acts.begin(), acts.end(),
         [](const Activity& a, const Activity& b) {
             return a.f < b.f;
         });
    // 加入虚拟活动：a0（结束时间=0）和 a_{n+1}（开始时间=正无穷）
    // 在数组头部插入 a0，尾部插入 a_{n+1}
    vector<Activity> a;
    a.push_back({0, 0, 0});          // a0：虚拟开始哨兵
    for (auto& act : acts) a.push_back(act);
    a.push_back({INT_MAX, INT_MAX, n + 1}); // a_{n+1}：虚拟结束哨兵
    int N = a.size(); // 总节点数 = n + 2
    // c[i][j]：区间 S_ij 的最大兼容活动数
    // act[i][j]：S_ij 最优解中选择的"中间活动"下标
    vector<vector<int>> c(N, vector<int>(N, 0));
    vector<vector<int>> actTable(N, vector<int>(N, -1));
    // 按区间长度 l 从小到大填表
    // l=2 表示 j=i+2，即区间 (i, i+2) 中只可能有 a_{i+1} 这一个候选
    for (int l = 2; l < N; l++) {         // l = j - i，即区间跨度
        for (int i = 0; i + l < N; i++) { // 枚举左端点 i
            int j = i + l;                 // 右端点 j
            // 枚举 S_ij 中所有可能的"中间活动" k
            // 条件：a_k 在 a_i 结束后开始，在 a_j 开始前结束
            for (int k = i + 1; k < j; k++) {
                // a[k] 是否属于 S_ij？
                // 需要：a[k].s >= a[i].f 且 a[k].f <= a[j].s
                if (a[k].s >= a[i].f && a[k].f <= a[j].s) {
                    int val = c[i][k] + c[k][j] + 1;
                    if (val > c[i][j]) {
                        c[i][j] = val;
                        actTable[i][j] = k;
                    }
                }
            }
        }
    }
    cout << "最大兼容活动数：" << c[0][N - 1] << endl;
    cout << "选中的活动：";
    printSolution(actTable, a, 0, N - 1);
    cout << endl;
}
int main() {
    // 教材图 15.1 的 11 个活动
    vector<Activity> acts = {
        {1,  4,  1}, {3,  5,  2}, {0,  6,  3},
        {5,  7,  4}, {3,  9,  5}, {5, 11,  6},
        {6, 10,  7}, {8, 12,  8}, {8, 14,  9},
        {2, 14, 10}, {12, 16, 11}
    };
    dpActivitySelector(acts);
    // 输出：最大兼容活动数：4
    //       选中的活动：a1 a4 a8 a11
    return 0;
}

与贪心算法的运行时间对比

---

算法	时间复杂度	原因
动态规划（上面的算法）	$O(n^3)$	三层嵌套循环：枚举 $(i,j)$ 是 $O(n^2)$，枚举中间活动 $k$ 是 $O(n)$
贪心算法（GREEDY-ACTIVITY-SELECTOR）	$O(n\log n)$	排序 $O(n\log n)$，单次扫描 $O(n)$

---

贪心算法远快于动态规划。这是因为贪心算法每步只考虑一个选择（最早结束的活动），不需要枚举所有可能的中间活动。

活动选择问题：动态规划完全理解

一、问题是什么

有一组活动，每个活动占用一段时间。我们想从中挑出尽量多的活动，但要求所有被选中的活动时间不能冲突。
两个活动时间不冲突，就叫它们兼容。判断方法很简单：如果一个活动在另一个结束之后才开始，就是兼容的。
例子：

• 活动 $a_1$：$[1,4)$，即从时间 1 开始，时间 4 结束
• 活动 $a_4$：$[5,7)$，即从时间 5 开始，时间 7 结束
• $a_1$ 在时间 4 结束，$a_4$ 在时间 5 才开始，不冲突，兼容

二、输入数据

教材给了 11 个活动，首先按结束时间从小到大排序：

数组下标	活动编号	开始时间 $s$	结束时间 $f$
1	$a_1$	1	4
2	$a_2$	3	5
3	$a_3$	0	6
4	$a_4$	5	7
5	$a_5$	3	9
6	$a_6$	5	11
7	$a_7$	6	10
8	$a_8$	8	12
9	$a_9$	8	14
10	$a_{10}$	2	14
11	$a_{11}$	12	16

---

排序后结束时间依次为 4, 5, 6, 7, 9, 10, 11, 12, 14, 14, 16，已经从小到大。

三、加入两个假活动（哨兵）

在头部加 $a_0$，在尾部加 $a_{12}$：

下标	活动	开始时间 $s$	结束时间 $f$	说明
0	$a_0$	0	0	左哨兵，代表"还没开始"
1~11	$a_1\sim a_{11}$	同上	同上	真实活动
12	$a_{12}$	$+\infty$	$+\infty$	右哨兵，代表"永远不会到"

---

为什么要加哨兵？
加了哨兵之后，整个问题可以统一描述为：在 $a_0$ 结束之后、$a_{12}$ 开始之前，从中选最多的兼容活动。代码不需要单独处理"第一个活动"和"最后一个活动"这样的边界情况，逻辑更整齐。
加入哨兵后数组共 13 个元素，下标 0 到 12，代码中用 N = 13 表示。

四、定义子问题

把原问题拆成小问题来解决。
定义：$S_{ij}$ 表示所有满足"在 $a_i$ 结束之后开始，并且在 $a_j$ 开始之前结束"的活动的集合。
用不等式写就是：
Sij={ak∣sk≥fi 并且 fk≤sj}S_{ij} = \{ a_k \mid s_k \ge f_i \text{ 并且 } f_k \le s_j \}Sij​={ak​∣sk​≥fi​ 并且 fk​≤sj​}
举三个例子帮助理解：
例 1：$S_{0,12}$
$a_0$ 结束时间 = 0，$a_{12}$ 开始时间 = $+\infty$。
条件变成：$s_k\ge 0$ 且 $f_k\le +\infty$，即所有真实活动都满足。
所以 S0,12={a1,a2,…,a11}S_{0,12} = \{a_1, a_2, \ldots, a_{11}\}S0,12​={a1​,a2​,…,a11​}，这就是整个问题。
例 2：$S_{0,4}$
$a_0$ 结束时间 = 0，$a_4$ 开始时间 = 5。
条件：$s_k\ge 0$ 且 $f_k\le 5$。
逐一检查：$a_1$（$f=4\le 5$，满足）、$a_2$（$f=5\le 5$，满足）、$a_3$（$f=6>5$，不满足）。
所以 S0,4={a1,a2}S_{0,4} = \{a_1, a_2\}S0,4​={a1​,a2​}。
例 3：$S_{1,4}$
$a_1$ 结束时间 = 4，$a_4$ 开始时间 = 5。
条件：$s_k\ge 4$ 且 $f_k\le 5$。
逐一检查：$a_2$（$s=3<4$，不满足）、$a_3$（$s=0<4$，不满足）。没有活动满足。
所以 $S_{1,4}=\varnothing$（空集）。
DP 状态定义：
$$c[i][j]=S_{ij}\text{ 中能选出的最多兼容活动数}$$
最终要求的答案就是 $c[0][12]$，即整个问题的最优解。

五、递推公式推导

对于区间 $S_{ij}$，假设我们决定把其中某个活动 $a_k$ 纳入最优解。
$a_k$ 被选中之后，它把时间轴分成了两段：

• $a_k$ 开始之前：只能从 $S_{ik}$ 里再选活动
• $a_k$ 结束之后：只能从 $S_{kj}$ 里再选活动
• 这两段互不干扰，可以独立求最优
  所以选了 $a_k$ 的总收益 = 左边最优 + 右边最优 + $a_k$ 本身 1 个：
  $$c[i][k]+c[k][j]+1$$
  我们不知道选哪个 $a_k$ 最好，就把所有合法的 $k$ 都试一遍，取最大值：
  c[i][j]=max⁡i<k<jak∈Sij{c[i][k]+c[k][j]+1}c[i][j] = \max_{\substack{i < k < j \\ a_k \in S_{ij}}} \left\{ c[i][k] + c[k][j] + 1 \right\}c[i][j]=i<k<jak​∈Sij​​max​{c[i][k]+c[k][j]+1}
  边界：若 $S_{ij}=\varnothing$，没有活动可选，$c[i][j]=0$。

六、填表顺序

填 $c[i][j]$ 时需要用到 $c[i][k]$ 和 $c[k][j]$，其中 $i<k<j$，说明这两个子区间比当前区间更短。
因此要先填短区间，再填长区间，即按跨度 $l=j-i$ 从 2 开始逐步增大。

l = 2: 填所有跨度为 2 的区间，如 (0,2), (1,3), ..., (10,12)
l = 3: 填所有跨度为 3 的区间，如 (0,3), (1,4), ..., (9,12)
...
l = 12: 填 (0,12)，这就是最终答案

当 $l=1$ 时，区间 $(i,i+1)$ 内没有可选活动（$k$ 只能取 $i+1$ 到 $j-1=i$，无效），初始化为 0 即可。

七、关键格子手算示例

下面用具体数字走几个格子，让填表过程完全清晰。

$c[0][4]$（跨度 $l=4$，$a_4$ 开始时间 $s_4=5$）

枚举 $k=1,2,3$：

• $k=1$（$a_1$，$s=1,f=4$）：$1\ge 0$ 且 $4\le 5$，满足。$val=c[0][1]+c[1][4]+1=0+0+1=1$
• $k=2$（$a_2$，$s=3,f=5$）：$3\ge 0$ 且 $5\le 5$，满足。$val=c[0][2]+c[2][4]+1=0+0+1=1$
• $k=3$（$a_3$，$s=0,f=6$）：$6\le 5$？不满足，跳过。
  最大值为 1，$c[0][4]=1$，记录 $\text{actTable}[0][4]=1$（选 $a_1$）。

$c[4][9]$（$a_4$ 结束时间 $f_4=7$，$a_9$ 开始时间 $s_9=8$）

枚举 $k=5,6,7,8$：

• $k=5$（$a_5$，$s=3,f=9$）：$3\ge 7$？不满足。
• $k=6$（$a_6$，$s=5,f=11$）：$5\ge 7$？不满足。
• $k=7$（$a_7$，$s=6,f=10$）：$6\ge 7$？不满足。
• $k=8$（$a_8$，$s=8,f=12$）：$8\ge 7$ 且 $12\le 8$？$12>8$，不满足。
  没有活动满足，$c[4][9]=0$，$\text{actTable}[4][9]=-1$。

$c[0][9]$（$a_0$ 结束 0，$a_9$ 开始 $s_9=8$）

枚举 $k=1$ 到 $8$，只列满足条件的：

• $k=1$（$a_1$，$s=1\ge 0$，$f=4\le 8$，满足）：$val=c[0][1]+c[1][9]+1$。需要知道 $c[1][9]$：$a_1$ 结束时间 4，$a_9$ 开始时间 8，$S_{1,9}$ 中满足的活动有 $a_4$（$s=5\ge 4$，$f=7\le 8$），$c[1][9]=1$。所以 $val=0+1+1=2$。
• $k=4$（$a_4$，$s=5\ge 0$，$f=7\le 8$，满足）：$val=c[0][4]+c[4][9]+1=1+0+1=2$。
• $k=8$（$a_8$，$s=8\ge 0$，$f=12\le 8$？不满足）。
  最大值为 2，$c[0][9]=2$。

$c[0][12]$（最终目标，$a_{12}$ 开始时间 $+\infty$）

枚举所有 $k=1$ 到 $11$，所有真实活动的 $f_k\le +\infty$ 都满足，因此只需检查 $s_k\ge 0$（都满足）。
关键的几个 $k$ 值（其余类似）：

• $k=8$（$a_8$，$f=12$）：$val=c[0][8]+c[8][12]+1$。$c[0][8]$ 表示在 $a_8$ 之前能选多少，经计算为 2（选 $a_1,a_4$）；$c[8][12]$ 表示 $a_8$ 之后能选多少（$a_9,a_{10},a_{11}$ 中，只有 $a_{11}$ 的 $s=12\ge 12$），为 1。所以 $val=2+1+1=4$。
  最终 $c[0][12]=4$，$\text{actTable}[0][12]=8$。

八、从表里读出答案（回溯）

$\text{actTable}[i][j]$ 记录了"区间 $(i,j)$ 中，我们选了哪个活动"。知道了这个活动 $k$ 之后，左半边的选择在 $\text{actTable}[i][k]$ 里，右半边在 $\text{actTable}[k][j]$ 里，递归读取即可。

回溯步骤（完整展开）

printSolution(0, 12)
  actTable[0][12] = 8，这一层选了 a8
  |
  +-- 先处理左半边 printSolution(0, 8)
  |     actTable[0][8] = 4，这一层选了 a4
  |     |
  |     +-- 先处理左半边 printSolution(0, 4)
  |     |     actTable[0][4] = 1，这一层选了 a1
  |     |     |
  |     |     +-- 先处理左半边 printSolution(0, 1)
  |     |     |     actTable[0][1] = -1，区间为空，返回
  |     |     |
  |     |     +-- 输出 a1
  |     |     |
  |     |     +-- 再处理右半边 printSolution(1, 4)
  |     |           actTable[1][4] = -1，区间为空，返回
  |     |
  |     +-- 输出 a4
  |     |
  |     +-- 再处理右半边 printSolution(4, 8)
  |           actTable[4][8] = -1，区间为空，返回
  |
  +-- 输出 a8
  |
  +-- 再处理右半边 printSolution(8, 12)
        actTable[8][12] = 11，这一层选了 a11
        |
        +-- 先处理左半边 printSolution(8, 11)
        |     actTable[8][11] = -1，区间为空，返回
        |
        +-- 输出 a11
        |
        +-- 再处理右半边 printSolution(11, 12)
              actTable[11][12] = -1，区间为空，返回

按输出顺序收集：a1 a4 a8 a11
最大兼容活动数 = 4。

九、答案验证

把选出的 4 个活动画在时间轴上：

时间: 0  1  2  3  4  5  6  7  8  9  10 11 12 13 14 15 16
a1:      [====)
a4:                  [==)
a8:                          [====)
a11:                                     [====)

$a_1$ 在时间 4 结束，$a_4$ 在时间 5 开始，不冲突。
$a_4$ 在时间 7 结束，$a_8$ 在时间 8 开始，不冲突。
$a_8$ 在时间 12 结束，$a_{11}$ 在时间 12 开始，不冲突。
4 个活动互相兼容，答案正确。

十、C++ 完整实现与逐行注释

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
struct Activity {
    int s;   // 开始时间
    int f;   // 结束时间
    int id;  // 活动编号，用于输出
};
// 回溯还原选中的活动
// actTable[i][j] == -1：区间 (i,j) 内没有可选活动，直接返回
// actTable[i][j] == k ：区间 (i,j) 中选了 a[k]，递归处理左半边和右半边
void printSolution(const vector<vector<int>>& actTable,
                   const vector<Activity>& a,
                   int i, int j) {
    if (actTable[i][j] == -1) return;
    int k = actTable[i][j];
    printSolution(actTable, a, i, k);     // 先输出左半边（更早的活动）
    cout << "a" << a[k].id << " ";       // 输出这一层选中的活动
    printSolution(actTable, a, k, j);    // 再输出右半边（更晚的活动）
}
void dpActivitySelector(vector<Activity>& acts) {
    int n = (int)acts.size();
    // 按结束时间升序排序
    // 排序目的：保证 i < j 时 a[i] 的结束时间不晚于 a[j]，
    // 这样 S_ij 的定义才有意义
    sort(acts.begin(), acts.end(),
         [](const Activity& x, const Activity& y) {
             return x.f < y.f;
         });
    // 构造含哨兵的活动序列
    vector<Activity> a;
    a.push_back({0, 0, 0});                        // 下标 0：左哨兵
    for (auto& act : acts) a.push_back(act);       // 下标 1~11：真实活动
    a.push_back({INT_MAX, INT_MAX, n + 1});         // 下标 12：右哨兵
    int N = (int)a.size();  // N = 13
    // c[i][j]：S_ij 能选的最多兼容活动数，初始全为 0
    // actTable[i][j]：S_ij 中选的中间活动下标，初始全为 -1（表示空）
    vector<vector<int>> c(N, vector<int>(N, 0));
    vector<vector<int>> actTable(N, vector<int>(N, -1));
    // 外层循环：按区间跨度 l = j - i 从小到大填表
    // l=2 是最短的有意义区间（l=1 时内部无候选活动）
    for (int l = 2; l < N; ++l) {
        // 中层循环：枚举所有左端点 i
        for (int i = 0; i + l < N; ++i) {
            int j = i + l;  // 右端点由左端点和跨度决定
            // 内层循环：枚举所有候选中间活动 k
            for (int k = i + 1; k < j; ++k) {
                // 判断 a[k] 是否属于 S_ij
                // 条件 1：a[k] 在 a[i] 结束之后才开始，即 s_k >= f_i
                // 条件 2：a[k] 在 a[j] 开始之前就结束，即 f_k <= s_j
                if (a[k].s >= a[i].f && a[k].f <= a[j].s) {
                    // 选 a[k] 作为这一层的活动，总数 = 左边 + 右边 + 1
                    int val = c[i][k] + c[k][j] + 1;
                    // 如果比当前记录更优，则更新
                    if (val > c[i][j]) {
                        c[i][j]        = val;
                        actTable[i][j] = k;
                    }
                }
            }
        }
    }
    cout << "最大兼容活动数：" << c[0][N - 1] << endl;
    cout << "选中的活动：";
    printSolution(actTable, a, 0, N - 1);
    cout << endl;
}
int main() {
    vector<Activity> acts = {
        {1,  4,  1}, {3,  5,  2}, {0,  6,  3},
        {5,  7,  4}, {3,  9,  5}, {5, 11,  6},
        {6, 10,  7}, {8, 12,  8}, {8, 14,  9},
        {2, 14, 10}, {12, 16, 11}
    };
    dpActivitySelector(acts);
    // 输出：
    //   最大兼容活动数：4
    //   选中的活动：a1 a4 a8 a11
    return 0;
}

十一、代码整体流程

输入：11 个活动，每个有开始时间 s、结束时间 f、编号 id
Step 1  排序
  按结束时间 f 从小到大排列所有活动
Step 2  加哨兵
  头部加 a[0]：s=0, f=0
  尾部加 a[12]：s=INF, f=INF
  数组共 13 个元素，下标 0~12
Step 3  初始化
  c[i][j] = 0        对所有 (i,j)
  actTable[i][j] = -1  对所有 (i,j)
Step 4  三层循环填表
  外层 l = 2, 3, ..., 12     （区间跨度，从短到长）
    中层 i = 0, 1, ..., 12-l  （枚举左端点）
      j = i + l               （计算右端点）
      内层 k = i+1, ..., j-1  （枚举候选中间活动）
        若 a[k].s >= a[i].f
        且 a[k].f <= a[j].s：  （a[k] 属于 S_ij）
          val = c[i][k] + c[k][j] + 1
          若 val > c[i][j]：
            c[i][j] = val
            actTable[i][j] = k
Step 5  读取答案
  最大兼容活动数 = c[0][12]
Step 6  回溯输出
  printSolution(0, 12)：
    若 actTable[i][j] == -1：返回（此区间无活动）
    k = actTable[i][j]
    递归 printSolution(i, k)   输出更早的活动
    输出 a[k].id               输出当前活动
    递归 printSolution(k, j)   输出更晚的活动

十二、算法复杂度

时间复杂度：三层循环，每层最多 $n$ 次，共 $O(n^3)$。回溯最多走 $n$ 步，$O(n)$。总体 $O(n^3)$。
空间复杂度：$c$ 表和 $\text{actTable}$ 各是 $(n+2)\times (n+2)$ 的二维数组，共 $O(n^2)$。

十三、总结

---

项目	内容
问题目标	选出最多个互相兼容的活动
核心思想	枚举每个区间的"中间活动"，把区间分为左右两半分别求最优
DP 状态	$c[i][j]$：区间 $S_{ij}$ 中最多能选几个活动
填表顺序	按跨度 $l=j-i$ 从 2 到 12，由短到长
回溯方式	递归读 $\text{actTable}$，先左后右输出
最终结果	最大兼容活动数 = 4，选中 $a_1,a_4,a_8,a_{11}$
时间复杂度	$O(n^3)$
空间复杂度	$O(n^2)$

---

习题 15.1-2：最晚开始的贪心策略

题目

将"选结束最早的活动"改为"选开始最晚的兼容活动"，证明这也是最优的。

理解思路

原始贪心：从左往右，每次选结束最早的。
新贪心：从右往左，每次选开始最晚的。
两者是对称的。想象把时间轴翻转（令 $s_i^{\prime }=-f_i$，$f_i^{\prime }=-s_i$），原问题变成翻转后的"选结束最早"，是同一个策略。

正式证明思路

设 $S_k$ 是从某活动 $a_k$ 之前开始的所有活动。
设 $a_m$ 是 $S_k$ 中开始最晚的活动，$A_k$ 是 $S_k$ 的任意最大兼容子集，$a_j$ 是 $A_k$ 中开始最晚的活动。
若 $a_j=a_m$，命题成立。
若 $a_j\ne a_m$，因为 $a_m$ 是开始最晚的，所以 $s_m\ge s_j$。
用 $a_m$ 替换 $a_j$：

• $a_m$ 的开始时间 $s_m\ge s_j$，所以 $a_m$ 不会与 $A_k$ 中比 $a_j$ 更晚的活动产生冲突（因为 $a_j$ 本身没有冲突）
• $A_k$ 的大小不变
  因此替换后仍是最大子集，且包含 $a_m$，贪心选择安全。

关键对比

原始贪心（最早结束优先）：
  时间轴 --> 扫描方向
  选 a1，然后在 a1 结束后的活动中继续选
新贪心（最晚开始优先）：
  时间轴 <-- 扫描方向（从右往左）
  选最后一个开始的活动，然后在它开始前的活动中继续选

两者产生的解集大小相同（都是最大的），但具体选出的活动可能不同。

习题 15.1-3：错误的贪心策略

题目

给出反例，说明以下三种贪心策略不能保证最优：

1. 每次选持续时间最短的兼容活动
2. 每次选与其他剩余活动重叠最少的兼容活动
3. 每次选开始时间最早的兼容活动

策略一反例：最短持续时间

设有三个活动：

时间轴:  0----1----2----3----4----5----6
活动 A:       [=====]            (时长=2, s=1, f=3)
活动 B:  [=============]         (时长=4, s=0, f=4, 持续时间最短... 不对)

构造更直接的反例，活动如下：

时间轴:  0----1----2----3----4
活动 A:  [=========]            (s=0, f=3, 时长=3)
活动 B:       [=]               (s=1, f=2, 时长=1) <-- 最短
活动 C:            [=========]  (s=2, f=4, 时长=2)

贪心选最短：选 B（时长1），但 B 与 A、C 都冲突，最终只选出 {B}，共 1 个。
最优解：选 {A, C}，共 2 个。
贪心失败。

策略二反例：与剩余活动重叠最少

构造活动（每个活动与哪些重叠标注出来）：

时间轴:  0--1--2--3--4--5--6--7--8
活动 A:  [====]                     (s=0,f=2) 与B重叠
活动 B:     [====]                  (s=1,f=3) 与A,C,D重叠  <-- 重叠最少? 不一定
活动 C:        [====]               (s=2,f=4) 与B,D重叠
活动 D:           [====]            (s=3,f=5) 与B,C重叠
活动 E:                 [====]      (s=5,f=7) 与D重叠

通过精心构造，可以让"重叠最少"的活动把两边都堵死，导致只选 1 个，而最优是选 3 个。这类反例在几何上很直观：中间那个"桥接"活动重叠少，但选了它就把两侧隔开了。

策略三反例：最早开始时间

时间轴:  0----1----2----3----4----5
活动 A:  [=================]        (s=0, f=5) 开始最早
活动 B:       [===]                 (s=1, f=3)
活动 C:            [===]            (s=3, f=5)

贪心选最早开始：选 A（s=0），A 占据整个时间段，无法再选其他。最终 {A}，共 1 个。
最优解：{B, C}，共 2 个。
贪心失败。原因：开始早的活动可能持续时间很长，"霸占"资源。

习题 15.1-4：最少讲堂数问题

题目

给定所有活动，每个讲堂同一时间只能容纳一个活动。用最少的讲堂安排所有活动。

理解思路

这等价于"区间图着色问题"：把每个活动看作一个顶点，两个时间重叠的活动之间连边。求最少需要多少种颜色（讲堂），使相邻顶点颜色不同。
关键定理：需要的最少讲堂数 = 同一时刻最多有多少个活动同时进行（称为"最大重叠深度"）。

贪心策略

按开始时间排序，用最小堆维护当前各讲堂的"最早空闲时间"：

对每个活动 a_i（按开始时间排序）：
    如果存在某个讲堂在 s_i 之前就空了（堆顶 <= s_i）：
        把 a_i 分配给该讲堂，更新该讲堂的空闲时间为 f_i
    否则：
        开一个新讲堂，分配 a_i

C++ 完整实现

#include <vector>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
struct Activity {
    int s, f, id;
};
// 返回所需讲堂数，并输出每个活动分配到哪个讲堂
int minLectureHalls(vector<Activity>& acts) {
    int n = acts.size();
    if (n == 0) return 0;
    // 按开始时间升序排列
    sort(acts.begin(), acts.end(),
         [](const Activity& a, const Activity& b) {
             return a.s < b.s;
         });
    // 最小堆：存 (讲堂当前活动的结束时间, 讲堂编号)
    // 堆顶 = 最早空闲的讲堂
    priority_queue<pair<int,int>,
                   vector<pair<int,int>>,
                   greater<pair<int,int>>> pq;
    vector<int> hallAssign(n); // hallAssign[i] = 活动 i 分配到哪个讲堂
    int hallCount = 0;
    for (int i = 0; i < n; i++) {
        if (!pq.empty() && pq.top().first <= acts[i].s) {
            // 存在讲堂已经空了，复用它
            auto [finishTime, hallId] = pq.top();
            pq.pop();
            hallAssign[i] = hallId;
            pq.push({acts[i].f, hallId}); // 更新该讲堂的最新结束时间
        } else {
            // 没有空闲讲堂，新开一个
            hallCount++;
            hallAssign[i] = hallCount;
            pq.push({acts[i].f, hallCount});
        }
    }
    // 输出分配结果
    for (int i = 0; i < n; i++) {
        cout << "活动 a" << acts[i].id
             << " [" << acts[i].s << "," << acts[i].f << ")"
             << " --> 讲堂 " << hallAssign[i] << endl;
    }
    return hallCount;
}
int main() {
    vector<Activity> acts = {
        {1,  4,  1}, {3,  5,  2}, {0,  6,  3},
        {5,  7,  4}, {3,  9,  5}, {5, 11,  6},
        {6, 10,  7}, {8, 12,  8}, {8, 14,  9},
        {2, 14, 10}, {12, 16, 11}
    };
    int halls = minLectureHalls(acts);
    cout << "共需讲堂数：" << halls << endl;
    return 0;
}

执行追踪示意

按开始时间排序后：
  a3(0~6), a1(1~4), a2(3~5), a10(2~14), a5(3~9),
  a4(5~7), a6(5~11), a7(6~10), a8(8~12), a9(8~14), a11(12~16)
i=0 a3[0~6):  堆空，开讲堂1，堆={(6,1)}
i=1 a1[1~4):  堆顶(6,1)，6>1 不空，开讲堂2，堆={(4,2),(6,1)}
i=2 a2[3~5):  堆顶(4,2)，4>3 不空，开讲堂3，堆={(5,3),(6,1),(4,2)}
...（继续复用或新开讲堂）

时间复杂度：$O(n\log n)$（排序 + 堆操作）。

习题 15.1-5：带权活动选择

题目

每个活动 $a_i$ 额外有价值 $v_i$。不再最大化活动数量，而是最大化选出活动的总价值。给出多项式时间算法。

理解思路

这是经典的"带权区间调度"问题，贪心不再适用，必须用动态规划。
定义 $p(i)$：在活动 $a_i$（按结束时间排序）中，最大的满足 $f_{p(i)}\le s_i$ 的 $p(i)$（即与 $a_i$ 兼容且结束时间最晚的活动）。
定义 $dp[i]$：前 $i$ 个活动能获得的最大价值。
递推式：
$$dp[i]=\max (dp[i-1],v_i+dp[p(i)])$$
解释：

• $dp[i-1]$：不选 $a_i$，沿用前 $i-1$ 个活动的最优解
• $v_i+dp[p(i)]$：选 $a_i$，加上与 $a_i$ 兼容的最优子问题的解

C++ 完整实现

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
struct Activity {
    int s, f, v, id; // 开始时间、结束时间、价值、编号
};
// 二分查找：找最大的 j 满足 acts[j].f <= target
// acts 已按结束时间排序，下标从 0 开始（0 号为哨兵）
int findLatestCompatible(const vector<Activity>& acts, int i) {
    int lo = 0, hi = i - 1, ans = 0;
    while (lo <= hi) {
        int mid = (lo + hi) / 2;
        if (acts[mid].f <= acts[i].s) {
            ans = mid;
            lo = mid + 1;
        } else {
            hi = mid - 1;
        }
    }
    return ans;
}
int weightedActivitySelector(vector<Activity>& acts) {
    int n = acts.size();
    if (n == 0) return 0;
    // 按结束时间排序
    sort(acts.begin(), acts.end(),
         [](const Activity& a, const Activity& b) {
             return a.f < b.f;
         });
    // 在下标 0 插入哨兵（结束时间=0，价值=0）
    acts.insert(acts.begin(), {0, 0, 0, 0});
    n++;
    // dp[i]：前 i 个活动（含哨兵）的最大价值
    vector<int> dp(n, 0);
    vector<int> choice(n, 0); // 用于回溯
    for (int i = 1; i < n; i++) {
        int p = findLatestCompatible(acts, i); // p(i)
        int includeVal = acts[i].v + dp[p]; // 选 a_i
        int excludeVal = dp[i - 1];          // 不选 a_i
        if (includeVal >= excludeVal) {
            dp[i] = includeVal;
            choice[i] = 1; // 选了 a_i
        } else {
            dp[i] = excludeVal;
            choice[i] = 0; // 没选 a_i
        }
    }
    // 回溯输出选中的活动
    cout << "最大总价值：" << dp[n - 1] << endl;
    cout << "选中的活动：";
    int i = n - 1;
    while (i > 0) {
        if (choice[i] == 1) {
            cout << "a" << acts[i].id << "(v=" << acts[i].v << ") ";
            i = findLatestCompatible(acts, i); // 跳到 p(i)
        } else {
            i--;
        }
    }
    cout << endl;
    return dp[n - 1];
}
int main() {
    vector<Activity> acts = {
        {1, 4,  3, 1},
        {3, 5,  2, 2},
        {0, 6,  7, 3},
        {5, 7,  1, 4},
        {3, 9,  4, 5},
        {5, 11, 2, 6},
    };
    weightedActivitySelector(acts);
    return 0;
}

时间复杂度：$O(n\log n)$（排序 + 对每个活动二分查找 $p(i)$）。

习题 15.2-1：分数背包的贪心选择性质

题目

证明分数背包问题具有贪心选择性质。

问题设定

有 $n$ 件物品，第 $i$ 件重 $w_i$，价值 $v_i$，可以取任意分数。背包容量为 $W$。目标：最大化装入背包的总价值。
贪心策略：按单位重量价值 $v_i/w_i$ 降序排列，依次尽量多取。

证明

设物品已按 $v_1/w_1\ge v_2/w_2\ge \cdots \ge v_n/w_n$ 排序。
设 $S^{\ast }$ 是某个最优解，考虑它对物品 1 的取用量 $x_1^{\ast }$。
情况一：$x_1^{\ast }=\min (w_1,W)$（贪心选择，尽量多取物品 1）。最优解已经做出了贪心选择，命题成立。
情况二：$x_1^{\ast }<\min (w_1,W)$，即最优解没有把物品 1 取满。此时背包还有空余或者没取满物品 1，却取了某个 $j\ne 1$ 的物品（取了 $x_j^{\ast }>0$ 的量）。
构造新方案 $S^{\prime }$：把 $S^{\ast }$ 中物品 $j$ 减少 $\delta$，改为增加物品 1 的量 $\delta$，其中 $\delta$ 足够小使两者都合法。
价值变化量为：
$$\Delta =\delta \cdot \frac{v_1}{w_1}-\delta \cdot \frac{v_j}{w_j}=\delta \left(\frac{v_1}{w_1}-\frac{v_j}{w_j}\right)\ge 0$$
因为 $v_1/w_1\ge v_j/w_j$，所以 $\Delta \ge 0$，新方案不比原方案差。
反复做这个替换，直到物品 1 取满，得到包含贪心选择的最优解。因此贪心选择性质成立。

习题 15.2-2：0-1 背包的动态规划

题目

给出 $O(nW)$ 时间的 0-1 背包动态规划解法。

理解递推式

0-1 背包：每件物品只能取（1）或不取（0）。
设 $dp[i][w]$：从前 $i$ 件物品中选，总重量不超过 $w$ 时的最大价值。
$$dp[i][w]=\{\begin{array}{ll}dp[i-1][w]& \text{若 }{w}_i>w\text{（放不下，不选）}\\ \max (dp[i-1][w],dp[i-1][w-w_i]+v_i)& \text{若 }{w}_i\le w\end{array}$$
用人话说：

• 不选第 $i$ 件：价值与前 $i-1$ 件、容量 $w$ 的最优解相同
• 选第 $i$ 件：用 $w_i$ 重量换来 $v_i$ 价值，加上剩余容量 $w-w_i$ 下前 $i-1$ 件的最优解

填表示意（小例子）

3 件物品，容量 $W=5$：

物品	重量	价值
1	2	6
2	2	10
3	3	12

---

$dp$ 表（行=物品，列=容量）：

	w=0	w=1	w=2	w=3	w=4	w=5
i=0	0	0	0	0	0	0
i=1	0	0	6	6	6	6
i=2	0	0	10	10	16	16
i=3	0	0	10	12	16	22

---

最优解 $dp[3][5]=22$，选物品 2（价值10）+ 物品 3（价值12）。

C++ 完整实现

#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
struct Item {
    int w; // 重量
    int v; // 价值
};
// dp[i][w]：前 i 件物品，容量 w 下的最大价值
int knapsack01(const vector<Item>& items, int W) {
    int n = items.size();
    // dp 表，初始化全 0（0 件物品或容量 0 时价值都是 0）
    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
    for (int i = 1; i <= n; i++) {
        int wi = items[i - 1].w;
        int vi = items[i - 1].v;
        for (int w = 0; w <= W; w++) {
            // 不选第 i 件物品
            dp[i][w] = dp[i - 1][w];
            // 选第 i 件物品（前提：放得下）
            if (wi <= w) {
                dp[i][w] = max(dp[i][w], dp[i - 1][w - wi] + vi);
            }
        }
    }
    // 回溯：找出选了哪些物品
    cout << "最大价值：" << dp[n][W] << endl;
    cout << "选中物品：";
    int w = W;
    for (int i = n; i >= 1; i--) {
        if (dp[i][w] != dp[i - 1][w]) {
            // 第 i 件被选中了
            cout << "物品" << i
                 << "(w=" << items[i-1].w
                 << ",v=" << items[i-1].v << ") ";
            w -= items[i - 1].w;
        }
    }
    cout << endl;
    return dp[n][W];
}
int main() {
    vector<Item> items = {{2, 6}, {2, 10}, {3, 12}};
    int W = 5;
    knapsack01(items, W);
    // 最大价值：22
    // 选中物品：物品3(w=3,v=12) 物品2(w=2,v=10)
    return 0;
}

时间复杂度：$O(nW)$（两层循环）。
空间复杂度：$O(nW)$（可优化为 $O(W)$，每次只用前一行）。

习题 15.2-4：教授滑冰过北达科他

题目

沿公路有若干补水站，教授一次最多滑行 $m$ 英里。求停靠站数最少的路线。

贪心策略

每次走到能到达的最远补水站（但不超过当前位置 + $m$ 英里）再停。
用人话说：每次补水都尽量"不浪费"，能走多远就走多远再补。

正确性证明思路

设 $s_1,s_2,\dots$ 是贪心选择的停靠站序列，$s_1^{\ast },s_2^{\ast },\dots$ 是某个最优解的停靠站序列。
用交换论证：最优解的第一个停靠站 $s_1^{\ast }$ 必然在贪心解的第一个停靠站 $s_1$ 之前（或相同），因为贪心解选的是能到达的最远站。
把最优解的第一站换成 $s_1$：

• 若 $s_1=s_1^{\ast }$：无变化
• 若 $s_1$ 在 $s_1^{\ast }$ 之后：从 $s_1$ 出发，后续路程不变，但第一段走得更远，不会增加停靠次数
  如此归纳，贪心解的停靠次数不多于任何最优解，因此贪心最优。

C++ 完整实现

#include <vector>
#include <iostream>
using namespace std;
// stops：所有补水站的里程（含起点0和终点D）
// m：一次最多走多少英里
// 返回：最少停靠站编号列表（不含起点）
vector<int> minWaterStops(const vector<int>& stops, int m) {
    int n = stops.size();
    vector<int> chosen; // 选择的停靠站下标
    int cur = 0; // 当前位置的下标
    while (cur < n - 1) { // 还没到终点
        // 找从 stops[cur] 出发，能到达的最远站
        int farthest = cur;
        for (int j = cur + 1; j < n; j++) {
            if (stops[j] - stops[cur] <= m) {
                farthest = j;
            } else {
                break;
            }
        }
        if (farthest == cur) {
            // 连下一站都到不了，无解
            cout << "无法完成全程（相邻站距离超过 " << m << " 英里）" << endl;
            return {};
        }
        if (farthest < n - 1) {
            // 不是终点，需要在 farthest 处补水
            chosen.push_back(farthest);
        }
        cur = farthest;
    }
    return chosen;
}
int main() {
    // 补水站位置（英里），第一个是起点0，最后一个是终点
    vector<int> stops = {0, 10, 18, 25, 40, 55, 60, 75, 90, 100};
    int m = 25; // 一次最多走 25 英里
    vector<int> result = minWaterStops(stops, m);
    cout << "最少停靠 " << result.size() << " 次" << endl;
    cout << "停靠站里程：";
    for (int idx : result) {
        cout << stops[idx] << " ";
    }
    cout << endl;
    return 0;
}

时间复杂度：$O(n)$（单次扫描）。

习题 15.4-2：LRU 策略不是最优的反例

题目

给出请求序列，使得 LRU（驱逐最久未使用的块）比最远将来使用策略产生更多缺失。

什么是 LRU

LRU（Least Recently Used）：缓存满时，驱逐"最近最久没被访问"的块。
可以理解为"过去最远使用"，与"将来最远使用"对称。

反例构造

缓存容量 $k=2$，请求序列：$1,2,3,1,2,3,1,2,3$

请求序列:  1  2  3  1  2  3  1  2  3

LRU 策略执行过程：

请求 1: 缓存={1}        命中? 否  缺失=1
请求 2: 缓存={1,2}      命中? 否  缺失=2
请求 3: 缓存满，LRU驱逐最久未用=1，加入3  缓存={2,3}  缺失=3
请求 1: 缓存满，LRU驱逐最久未用=2，加入1  缓存={3,1}  缺失=4
请求 2: 缓存满，LRU驱逐最久未用=3，加入2  缓存={1,2}  缺失=5
请求 3: 缓存满，LRU驱逐最久未用=1，加入3  缓存={2,3}  缺失=6
请求 1: 缓存满，驱逐2  缓存={3,1}  缺失=7
请求 2: 缓存满，驱逐3  缓存={1,2}  缺失=8
请求 3: 缓存满，驱逐1  缓存={2,3}  缺失=9
LRU 总缺失：9

最远将来使用策略执行过程：

请求 1: 缓存={1}        缺失=1
请求 2: 缓存={1,2}      缺失=2
请求 3: 缓存满
        块1 下一次在位置 3（很快）
        块2 下一次在位置 4（稍远）
        驱逐块2，加入3  缓存={1,3}  缺失=3
请求 1: 缓存={1,3}  命中！
请求 2: 缓存满
        块1 下一次在位置 6
        块3 下一次在位置 5
        驱逐块1（下次更远），加入2  缓存={3,2}  缺失=4
请求 3: 命中！
请求 1: 缓存满
        块3 下一次在位置 8
        块2 下一次在位置 7
        驱逐块3，加入1  缓存={2,1}  缺失=5
请求 2: 命中！
请求 3: 缓存满
        块2 不再出现（INT_MAX）
        块1 不再出现（INT_MAX）
        驱逐任意一个，加入3  缓存={1,3}（或{2,3}）  缺失=6
最远将来使用 总缺失：6

---

策略	总缺失次数
LRU	9
最远将来使用（最优）	6

---

LRU 比最优策略多了 3 次缺失。这个反例的本质：请求序列循环访问比缓存容量多 1 个不同的块（1,2,3 共 3 个，缓存只有 2 个），LRU 在这种"循环模式"下会连续缺失，是其最坏情况。

总结：贪心策略的适用判断

是否适用贪心的两个核心问题：
1. 做出局部最优选择后，只剩一个子问题吗？
   （贪心选择性质）
2. 这个子问题的最优解，加上当前的贪心选择，
   能构成原问题的最优解吗？
   （最优子结构）
两者都满足 --> 贪心可行
否则      --> 考虑动态规划

---

问题	贪心可行？	贪心策略	若不可行的原因
活动选择（最大数量）	可行	选结束最早	—
活动选择（最大价值）	不可行	—	权重不同，局部最优不等于全局最优
分数背包	可行	按价值密度降序取	—
0-1 背包	不可行	—	不能拆分，空间浪费影响全局
Huffman 编码	可行	合并最小两个节点	—
离线缓存	可行	驱逐最远将来使用	—

---