贪心算法详解及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;
}