贪心算法（Greedy Algorithm）详解：从理论到C++实践

目录1. 什么是贪心算法2. 贪心算法的适用条件3. 贪心算法的通用模板4. 经典贪心算法问题详解4.1 活动选择问题4.2 哈夫曼编码4.3 零钱兑换问题4.4 区间调度问题4.5 背包问题分数背包5. 贪心算法的证明技术6. 贪心算法的局限性7. 实际应用场景8. 总结与练习1. 什么是贪心算法贪心算法Greedy Algorithm是一种在每一步选择中都采取当前状态下最优的选择从而希望导致结果是全局最优的算法策略。它就像一个只看眼前的决策者每次只考虑当前最优不考虑长远影响。贪心算法的核心特点局部最优每次选择都是当前看起来最好的不可回溯一旦做出选择就不再改变高效通常时间复杂度较低不一定最优不能保证总是得到全局最优解2. 贪心算法的适用条件贪心算法要能产生全局最优解必须满足以下两个性质2.1 贪心选择性质局部最优选择能导致全局最优解。即可以通过一系列局部最优选择构建全局最优解。2.2 最优子结构问题的最优解包含其子问题的最优解。验证方法bool canUseGreedy(Problem problem) { // 检查问题是否满足 // 1. 局部最优能导致全局最优 // 2. 具有最优子结构 return checkGreedyChoice() checkOptimalSubstructure(); }3. 贪心算法的通用模板#include iostream #include vector #include algorithm using namespace std; /** * 贪心算法通用模板 * * param elements 待处理元素集合 * param comparator 比较函数定义最优的标准 * param canSelect 判断函数检查元素是否能加入当前解 * return 优化结果 */ templatetypename T vectorT greedyAlgorithm( vectorT elements, bool (*comparator)(const T, const T), bool (*canSelect)(const T, const vectorT) ) { vectorT result; // 步骤1按贪心策略排序 sort(elements.begin(), elements.end(), comparator); // 步骤2遍历并做出贪心选择 for (const T element : elements) { if (canSelect(element, result)) { result.push_back(element); } } return result; } // 示例比较函数 bool compareByValue(const int a, const int b) { return a b; // 降序排列值大的优先 } // 示例选择判断函数 bool canAddToResult(const int element, const vectorint result) { // 这里可以根据具体问题定义条件 return true; }4. 经典贪心算法问题详解4.1 活动选择问题问题描述有n个活动每个活动有开始时间和结束时间。选择尽可能多的互不冲突的活动。#include iostream #include vector #include algorithm using namespace std; // 活动结构体 struct Activity { int id; int start; int finish; Activity(int i, int s, int f) : id(i), start(s), finish(f) {} }; /** * 活动选择问题 - 贪心算法 * 策略每次选择结束时间最早且不与已选活动冲突的活动 * 时间复杂度O(n log n) */ class ActivitySelector { public: vectorActivity selectMaxActivities(vectorActivity activities) { // 1. 按结束时间升序排序 sort(activities.begin(), activities.end(), [](const Activity a, const Activity b) { return a.finish b.finish; }); vectorActivity selected; int lastFinishTime 0; // 2. 贪心选择 for (const auto activity : activities) { if (activity.start lastFinishTime) { selected.push_back(activity); lastFinishTime activity.finish; } } return selected; } }; // 测试函数 void testActivitySelection() { cout 活动选择问题测试 endl; vectorActivity activities { {1, 1, 3}, {2, 2, 5}, {3, 4, 6}, {4, 5, 7}, {5, 8, 9}, {6, 5, 9} }; ActivitySelector selector; vectorActivity result selector.selectMaxActivities(activities); cout 选择的活动按结束时间排序 endl; for (const auto act : result) { cout 活动 act.id : [ act.start , act.finish ] endl; } cout 总共选择了 result.size() 个活动 endl; cout endl; }算法分析排序O(n log n)选择O(n)总复杂度O(n log n)正确性证明通过交换论证法可以证明结束时间最早的活动一定在某个最优解中4.2 哈夫曼编码问题描述构建最优前缀编码使编码后的总长度最短。#include iostream #include queue #include vector #include unordered_map #include string using namespace std; // 哈夫曼树节点 struct HuffmanNode { char ch; // 字符 int freq; // 频率 HuffmanNode* left; HuffmanNode* right; HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {} // 判断是否为叶子节点 bool isLeaf() const { return left nullptr right nullptr; } }; // 比较函数用于最小堆 struct CompareNode { bool operator()(HuffmanNode* a, HuffmanNode* b) { return a-freq b-freq; // 最小堆 } }; class HuffmanCoding { private: HuffmanNode* root; unordered_mapchar, string huffmanCodes; // 递归生成编码 void generateCodes(HuffmanNode* node, string code) { if (node nullptr) return; if (node-isLeaf()) { huffmanCodes[node-ch] code; } else { generateCodes(node-left, code 0); generateCodes(node-right, code 1); } } // 清理内存 void clearTree(HuffmanNode* node) { if (node nullptr) return; clearTree(node-left); clearTree(node-right); delete node; } public: HuffmanCoding() : root(nullptr) {} ~HuffmanCoding() { clearTree(root); } /** * 构建哈夫曼树 * 贪心策略每次合并频率最小的两个节点 */ void buildTree(const unordered_mapchar, int frequencies) { // 创建最小堆 priority_queueHuffmanNode*, vectorHuffmanNode*, CompareNode minHeap; // 1. 创建叶子节点 for (const auto pair : frequencies) { minHeap.push(new HuffmanNode(pair.first, pair.second)); } // 2. 贪心合并 while (minHeap.size() 1) { // 取出两个频率最小的节点 HuffmanNode* left minHeap.top(); minHeap.pop(); HuffmanNode* right minHeap.top(); minHeap.pop(); // 创建新节点 HuffmanNode* parent new HuffmanNode(#, left-freq right-freq); parent-left left; parent-right right; // 放回堆中 minHeap.push(parent); } // 3. 设置根节点 if (!minHeap.empty()) { root minHeap.top(); } // 4. 生成编码 if (root ! nullptr) { if (root-isLeaf()) { huffmanCodes[root-ch] 0; // 只有一个字符的特殊情况 } else { generateCodes(root, ); } } } // 编码文本 string encode(const string text) { string encoded ; for (char ch : text) { if (huffmanCodes.find(ch) ! huffmanCodes.end()) { encoded huffmanCodes[ch]; } else { cerr 错误字符 ch 不在编码表中 endl; } } return encoded; } // 解码 string decode(const string encoded) { string decoded ; HuffmanNode* current root; for (char bit : encoded) { if (bit 0) { current current-left; } else { current current-right; } if (current-isLeaf()) { decoded current-ch; current root; } } return decoded; } // 获取编码表 const unordered_mapchar, string getCodes() const { return huffmanCodes; } // 计算压缩率 double calculateCompressionRate(const string original) { int originalBits original.length() * 8; // 假设原始是ASCII int compressedBits encode(original).length(); return 1.0 - (double)compressedBits / originalBits; } }; void testHuffmanCoding() { cout 哈夫曼编码测试 endl; // 字符频率统计 unordered_mapchar, int frequencies { {a, 5}, {b, 9}, {c, 12}, {d, 13}, {e, 16}, {f, 45} }; HuffmanCoding huffman; huffman.buildTree(frequencies); // 输出编码表 cout 哈夫曼编码表 endl; for (const auto pair : huffman.getCodes()) { cout pair.first : pair.second endl; } // 测试编码解码 string text abcdef; string encoded huffman.encode(text); string decoded huffman.decode(encoded); cout \n原始文本: text endl; cout 编码结果: encoded endl; cout 解码结果: decoded endl; double compressionRate huffman.calculateCompressionRate(text); cout 压缩率: compressionRate * 100 % endl; cout endl; }算法分析构建最小堆O(n)合并操作每次O(log n)共n-1次 → O(n log n)总复杂度O(n log n)正确性证明通过Huffman算法的贪心选择性质证明4.3 零钱兑换问题#include iostream #include vector #include algorithm using namespace std; /** * 零钱兑换 - 贪心算法 * 注意贪心算法只适用于特定面值系统如标准人民币 * 对于任意面值系统需要使用动态规划 */ class CoinChange { public: /** * 贪心算法实现 * 策略每次选择面值最大的硬币 * param amount 目标金额 * param coins 硬币面值数组已按降序排序 * return 使用的硬币数量-1表示无法兑换 */ int greedyChange(int amount, vectorint coins) { sort(coins.begin(), coins.end(), greaterint()); int count 0; int remaining amount; for (int coin : coins) { if (coin remaining) { int numCoins remaining / coin; count numCoins; remaining - numCoins * coin; } if (remaining 0) break; } return remaining 0 ? count : -1; } /** * 动态规划实现用于对比 * 适用于所有面值系统 */ int dpChange(int amount, vectorint coins) { vectorint dp(amount 1, amount 1); dp[0] 0; for (int i 1; i amount; i) { for (int coin : coins) { if (coin i) { dp[i] min(dp[i], dp[i - coin] 1); } } } return dp[amount] amount ? -1 : dp[amount]; } /** * 检查硬币系统是否满足贪心性质 * 贪心性质对于任意金额贪心算法都能得到最优解 */ bool canUseGreedy(vectorint coins) { sort(coins.begin(), coins.end()); int n coins.size(); for (int i 0; i n; i) { for (int j i 1; j n; j) { // 检查是否有反例 int amount coins[j] - 1; int greedyResult greedyChange(amount, coins); int dpResult dpChange(amount, coins); if (greedyResult ! dpResult greedyResult ! -1) { return false; } } } return true; } }; void testCoinChange() { cout 零钱兑换问题测试 endl; CoinChange changer; // 测试1标准人民币面值满足贪心性质 cout \n测试1标准人民币面值 endl; vectorint rmbCoins {100, 50, 20, 10, 5, 1}; int amount1 186; int greedyResult1 changer.greedyChange(amount1, rmbCoins); int dpResult1 changer.dpChange(amount1, rmbCoins); cout 金额: amount1 元 endl; cout 贪心算法结果: greedyResult1 枚硬币 endl; cout 动态规划结果: dpResult1 枚硬币 endl; cout 是否满足贪心性质: (changer.canUseGreedy(rmbCoins) ? 是 : 否) endl; // 测试2不满足贪心性质的面值 cout \n测试2不满足贪心性质的面值 [1, 3, 4] endl; vectorint badCoins {1, 3, 4}; int amount2 6; int greedyResult2 changer.greedyChange(amount2, badCoins); int dpResult2 changer.dpChange(amount2, badCoins); cout 金额: amount2 endl; cout 贪心算法结果: greedyResult2 枚硬币 endl; cout 动态规划结果: dpResult2 枚硬币 endl; cout 是否满足贪心性质: (changer.canUseGreedy(badCoins) ? 是 : 否) endl; cout 分析贪心得到 [4,1,1] 需要3枚但最优是 [3,3] 只需要2枚 endl; cout endl; }4.4 区间调度问题#include iostream #include vector #include algorithm using namespace std; struct Interval { int start; int end; int id; Interval(int s, int e, int i) : start(s), end(e), id(i) {} }; class IntervalScheduling { public: /** * 问题1选择最多不重叠区间 * 策略按结束时间排序选择结束最早的 */ vectorInterval maxNonOverlappingIntervals(vectorInterval intervals) { // 按结束时间升序排序 sort(intervals.begin(), intervals.end(), [](const Interval a, const Interval b) { return a.end b.end; }); vectorInterval result; int lastEnd INT_MIN; for (const auto interval : intervals) { if (interval.start lastEnd) { result.push_back(interval); lastEnd interval.end; } } return result; } /** * 问题2用最少的点覆盖所有区间 * 策略每次选择当前区间集合的结束最早点 */ vectorint minPointsToCoverIntervals(vectorInterval intervals) { if (intervals.empty()) return {}; // 按开始时间升序排序 sort(intervals.begin(), intervals.end(), [](const Interval a, const Interval b) { return a.start b.start; }); vectorint points; int currentPoint intervals[0].end; for (int i 1; i intervals.size(); i) { if (intervals[i].start currentPoint) { points.push_back(currentPoint); currentPoint intervals[i].end; } else { currentPoint min(currentPoint, intervals[i].end); } } points.push_back(currentPoint); return points; } }; void testIntervalScheduling() { cout 区间调度问题测试 endl; IntervalScheduling scheduler; // 测试数据 vectorInterval intervals { {1, 3, 1}, {2, 5, 2}, {4, 6, 3}, {7, 9, 4}, {8, 10, 5} }; // 问题1最多不重叠区间 cout \n问题1选择最多不重叠区间 endl; vectorInterval result1 scheduler.maxNonOverlappingIntervals(intervals); cout 选择的区间 endl; for (const auto interval : result1) { cout 区间 interval.id : [ interval.start , interval.end ] endl; } // 问题2最少点覆盖 cout \n问题2用最少的点覆盖所有区间 endl; vectorint points scheduler.minPointsToCoverIntervals(intervals); cout 需要的点; for (int point : points) { cout point ; } cout endl; cout endl; }4.5 背包问题分数背包#include iostream #include vector #include algorithm using namespace std; struct Item { int value; int weight; int id; Item(int v, int w, int i) : value(v), weight(w), id(i) {} // 计算价值密度 double valuePerWeight() const { return (double)value / weight; } }; class FractionalKnapsack { public: /** * 分数背包问题 - 贪心算法 * 策略按价值密度value/weight降序排序 * 时间复杂度O(n log n) */ double getMaxValue(int capacity, vectorItem items) { // 按价值密度降序排序 sort(items.begin(), items.end(), [](const Item a, const Item b) { return a.valuePerWeight() b.valuePerWeight(); }); double totalValue 0.0; int remainingCapacity capacity; for (const auto item : items) { if (remainingCapacity 0) break; if (item.weight remainingCapacity) { // 可以放整个物品 totalValue item.value; remainingCapacity - item.weight; } else { // 只能放部分物品 double fraction (double)remainingCapacity / item.weight; totalValue item.value * fraction; remainingCapacity 0; } } return totalValue; } // 0-1背包问题用于对比 int zeroOneKnapsack(int capacity, vectorItem items) { int n items.size(); vectorvectorint dp(n 1, vectorint(capacity 1, 0)); for (int i 1; i n; i) { for (int w 1; w capacity; w) { if (items[i-1].weight w) { dp[i][w] max(dp[i-1][w], dp[i-1][w - items[i-1].weight] items[i-1].value); } else { dp[i][w] dp[i-1][w]; } } } return dp[n][capacity]; } }; void testKnapsack() { cout 背包问题测试 endl; FractionalKnapsack knapsack; vectorItem items { {60, 10, 1}, // 价值60重量10 {100, 20, 2}, // 价值100重量20 {120, 30, 3} // 价值120重量30 }; int capacity 50; // 分数背包 double fractionalValue knapsack.getMaxValue(capacity, items); cout 分数背包最大价值: fractionalValue endl; // 0-1背包 int zeroOneValue knapsack.zeroOneKnapsack(capacity, items); cout 0-1背包最大价值: zeroOneValue endl; cout \n分析 endl; cout 分数背包可以取物品的一部分所以价值更高 endl; cout 0-1背包只能整个取或不取 endl; cout endl; }5. 贪心算法的证明技术5.1 交换论证法通过证明贪心选择不会比最优解差。/** * 交换论证示例活动选择问题 * 证明假设存在最优解A贪心解G * 1. 找到第一个不同的选择 * 2. 用贪心选择替换最优解中的对应选择 * 3. 证明替换后仍然是可行解 * 4. 重复直到与贪心解相同 */5.2 归纳法证明/** * 归纳法证明步骤 * 1. 基础n1时贪心算法正确 * 2. 归纳假设对n-1成立 * 3. 步骤证明对n也成立 */6. 贪心算法的局限性void demonstrateLimitations() { cout 贪心算法的局限性 endl; // 1. 不总是得到最优解 cout 1. 不总是得到全局最优解 endl; cout 如硬币系统[1,3,4]凑6元 endl; cout 贪心4113枚最优332枚 endl; // 2. 依赖问题特性 cout \n2. 需要问题满足贪心选择性质 endl; cout 必须验证问题是否适合贪心 endl; // 3. 无后效性 cout \n3. 无法回溯 endl; cout 一旦做出选择就不能改变 endl; }7. 实际应用场景应用领域具体问题贪心策略数据压缩哈夫曼编码频率最小的先合并网络路由最短路径(Dijkstra)当前最短路径优先任务调度区间调度结束时间最早优先资源分配分数背包价值密度最高优先图论最小生成树(Prim/Kruskal)最小边优先8. 总结与练习8.1 贪心算法选择步骤分析问题是否满足贪心性质设计合适的贪心策略证明贪心策略的正确性实现并测试8.2 练习题// 练习题1跳跃游戏 bool canJump(vectorint nums) { int maxReach 0; for (int i 0; i nums.size(); i) { if (i maxReach) return false; maxReach max(maxReach, i nums[i]); } return true; } // 练习题2加油站问题 int canCompleteCircuit(vectorint gas, vectorint cost) { int total 0, current 0, start 0; for (int i 0; i gas.size(); i) { total gas[i] - cost[i]; current gas[i] - cost[i]; if (current 0) { start i 1; current 0; } } return total 0 ? start : -1; }8.3 学习建议理解每个问题的贪心策略掌握证明方法多练习相关题目对比贪心与其他算法DP、回溯注意在实际应用中使用贪心算法前务必验证问题是否满足贪心选择性质。贪心算法虽然高效但不保证总是最优需要根据具体问题谨慎选择。本文代码已在GCC 9.0环境下测试通过建议使用C11及以上标准编译运行。