贪心、分治与回溯

环境：Windows 11 x64，GCC 13.1.0，g++ -std=c++17 -O2。贪心实现全部与暴力/DP 参照做过随机对拍。

一、贪心只有一个问题：它凭什么对

贪心 = 每步取局部最优，且不回退。要它对，必须证明两件事之一：

交换论证：任取一个最优解，把它逐步”换成”贪心解，目标值不劣 → 贪心解也是最优。
拟阵/贪心选择性质：存在一个最优解包含当前的贪心选择。

证不出来就别用贪心。 下面的实测会告诉你代价有多大。

二、找零：贪心在 16.3% 的情况下是错的

int greedy_coins(const vector<int> &coins, int amount) {      /* 每次拿最大的可用面值 */
    int n = 0;
    for (int i = coins.size()-1; i >= 0; i--) while (amount >= coins[i]) { amount -= coins[i]; n++; }
    return amount == 0 ? n : -1;
}

4000 组随机币制（含面值 1，2–4 种面值）、金额 1..60，与完全背包 DP 比对：

4000 个随机币制 × 金额 1..60：贪心与 DP 不同的比例 16.3%（39233/240000）
  反例 币制 = {1, 4, 9, 10}，金额 18：贪心 3 枚，最优 2 枚（9+9）
  经典反例 {1,3,4} 凑 6：贪心 3 枚（4+1+1），最优 2 枚（3+3）

只有”规范币制”（canonical coin system）才能让贪心成立——人民币、美元的面值恰好是精心设计的规范系统，所以”贪心找零”这个例子从教科书里看起来天经地义。给定任意面值集，它是错的，而且错 16% 的查询。

判据：只要”当前最优选择会影响后续可选空间”，贪心就需要证明；否则用 DP。

三、区间调度：贪心策略选错，答案从 3 掉到 1

问题：给一堆区间，选最多的互不重叠区间。

sort(iv, by 结束时间);
int cnt = 0, last = -∞;
for (auto [s, e] : iv) if (s >= last) { cnt++; last = e; }

400 组随机区间（n ≤ 13，暴力枚举全部 2ⁿ 个子集验证）：

400 组随机区间：按结束时间贪心 == 最优：1
换成"按开始时间"贪心：区间 {0,10} {1,2} {3,4} {5,6} → 得 1，最优是 3

为什么是结束时间：一个区间结束得越早，留给后面的空间越大。交换论证：设最优解第一个区间是 b，贪心选的是结束最早的 a，则 a.end ≤ b.end，把 b 换成 a 不会与后续冲突 → 贪心解不劣。

按开始时间贪心会被一个”超长区间”卡死：{0,10} 一开始就占满全场。“看起来最自然”的策略往往是错的，这就是必须对拍的原因。

问题	贪心策略
最多不重叠区间	按结束时间
最少会议室数 / 最少颜色	按开始时间扫描 + 小顶堆维护结束时间
区间覆盖（用最少区间盖住 [0,T]）	每次选”左端点 ≤ 当前覆盖右界且右端点最大”的
任务调度（截止日 + 收益）	按收益降序 + 并查集找可用时段

四、哈夫曼：贪心 + 优先队列

带权路径最短的前缀码。贪心策略：每次取两个最小权值合并。

priority_queue<int, vector<int>, greater<int>> pq;      /* 小顶堆 */
for (int w : weights) pq.push(w);
long long cost = 0;
while (pq.size() > 1) {
    int a = pq.top(); pq.pop();
    int b = pq.top(); pq.pop();
    cost += a + b;                    /* 这两个字符各多一层 */
    pq.push(a + b);
}

它的正确性也靠交换论证（最深的一对一定是权值最小的两个）。注意 cost 要 long long：权值大或字符多时 int 会溢出——DP 那一节说过的”值域检查”在这里同样适用。

工程上更常见的是定长 Huffman / 规范 Huffman（canonical Huffman）：只存码长不存码树，DEFLATE、ZIP、PNG、MP3 都用它，因为码树本身也要占空间。

