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

C语言实现贪心算法

news 2025/5/18 9:11:53

一、贪心算法核心思想

特征：在每一步选择中都采取当前状态下最优（局部最优）的选择，从而希望导致全局最优解
适用场景：需要满足贪心选择性质和最优子结构性质

二、经典贪心算法示例

1. 活动选择问题

目标：在给定时间段内安排最多的互不冲突的活动
策略：每次选择结束时间最早的活动

#include <stdio.h>
#include <stdlib.h>// 活动结构体定义
typedef struct {int start;int end;
} Activity;// 比较函数：按结束时间升序排序
int compare(const void *a, const void *b) {Activity *actA = (Activity*)a;Activity *actB = (Activity*)b;return actA->end - actB->end;
}void activitySelection(Activity activities[], int n) {// 按结束时间排序qsort(activities, n, sizeof(Activity), compare);printf("选中活动序列:\n");int lastEnd = 0;for(int i=0; i<n; i++) {if(activities[i].start >= lastEnd) {printf("[%d-%d] ", activities[i].start, activities[i].end);lastEnd = activities[i].end;}}
}int main() {Activity acts[] = {{1,3}, {2,5}, {3,7}, {5,9}, {8,10}};int n = sizeof(acts)/sizeof(acts[0]);activitySelection(acts, n);  // 输出：[1-3] [3-7] [8-10]return 0;
}

2. 找零钱问题

目标：用最少的硬币数量组成指定金额（假设硬币系统为规范系统，如人民币）
策略：每次选择当前可用的最大面值硬币

#include <stdio.h>void coinChange(int coins[], int n, int amount) {printf("找零%d元的方案：\n", amount);for(int i=0; i<n; i++) {while(amount >= coins[i]) {printf("%d元 ", coins[i]);amount -= coins[i];}}if(amount > 0) printf("\n剩余%d元无法找零", amount);
}int main() {int coins[] = {100, 50, 20, 10, 5, 1}; // 降序排列int amount = 176;coinChange(coins, 6, amount);  // 输出：100元 50元 20元 5元 1元return 0;
}

3. 霍夫曼编码（核心部分）

目标：生成最优前缀编码，实现数据压缩
策略：每次合并频率最小的两个节点

#include <stdio.h>
#include <stdlib.h>
#define MAX_TREE_HT 100// 霍夫曼树节点
struct MinHeapNode {char data;unsigned freq;struct MinHeapNode *left, *right;
};// 最小堆结构
struct MinHeap {unsigned size;unsigned capacity;struct MinHeapNode** array;
};// 创建新节点
struct MinHeapNode* newNode(char data, unsigned freq) {struct MinHeapNode* temp = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode));temp->left = temp->right = NULL;temp->data = data;temp->freq = freq;return temp;
}// 核心构建函数（完整实现需要约150行代码，此处展示核心逻辑）
void buildHuffmanTree(char data[], int freq[], int size) {// 1. 创建最小堆并初始化// 2. 循环执行以下操作直到堆中只剩一个节点：//    a. 提取两个最小频率节点//    b. 创建新内部节点，频率为两者之和//    c. 将新节点插入堆// 3. 剩余节点即为霍夫曼树的根
}

三、贪心算法特性对比

问题类型	适用性	时间复杂度	空间复杂度	是否需要排序
活动选择问题	✅	O(n log n)	O(1)	需要
找零问题	✅	O(n)	O(1)	需要
单源最短路径	✅	O(V²)	O(V)	不需要
背包问题（分数）	✅	O(n log n)	O(1)	需要