贪心算法详解及C++实现
1. 什么是贪心算法
贪心算法(Greedy Algorithm)是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法策略。
贪心算法与动态规划不同在于它对每个子问题的解决方案都做出选择,不能回退。动态规划则会保存以前的运算结果,并根据以前的结果对当前进行选择,有回退功能。
2. 贪心算法的基本要素
贪心算法适用的问题通常具有以下两个性质:
- 贪心选择性质:所求问题的整体最优解可以通过一系列局部最优的选择来达到。
- 最优子结构:问题的最优解包含其子问题的最优解。
3. 贪心算法的基本步骤
- 建立数学模型来描述问题
- 把求解的问题分成若干个子问题
- 对每个子问题求解,得到子问题的局部最优解
- 把子问题的解合并成原问题的一个解
4. 经典贪心算法问题
4.1 找零钱问题
问题描述:假设有不同面额的硬币 coins = [1, 2, 5, 10, 20, 50, 100],我们需要用最少数量的硬币来找零 n 元。
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;vector<int> coinChange(int amount, vector<int>& coins) {sort(coins.rbegin(), coins.rend()); // 从大到小排序vector<int> result;for (int coin : coins) {while (amount >= coin) {amount -= coin;result.push_back(coin);}}if (amount != 0) {cout << "无法正好找零" << endl;return {};}return result;
}int main() {vector<int> coins = {1, 2, 5, 10, 20, 50, 100};int amount = 93;vector<int> result = coinChange(amount, coins);cout << "找零" << amount << "元需要的硬币为:";for (int coin : result) {cout << coin << " ";}cout << endl;return 0;
}
4.2 活动选择问题
问题描述:给定一组活动,每个活动都有一个开始时间和结束时间,选择最大的互不冲突的活动集合。
#include <iostream>
#include <vector>
#include <algorithm>using namespace std;struct Activity {int start;int end;
};bool compareActivity(Activity a, Activity b) {return a.end < b.end;
}vector<Activity> selectActivities(vector<Activity>& activities) {sort(activities.begin(), activities.end(), compareActivity);vector<Activity> selected;selected.push_back(activities[0]);int lastEnd = activities[0].end;for (int i = 1; i < activities.size(); i++) {if (activities[i].start >= lastEnd) {selected.push_back(activities[i]);lastEnd = activities[i].end;}}return selected;
}int main() {vector<Activity> activities = {{1, 4}, {3, 5}, {0, 6}, {5, 7},{3, 8}, {5, 9}, {6, 10}, {8, 11},{8, 12}, {2, 13}, {12, 14}};vector<Activity> result = selectActivities(activities);cout << "选择的活动序列为:" << endl;for (Activity act : result) {cout << "[" << act.start << ", " << act.end << "] ";}cout << endl;return 0;
}
4.3 霍夫曼编码
问题描述:霍夫曼编码是一种用于无损数据压缩的贪心算法,通过给出现频率高的字符较短的编码,出现频率低的字符较长的编码,来达到压缩数据的目的。
#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>using namespace std;struct HuffmanNode {char ch;int freq;HuffmanNode *left, *right;HuffmanNode(char c, int f) : ch(c), freq(f), left(nullptr), right(nullptr) {}
};struct compare {bool operator()(HuffmanNode* l, HuffmanNode* r) {return l->freq > r->freq;}
};void encode(HuffmanNode* root, string str, unordered_map<char, string> &huffmanCode) {if (root == nullptr) return;if (!root->left && !root->right) {huffmanCode[root->ch] = str;}encode(root->left, str + "0", huffmanCode);encode(root->right, str + "1", huffmanCode);
}void buildHuffmanTree(string text) {unordered_map<char, int> freq;for (char ch : text) {freq[ch]++;}priority_queue<HuffmanNode*, vector<HuffmanNode*>, compare> pq;for (auto pair : freq) {pq.push(new HuffmanNode(pair.first, pair.second));}while (pq.size() != 1) {HuffmanNode *left = pq.top(); pq.pop();HuffmanNode *right = pq.top(); pq.pop();int sum = left->freq + right->freq;HuffmanNode *node = new HuffmanNode('\0', sum);node->left = left;node->right = right;pq.push(node);}HuffmanNode* root = pq.top();unordered_map<char, string> huffmanCode;encode(root, "", huffmanCode);cout << "霍夫曼编码表:" << endl;for (auto pair : huffmanCode) {cout << pair.first << " : " << pair.second << endl;}string encodedStr;for (char ch : text) {encodedStr += huffmanCode[ch];}cout << "编码后的字符串:" << encodedStr << endl;
}int main() {string text = "hello world";cout << "原始字符串:" << text << endl;buildHuffmanTree(text);return 0;
}
5. 贪心算法的优缺点
优点:
- 简单易懂,容易实现
- 运行效率高,时间复杂度通常较低
- 可以作为其他算法的辅助算法
缺点:
- 不能保证得到全局最优解
- 适用范围有限,只有部分问题能用贪心算法解决
- 需要证明其正确性,有时证明较复杂
6. 贪心算法的应用场景
- 最小生成树(Prim和Kruskal算法)
- 最短路径问题(Dijkstra算法)
- 数据压缩(霍夫曼编码)
- 任务调度问题
- 集合覆盖问题
7. 总结
贪心算法是一种简单而有效的算法设计技术,适用于具有贪心选择性质和最优子结构的问题。虽然它不能解决所有优化问题,但在适用的情况下,它通常能提供高效且简单的解决方案。理解贪心算法的原理和应用场景,对于算法学习和问题解决能力的提升都有很大帮助。
在实际应用中,我们需要仔细分析问题是否适合使用贪心算法,并验证其正确性。当贪心算法不能得到全局最优解时,可能需要考虑动态规划等其他方法。