C++中的贪心算法及其实现

贪心算法是一种常用的算法思想，在许多问题中都有着广泛的应用。其核心思想是在做出每一步的决策时，只考虑眼前最优解，而不考虑长远的影响。

在C++中，贪心算法的实现经常会涉及到排序、数据处理等基本操作。下面，我们将针对几个典型的问题，介绍贪心算法的思路及其在C++中的实现。

1.活动安排问题

给定一组活动，每个活动有其开始时间和结束时间，同时一个人一次只能参加一个活动。问如何安排活动才能保证这个人参加的活动数量最多。

贪心算法的思路是先按照每个活动的结束时间升序排序，然后从第一个活动开始，选择结束时间最早的活动作为第一个参加的活动。接着，从余下活动中选择结束时间最早的可与当前活动兼容的活动，并将其作为下一个参加的活动。重复该过程，直到所有活动都被安排完为止。

以下是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 = lastEnd) { cnt++; lastEnd = arr[i].end; } } return cnt; }登录后复制

给定一组权值，要求将它们编码为不等长的二进制字符串，使得所有权值相加的编码长度最小。

贪心算法的思路是先将权值升序排序，在每一步中选择权值最小的两个节点组合成一个新节点，并将其权值定义为这两个节点的权值之和。重复该过程，直至所有节点都被组合成一个根节点。这个根节点所对应的二叉树即为哈夫曼树。在遍历哈夫曼树时，向左走表示添加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 = coins[i]) { cnt += amount / coins[i]; amount -= coins[i] * (amount / coins[i]); } } return cnt; }登录后复制

以上就是C++中的贪心算法及其实现的详细内容，更多请关注每日运维网(www.mryunwei.com)其它相关文章！