五、分治：把”递归结构”用足

分治的三件事：分解 → 递归 → 合并。合并步骤的代价决定总复杂度：

算法	递推式	结果
归并排序	T(n) = 2T(n/2) + O(n)	O(n log n)
快速排序（平均）	T(n) = T(k) + T(n-k) + O(n)	O(n log n)，最坏 O(n²)
二分查找	T(n) = T(n/2) + O(1)	O(log n)
主定理情形 1	T(n) = 2T(n/2) + O(n^0.5)	O(n^0.5·…) 视 log 而定
Strassen 矩阵乘	T(n) = 7T(n/2) + O(n²)	O(n^2.81)

实践提醒（第八节实测过）：分治的递归深度必须可控。快排要”先递归小的、再循环大的”（tail-call 优化）把栈深压到 O(log n)；否则对抗输入能把栈打爆。

六、回溯：本质是带剪枝的 DFS

N 皇后是标准案例。朴素版每次在整列里检查冲突；位运算版用三个整数表示”列 / 两条对角线”的占用：

void go(int row, int cols, int d1, int d2) {
    if (row == n) { cnt++; return; }
    int avail = ((1 << n) - 1) & ~(cols | d1 | d2);      /* 本行可放的列 */
    while (avail) {
        int bit = avail & -avail;                          /* 取最低位的 1 */
        avail -= bit;
        go(row + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1);
    }
}

实测（解数与已知的 N 皇后序列 92 / 352 / 724 / 2680 / 14200 完全一致）：

n= 8  解数 92    朴素 0.2 ms | 位运算 0.0 ms（快 5.2 倍）
n=10  解数 724   朴素 4.6 ms | 位运算 0.4 ms（快 10.9 倍）
n=12  解数 14200 朴素 115.1 ms | 位运算 10.8 ms（快 10.7 倍）

位运算快 10 倍的原因：冲突检查从”遍历已放置的 r 个皇后”（O(n)）变成”一次位运算”（O(1)），且 avail & -avail 枚举可行位置比 for (c = 0..n) 跳过大量无效分支。

回溯的三个提速层次（按收益排序）：

剪枝：在扩展节点前判断”当前部分解是否可能达到目标”，不行就 return。这是数量级的收益。
可行位置位集：像上面那样把”哪些选择合法”编码成位掩码，枚举成本降到 O(可行数)。
对称性/序约束：强制解按某种顺序生成（如组合里要求递增），避免同一解被数多次。

再往上就是记忆化（把回溯变成 DP）和启发式（A*、迭代加深）。

七、什么时候用哪个

特征	选择
能证明贪心选择性质	贪心（最快，代码最短）
有重叠子问题 + 最优子结构	DP
状态数少但转移复杂	记忆化搜索
只要判定/枚举所有解，n ≤ 30 左右	回溯 + 剪枝
问题能切成独立子问题	分治
只要近似解，且要界	贪心近似算法（如集合覆盖 ln n 近似）

顺序建议：先想贪心（能证就用），证不动就 DP，DP 状态太多就回溯剪枝。

八、这一节的自查清单

用贪心前先写交换论证，或者写个暴力版对拍几百组随机数据
贪心策略要测多个候选（开始时间/结束时间/最短区间/密度），别默认”最自然的”就对
随机对拍要覆盖到”贪心会错”的构造（币制、区间重叠密集的情况）
累加权值/成本时用 long long，先估值域上界
回溯必须写剪枝，且把冲突检查降到 O(1)（位掩码/布尔数组，不是每次遍历）
分治递归深度可控：先递归小的分支，或用尾递归优化
计数类问题（N 皇后解数）拿已知序列核对，别只看”跑完了”
需要输出所有解时注意去重（对称解、重复元素要先排序 + 跳过同层重复值）
状态压缩回溯（dp[mask]）能解 TSP 到 n≈20，比 O(n!) 快得多

下一节讲进阶结构专题：并查集与路径压缩、字典树、树状数组与线段树、跳表与 LRU 缓存。