当前位置：首页 > news >正文

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

news 2026/4/27 8:30:46

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 优化结果 */ template<typename T> vector<T> greedyAlgorithm( vector<T>& elements, bool (*comparator)(const T&, const T&), bool (*canSelect)(const T&, const vector<T>&) ) { vector<T> 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 vector<int>& 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: vector<Activity> selectMaxActivities(vector<Activity>& activities) { // 1. 按结束时间升序排序 sort(activities.begin(), activities.end(), [](const Activity& a, const Activity& b) { return a.finish < b.finish; }); vector<Activity> 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; vector<Activity> activities = { {1, 1, 3}, {2, 2, 5}, {3, 4, 6}, {4, 5, 7}, {5, 8, 9}, {6, 5, 9} }; ActivitySelector selector; vector<Activity> 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_map<char, 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_map<char, int>& frequencies) { // 创建最小堆 priority_queue<HuffmanNode*, vector<HuffmanNode*>, 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_map<char, 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_map<char, 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, vector<int>& coins) { sort(coins.begin(), coins.end(), greater<int>()); 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, vector<int>& coins) { vector<int> 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(vector<int>& 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; vector<int> 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; vector<int> 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：选择最多不重叠区间 * 策略：按结束时间排序，选择结束最早的 */ vector<Interval> maxNonOverlappingIntervals(vector<Interval>& intervals) { // 按结束时间升序排序 sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) { return a.end < b.end; }); vector<Interval> result; int lastEnd = INT_MIN; for (const auto& interval : intervals) { if (interval.start >= lastEnd) { result.push_back(interval); lastEnd = interval.end; } } return result; } /** * 问题2：用最少的点覆盖所有区间 * 策略：每次选择当前区间集合的结束最早点 */ vector<int> minPointsToCoverIntervals(vector<Interval>& intervals) { if (intervals.empty()) return {}; // 按开始时间升序排序 sort(intervals.begin(), intervals.end(), [](const Interval& a, const Interval& b) { return a.start < b.start; }); vector<int> 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; // 测试数据 vector<Interval> intervals = { {1, 3, 1}, {2, 5, 2}, {4, 6, 3}, {7, 9, 4}, {8, 10, 5} }; // 问题1：最多不重叠区间 cout << "\n问题1：选择最多不重叠区间" << endl; vector<Interval> result1 = scheduler.maxNonOverlappingIntervals(intervals); cout << "选择的区间：" << endl; for (const auto& interval : result1) { cout << "区间" << interval.id << ": [" << interval.start << ", " << interval.end << "]" << endl; } // 问题2：最少点覆盖 cout << "\n问题2：用最少的点覆盖所有区间" << endl; vector<int> 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, vector<Item>& 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, vector<Item>& items) { int n = items.size(); vector<vector<int>> dp(n + 1, vector<int>(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; vector<Item> 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. 基础：n=1时贪心算法正确 * 2. 归纳：假设对n-1成立 * 3. 步骤：证明对n也成立 */

6. 贪心算法的局限性

void demonstrateLimitations() { cout << "=== 贪心算法的局限性 ===" << endl; // 1. 不总是得到最优解 cout << "1. 不总是得到全局最优解：" << endl; cout << " 如硬币系统[1,3,4]凑6元" << endl; cout << " 贪心：4+1+1=3枚，最优：3+3=2枚" << 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(vector<int>& 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(vector<int>& gas, vector<int>& 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; }