企业官网建设流程全解析

前言

贪心算法（greedy algorithm）是"每一步都选当前看起来最好的那个"的算法范式。它的代码往往只有十几行，比动态规划（dynamic programming，DP）短得多，但正确性门槛比 DP 高得多：DP 只要状态和转移写对就必然正确，而贪心必须证明"局部最优能推出全局最优"，证不出来就不能用。

最常见的三个误解是：

1. 
   
2. 以为"局部最优"是显然的。于是随手按某个规则排序，跑出结果就交差了。经典反例：用贪心解 0/1 背包问题会得到错误答案（本文第三节给出具体算例）。
3. 
   
4. 以为贪心是 DP 的简化版，随时可以互相替换。事实上它们是两种不同的正确性模型。有些问题（比如区间调度）贪心可解而 DP 反而麻烦；有些问题（比如 0/1 背包）DP 可解而贪心根本不成立。
5. 
   
6. 以为"排序后用贪心"就是贪心算法。排序常常是贪心的预处理步骤，但排序键选错，整个算法就错了——而且错得很难发现，因为程序不会报错，只是结果偏小或偏大。
7. 
   
   

本文讲三件事：贪心成立的两个必要条件、两种证明思路（交换论证与归纳）、以及四个经典问题的完整可编译实现与一个明确的反例。代码基于 C++17，可在 GCC 13 / Clang 17 / MSVC 19.3x 上编译。

一、贪心成立的两个前提

贪心算法要正确，必须同时满足两个性质：

这两个性质不是"看起来像"就成立的，必须证明。反例是检验的最好工具：能构造出一个"贪心结果 ≠ 最优解"的输入，就能立刻否掉贪心。

一个重要的判据：如果问题要求"每个元素只能整体选或不选"，贪心通常不成立；如果元素可以按比例切分，贪心常常成立。分数背包（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::vector<std::pair<int, int>> intervals) { if (intervals.empty()) return 0; std::sort(intervals.begin(), intervals.end(), [](const std::pair<int, int>& a, const std::pair<int, 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::vector<std::pair<int, 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::vector<Item> 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::vector<Item> 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::vector<int>& coins, int amount) { std::vector<int> sorted = coins; std::sort(sorted.begin(), sorted.end(), std::greater<int>()); 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; }

换面额就不是贪心能解决的问题了，得用 DP：dp[i] = min(dp[i - coin] + 1)。这个例子最能说明"贪心不是通用技巧，它依赖问题的具体性质"。

3.4 霍夫曼编码 —— 每次合并最小的两个

问题：给一组带权字符，构造前缀编码使总编码长度最短。

贪心策略：每次取出权值最小的两个节点合并成一个新节点，新节点权值为两者之和，放回集合，重复直到只剩一个节点。用std::priority_queue做最小堆是最自然的实现。

#include <functional> #include <iostream> #include <queue> #include <vector> // 返回合并的总代价，也就是编码后的总位数 long long huffmanCost(std::vector<long long> weights) { std::priority_queue<long long, std::vector<long long>, std::greater<long long>> pq( std::greater<long 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::vector<long long> w{5, 9, 12, 13, 16, 45}; std::cout << huffmanCost(w) << '\n'; // 224 return 0; }

霍夫曼算法的正确性有严格证明（交换论证 + 归纳，属于"贪心选择性质"的标准案例），这也是它被视为贪心算法典范的原因。

3.5 反例：0/1 背包不能用贪心

问题：物品不能切分，每件要么完整拿走，要么不拿。

反例：背包容量10，三件物品：

• 
  
• 按"单位价值"贪心：先拿 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++ -std=c++17 -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::vector<std::pair<int, int>> intervals) { if (intervals.empty()) return 0; std::sort(intervals.begin(), intervals.end(), [](const std::pair<int, int>& a, const std::pair<int, 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::vector<std::pair<int, 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_distribution<int> pos(0, 20); std::uniform_int_distribution<int> len(1, 5); for (int round = 0; round < 200; ++round) { const std::size_t n = 10; std::vector<std::pair<int, 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; }

这个"对拍"框架能直接复用到其他贪心问题上：把贪心函数和暴力函数换成你要验证的那一对，随机生成小规模输入，跑几百轮。比起盯着代码苦思冥想，对拍可靠得多。

常见坑点

1. 
   
2. 区间调度按开始时间排序
3. 
   
   

❌return a.first < b.first;—— 会优先选到"开始早、拖得长"的区间，把后面大量区间挤掉。

✅ 按结束时间a.second < b.second排序。

1. 
   
2. 比较器不满足严格弱序
3. 
   
   

❌return a.second <= b.second;——<=不是严格弱序，传给std::sort是UB（未定义行为），标准不保证任何行为。

✅ 一律用<。相等时返回false。

1. 
   
2. 贪心解的初始化边界处理错误
3. 
   
   

❌std::size_t count = 0;然后直接进入从下标 1 开始的循环 —— 第一个区间没被计入，答案少 1。

✅ 区间非空时count初始为 1，lastEnd取排序后第一个区间的结束时间；空输入单独返回 0。

1. 
   
2. 浮点比较器直接比较除法结果
3. 
   
   

❌return a.value / a.weight > b.value / b.weight;—— 有精度误差，且weight为 0 时除零。

✅ 用交叉相乘a.value * b.weight > b.value * a.weight。

1. 
   
2. std::priority_queue想改键值直接改
3. 
   
   

❌ 拿到堆内元素引用改它的权值 —— 堆序被破坏，后续top()不再正确。

✅ 霍夫曼这类算法里，只push新节点、pop旧节点，不要原地修改。

1. 
   
2. 找零问题忽略"无法凑出"的情况
3. 
   
   

❌int used = amount / c;循环结束后不管剩余金额，直接返回used—— 剩余金额不为 0 时答案无意义。

✅ 循环后判断amount == 0，否则返回失败标记（如-1）。

1. 
   
2. 排序键相同导致结果不稳定
3. 
   
   

❌ 依赖std::sort在键相等时保持原顺序（它不保证稳定），于是同样输入换台机器结果不同。

✅ 需要稳定语义时用std::stable_sort，或让比较器在键相等时再比较第二个字段，保证全序。

总结

三句话总结：贪心的门槛不在写代码，而在证明"贪心选择性质"和"最优子结构"这两个前提，证不出来就只能靠对拍或反例验证；最实用的判据是"元素能否按比例切分"——能切分（分数背包）通常可贪心，必须整体取舍（0/1 背包）通常不行；无论你多确信贪心是对的，都值得用对拍框架在小规模随机数据上跑一遍，因为贪心写错时程序不会报错，只会安静地给出一个偏小或偏大的答案。