贪心算法是一种常用的算法思想，在许多问题中都有着广泛的应用。其核心思想是在做出每一步的决策时，只考虑眼前最优解，而不考虑长远的影响。
在C++中，贪心算法的实现经常会涉及到排序、数据处理等基本操作。下面，我们将针对几个典型的问题，介绍贪心算法的思路及其在C++中的实现。
1.活动安排问题
给定一组活动，每个活动有其开始时间和结束时间，同时一个人一次只能参加一个活动。问如何安排活动才能保证这个人参加的活动数量最多。
贪心算法的思路是先按照每个活动的结束时间升序排序，然后从第一个活动开始，选择结束时间最早的活动作为第一个参加的活动。接着，从余下活动中选择结束时间最早的可与当前活动兼容的活动，并将其作为下一个参加的活动。重复该过程，直到所有活动都被安排完为止。
立即学习“C++免费学习笔记（深入）”；
以下是C++代码实现：
struct activity {
int start;
int end;
}
bool cmp(activity a, activity b) {
return a.end < b.end;
}
int arrangeActivities(activity arr[], int n) {
sort(arr, arr + n, cmp);
int cnt = 1;
int lastEnd = arr[0].end;
for (int i = 1; i < n; i++) {
if (arr[i].start >= lastEnd) {
cnt++;
lastEnd = arr[i].end;
}
}
return cnt;
}2.哈夫曼编码问题
给定一组权值，要求将它们编码为不等长的二进制字符串，使得所有权值相加的编码长度最小。
C编写，实现字符串摘要、文件摘要两个功能。里面主要包含3个文件: Md5.cpp、Md5.h、Main.cpp。其中Md5.cpp是算法的代码，里的代码大多是从 rfc-1321 里copy过来的；Main.cpp是主程序。
贪心算法的思路是先将权值升序排序，在每一步中选择权值最小的两个节点组合成一个新节点，并将其权值定义为这两个节点的权值之和。重复该过程，直至所有节点都被组合成一个根节点。这个根节点所对应的二叉树即为哈夫曼树。在遍历哈夫曼树时，向左走表示添加0，向右走表示添加1，这样便可以实现对每个权值对应编码的求解。
以下是C++代码实现：
struct Node {
int weight;
int parent, leftChild, rightChild;
}
bool cmp(Node a, Node b) {
return a.weight < b.weight;
}
void buildHuffmanTree(Node arr[], int n) {
// 初始化所有节点
for (int i = 0; i < n; i++) {
arr[i].parent = -1;
arr[i].leftChild = -1;
arr[i].rightChild = -1;
}
// 构建哈夫曼树
for (int i = n; i < 2 * n - 1; i++) {
int minIndex1 = -1, minIndex2 = -1;
for (int j = 0; j < i; j++) {
if (arr[j].parent == -1) {
if (minIndex1 == -1) {
minIndex1 = j;
}
else if (minIndex2 == -1) {
minIndex2 = j;
}
else {
if (arr[j].weight < arr[minIndex1].weight) {
minIndex2 = minIndex1;
minIndex1 = j;
}
else if (arr[j].weight < arr[minIndex2].weight) {
minIndex2 = j;
}
}
}
}
arr[minIndex1].parent = i;
arr[minIndex2].parent = i;
arr[i].leftChild = minIndex1;
arr[i].rightChild = minIndex2;
arr[i].weight = arr[minIndex1].weight + arr[minIndex2].weight;
}
}
void findHuffmanCode(Node arr[], int n) {
// 从叶节点开始遍历哈夫曼树
for (int i = 0; i < n; i++) {
string code = "";
int currentNode = i;
while (arr[currentNode].parent != -1) {
int parent = arr[currentNode].parent;
if (arr[parent].leftChild == currentNode) {
code = "0" + code;
}
else {
code = "1" + code;
}
currentNode = parent;
}
cout << code << endl;
}
}3.求解硬币找零问题
给定一组硬币的面值，以及要找零的金额，问最少需要多少个硬币才能凑出该金额。
贪心算法的思路是先将硬币的面值降序排序，然后从面值最大的硬币开始，不断取用该硬币直至无法再选，接着使用面值次大的硬币，直至凑出所有金额。
以下是C++代码实现：
bool cmp(int a, int b) {
return a > b;
}
int minCoinNum(int coins[], int n, int amount) {
sort(coins, coins + n, cmp);
int cnt = 0;
for (int i = 0; i < n; i++) {
if (amount >= coins[i]) {
cnt += amount / coins[i];
amount -= coins[i] * (amount / coins[i]);
}
}
return cnt;
}在实际开发过程中，贪心算法往往不是最优解，但是其简单、高效的特点使其获得了广泛的应用。通过以上三个典型问题的介绍，相信读者可以更好地理解并掌握贪心算法思想及其在C++中的实现。
