前言贪心算法greedy algorithm是每一步都选当前看起来最好的那个的算法范式。它的代码往往只有十几行比动态规划dynamic programmingDP短得多但正确性门槛比 DP 高得多DP 只要状态和转移写对就必然正确而贪心必须证明局部最优能推出全局最优证不出来就不能用。最常见的三个误解是以为局部最优是显然的。于是随手按某个规则排序跑出结果就交差了。经典反例用贪心解 0/1 背包问题会得到错误答案本文第三节给出具体算例。以为贪心是 DP 的简化版随时可以互相替换。事实上它们是两种不同的正确性模型。有些问题比如区间调度贪心可解而 DP 反而麻烦有些问题比如 0/1 背包DP 可解而贪心根本不成立。以为排序后用贪心就是贪心算法。排序常常是贪心的预处理步骤但排序键选错整个算法就错了——而且错得很难发现因为程序不会报错只是结果偏小或偏大。本文讲三件事贪心成立的两个必要条件、两种证明思路交换论证与归纳、以及四个经典问题的完整可编译实现与一个明确的反例。代码基于 C17可在 GCC 13 / Clang 17 / MSVC 19.3x 上编译。一、贪心成立的两个前提贪心算法要正确必须同时满足两个性质性质含义不满足时的症状贪心选择性质greedy choice property每一步的局部最优选择都包含在某个全局最优解中结果偏大或偏小且无法通过补救修正最优子结构optimal substructure做出贪心选择后剩下的子问题仍是最优子问题做出选择后剩余问题的解与全局最优解不一致这两个性质不是看起来像就成立的必须证明。反例是检验的最好工具能构造出一个贪心结果 ≠ 最优解的输入就能立刻否掉贪心。一个重要的判据如果问题要求每个元素只能整体选或不选贪心通常不成立如果元素可以按比例切分贪心常常成立。分数背包fractional knapsack能用贪心0/1 背包不能差别就在这里。二、两种证明思路思路一交换论证exchange argument。设贪心算法的解是G某个最优解是O。证明的核心是如果G和O的第一个不同之处是G选了元素x而O选了y那么可以把O中的y换成x得到的解O依然是最优的。反复交换最终把O变成G于是G也是最优的。以区间调度为例见 3.1 节设y是最优解里结束最早的那个区间x是贪心选出的结束最早的区间因为x的结束时间不晚于y把y换成x不会和后面的区间冲突。思路二归纳法。证明贪心选择之后剩下的问题规模更小且原问题的最优解等于贪心选择加上子问题的最优解。这更像是 DP 的思路但用在贪心上要求子问题的最优解可以由同一个贪心规则递归得到。实践建议不要在比赛或工程里追求严格的形式化证明。更实用的两个做法是写一个暴力/DP 的对照程序在小规模随机数据上对拍以及刻意去构造反例。三、四个经典问题与一个反例3.1 区间调度活动选择—— 按结束时间排序问题给若干个区间[start, end)选出尽可能多的互不重叠的区间。贪心策略按结束时间升序排序依次选取开始时间不早于上一个被选区间结束时间的区间。为什么按结束时间而不是开始时间按开始时间排序会选到开始很早但拖得很长的区间把后面一大片时间全堵死按结束时间排序每次留下的空余最多。这是交换论证的标准结论。#include algorithm #include cstddef #include iostream #include utility #include vector // 返回最多能选出的互不重叠区间个数 std::size_t maxNonOverlapping(std::vectorstd::pairint, int intervals) { if (intervals.empty()) return 0; std::sort(intervals.begin(), intervals.end(), [](const std::pairint, int a, const std::pairint, int b) { return a.second b.second; // 按结束时间升序 }); std::size_t count 1; int lastEnd intervals[0].second; for (std::size_t i 1; i intervals.size(); i) { if (intervals[i].first lastEnd) { // 不重叠 count; lastEnd intervals[i].second; } } return count; } int main() { std::vectorstd::pairint, int data{{1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}}; std::cout maxNonOverlapping(data) \n; // 3(1,4) (5,7) (8,11) return 0; }3.2 分数背包 —— 按性价比排序问题背包有承重上限物品可以按任意比例切分求能装入的最大价值。贪心策略按单位重量价值价值 ÷ 重量降序排序能整件装就整件装装不下就切一部分。#include algorithm #include cstddef #include iomanip #include iostream #include vector struct Item { double weight; double value; }; double fractionalKnapsack(std::vectorItem items, double capacity) { std::sort(items.begin(), items.end(), [](const Item a, const Item b) { // 比较单位重量价值用乘法避免除法的精度问题 return a.value * b.weight b.value * a.weight; }); double total 0.0; for (const Item it : items) { if (capacity 0.0) break; const double take std::min(capacity, it.weight); total take * (it.value / it.weight); capacity - take; } return total; } int main() { std::vectorItem items{{10.0, 60.0}, {20.0, 100.0}, {30.0, 120.0}}; std::cout std::fixed std::setprecision(2) fractionalKnapsack(items, 50.0) \n; // 240.00 return 0; }注意比较器用的是交叉相乘a.value * b.weight b.value * a.weight而不是直接比较两个商。两者数学上等价但乘法避免了浮点除法的精度误差也避开了weight 0时的除零。3.3 贪心找零 —— 只在特定面额下成立问题用尽量少的硬币凑出指定金额。贪心策略每次拿面额不超过剩余金额的最大硬币。这个策略只在规范硬币系统canonical coin system下正确。人民币的 1、2、5、10、20、50、100 元以及常用的 1、5、10、25 美分属于这类系统贪心给出最优解。但面额换成{1, 3, 4}就不成立了——反例面额{1, 3, 4}目标金额6。贪心先拿 4剩 2再拿 1剩 1再拿 1剩 0。一共3 枚。最优3 3一共2 枚。#include algorithm #include cstddef #include functional #include iostream #include vector // 贪心找零只在规范硬币系统下给出最优解{1,3,4} 是反例 int greedyCoins(const std::vectorint coins, int amount) { std::vectorint sorted coins; std::sort(sorted.begin(), sorted.end(), std::greaterint()); int used 0; for (int c : sorted) { if (amount 0) break; used amount / c; amount % c; } return (amount 0) ? used : -1; // -1 表示无法凑出 } int main() { std::cout greedy({1,3,4}, 6) greedyCoins({1, 3, 4}, 6) \n; // 3 std::cout greedy({1,5,10,50}, 63) greedyCoins({1, 5, 10, 50}, 63) \n; // 6 return 0; }换面额就不是贪心能解决的问题了得用 DPdp[i] min(dp[i - coin] 1)。这个例子最能说明贪心不是通用技巧它依赖问题的具体性质。3.4 霍夫曼编码 —— 每次合并最小的两个问题给一组带权字符构造前缀编码使总编码长度最短。贪心策略每次取出权值最小的两个节点合并成一个新节点新节点权值为两者之和放回集合重复直到只剩一个节点。用std::priority_queue做最小堆是最自然的实现。#include functional #include iostream #include queue #include vector // 返回合并的总代价也就是编码后的总位数 long long huffmanCost(std::vectorlong long weights) { std::priority_queuelong long, std::vectorlong long, std::greaterlong long pq( std::greaterlong long(), std::move(weights)); // 容器被移动构造不复制 long long total 0; while (pq.size() 2) { const long long a pq.top(); pq.pop(); const long long b pq.top(); pq.pop(); total a b; pq.push(a b); } return total; } int main() { std::vectorlong long w{5, 9, 12, 13, 16, 45}; std::cout huffmanCost(w) \n; // 224 return 0; }霍夫曼算法的正确性有严格证明交换论证 归纳属于贪心选择性质的标准案例这也是它被视为贪心算法典范的原因。3.5 反例0/1 背包不能用贪心问题物品不能切分每件要么完整拿走要么不拿。反例背包容量10三件物品物品重量价值单位价值A6305.00B5204.00C5204.00按单位价值贪心先拿 A剩 4装不下 B 和 C总价值30。按价值贪心先拿 A同上总价值30。真正的最优解拿 B 和 C总价值40重量恰好5 5 10。贪心在这里失败的根本原因是它一旦拿了 A 就无法回退而 A 占了 6 份容量却只带来 30 的价值把两个各占 5 份、合计 40 价值的物品挤掉了。0/1 背包需要 DP状态是前 i 件物品、容量 j 下的最大价值。这也说明为什么分数背包可以贪心——如果可以只拿 A 的一部分就不会出现占着容量拿不出价值的情况。四、实战完整可编译对照程序下面这个程序把区间调度的贪心解和一个暴力枚举解放在一起对拍。暴力解枚举所有子集n取小值例如 12就能跑完2^12 4096种组合足够暴露贪心规则的错误。// 文件greedy_vs_bruteforce.cpp // 编译g -stdc17 -O2 -Wall -Wextra greedy_vs_bruteforce.cpp -o greedy_vs_bruteforce #include algorithm #include cstddef #include iostream #include random #include utility #include vector namespace { std::size_t greedyMaxNonOverlapping(std::vectorstd::pairint, int intervals) { if (intervals.empty()) return 0; std::sort(intervals.begin(), intervals.end(), [](const std::pairint, int a, const std::pairint, int b) { return a.second b.second; }); std::size_t count 1; int lastEnd intervals[0].second; for (std::size_t i 1; i intervals.size(); i) { if (intervals[i].first lastEnd) { count; lastEnd intervals[i].second; } } return count; } // 暴力枚举所有子集检查是否两两不重叠 std::size_t bruteMaxNonOverlapping(const std::vectorstd::pairint, int v) { const std::size_t n v.size(); std::size_t best 0; for (std::size_t mask 0; mask (std::size_t{1} n); mask) { bool ok true; std::size_t cnt 0; for (std::size_t i 0; i n ok; i) { if (((mask i) 1U) 0U) continue; cnt; for (std::size_t j i 1; j n; j) { if (((mask j) 1U) 0U) continue; // 有交集就作废 if (v[i].first v[j].second v[j].first v[i].second) { ok false; break; } } } if (ok) best std::max(best, cnt); } return best; } } // namespace int main() { std::mt19937 rng(12345); std::uniform_int_distributionint pos(0, 20); std::uniform_int_distributionint len(1, 5); for (int round 0; round 200; round) { const std::size_t n 10; std::vectorstd::pairint, int v; for (std::size_t i 0; i n; i) { const int s pos(rng); v.emplace_back(s, s len(rng)); } const std::size_t g greedyMaxNonOverlapping(v); const std::size_t b bruteMaxNonOverlapping(v); if (g ! b) { std::cout MISMATCH: greedy g brute b \n; return 1; } } std::cout all random cases agree\n; return 0; }这个对拍框架能直接复用到其他贪心问题上把贪心函数和暴力函数换成你要验证的那一对随机生成小规模输入跑几百轮。比起盯着代码苦思冥想对拍可靠得多。常见坑点区间调度按开始时间排序❌return a.first b.first;—— 会优先选到开始早、拖得长的区间把后面大量区间挤掉。✅ 按结束时间a.second b.second排序。比较器不满足严格弱序❌return a.second b.second;——不是严格弱序传给std::sort是UB未定义行为标准不保证任何行为。✅ 一律用。相等时返回false。贪心解的初始化边界处理错误❌std::size_t count 0;然后直接进入从下标 1 开始的循环 —— 第一个区间没被计入答案少 1。✅ 区间非空时count初始为 1lastEnd取排序后第一个区间的结束时间空输入单独返回 0。浮点比较器直接比较除法结果❌return a.value / a.weight b.value / b.weight;—— 有精度误差且weight为 0 时除零。✅ 用交叉相乘a.value * b.weight b.value * a.weight。std::priority_queue想改键值直接改❌ 拿到堆内元素引用改它的权值 —— 堆序被破坏后续top()不再正确。✅ 霍夫曼这类算法里只push新节点、pop旧节点不要原地修改。找零问题忽略无法凑出的情况❌int used amount / c;循环结束后不管剩余金额直接返回used—— 剩余金额不为 0 时答案无意义。✅ 循环后判断amount 0否则返回失败标记如-1。排序键相同导致结果不稳定❌ 依赖std::sort在键相等时保持原顺序它不保证稳定于是同样输入换台机器结果不同。✅ 需要稳定语义时用std::stable_sort或让比较器在键相等时再比较第二个字段保证全序。总结问题贪心是否适用贪心策略备注区间调度适用按结束时间升序能选就选交换论证可证分数背包适用按单位价值降序可切分靠可切分这个性质0/1 背包不适用无反例容量 10(6,30) (5,20) (5,20)贪心得 30、最优 40找零规范硬币系统适用每次取不超剩余金额的最大面额面额{1,3,4}找 6 是反例找零任意面额不适用无用 DPdp[i] min(dp[i-c] 1)霍夫曼编码适用每次合并权值最小的两个有严格证明三句话总结贪心的门槛不在写代码而在证明贪心选择性质和最优子结构这两个前提证不出来就只能靠对拍或反例验证最实用的判据是元素能否按比例切分——能切分分数背包通常可贪心必须整体取舍0/1 背包通常不行无论你多确信贪心是对的都值得用对拍框架在小规模随机数据上跑一遍因为贪心写错时程序不会报错只会安静地给出一个偏小或偏大的答案。