【数据结构与算法】第48篇：算法思想（三）：贪心算法

目录一、什么是贪心算法1.1 贪心策略1.2 贪心 vs 动态规划二、经典问题一活动选择问题2.1 问题描述2.2 贪心证明思路2.3 代码实现2.4 复杂度分析三、经典问题二找零问题3.1 问题描述3.2 贪心的局限性3.3 代码实现贪心四、贪心算法的正确性条件4.1 贪心选择性质4.2 最优子结构五、其他贪心算法经典问题六、贪心算法解题模板七、贪心 vs DP 选择指南八、小结九、思考题一、什么是贪心算法1.1 贪心策略贪心算法在每一步都选择当前状态下的最优解局部最优而不考虑未来的影响。特点实现简单通常很快不能保证对所有问题都得到全局最优解需要证明问题具有贪心选择性质1.2 贪心 vs 动态规划对比项贪心算法动态规划决策方式单次决策不回头考虑所有可能性子问题重叠不一定必然典型问题活动选择、找零背包、LCS时间复杂度通常 O(n) 或 O(n log n)通常 O(n²) 或更高全局最优保证需要证明总是保证二、经典问题一活动选择问题2.1 问题描述有 n 个活动每个活动有开始时间s[i]和结束时间f[i]。活动不能同时进行时间不能重叠。求最多能安排多少个活动。贪心策略每次选择结束时间最早且与已选活动不冲突的活动。2.2 贪心证明思路为什么选结束时间最早的是最优选结束时间最早的活动能为剩余活动留出最多的时间这个选择不会比任何最优解差2.3 代码实现c#include stdio.h #include stdlib.h // 活动结构体 typedef struct { int start; int finish; } Activity; // 按结束时间排序升序 int cmp(const void *a, const void *b) { return ((Activity*)a)-finish - ((Activity*)b)-finish; } // 贪心算法选择活动 int activitySelection(Activity activities[], int n) { if (n 0) return 0; // 1. 按结束时间排序 qsort(activities, n, sizeof(Activity), cmp); // 2. 贪心选择 int count 1; int lastFinish activities[0].finish; printf(选中的活动: (0, %d)\n, activities[0].finish); for (int i 1; i n; i) { if (activities[i].start lastFinish) { printf(选中的活动: (%d, %d)\n, activities[i].start, activities[i].finish); count; lastFinish activities[i].finish; } } return count; } int main() { Activity activities[] { {1, 4}, {3, 5}, {0, 6}, {5, 7}, {3, 9}, {5, 9}, {6, 10}, {8, 11}, {8, 12}, {2, 14}, {12, 16} }; int n sizeof(activities) / sizeof(activities[0]); int result activitySelection(activities, n); printf(最多可安排活动数: %d\n, result); return 0; }运行结果text选中的活动: (0, 4) 选中的活动: (5, 7) 选中的活动: (8, 11) 选中的活动: (12, 16) 最多可安排活动数: 42.4 复杂度分析排序O(n log n)贪心选择O(n)总时间复杂度O(n log n)三、经典问题二找零问题3.1 问题描述给定面额数组coins假设无限供应和金额amount求最少需要多少枚硬币。贪心策略每次用最大面额不超过剩余金额的硬币。3.2 贪心的局限性贪心算法不一定对所有硬币系统都正确。硬币系统金额贪心结果最优结果是否正确1,5,10,25标准30255 → 2枚101010 → 3枚✓1,3,46411 → 3枚33 → 2枚✗3.3 代码实现贪心c#include stdio.h #include stdlib.h // 按面额降序排序 int cmpDesc(const void *a, const void *b) { return *(int*)b - *(int*)a; } // 贪心找零 void greedyCoinChange(int coins[], int n, int amount) { qsort(coins, n, sizeof(int), cmpDesc); printf(贪心找零 %d 元: , amount); int remaining amount; for (int i 0; i n remaining 0; i) { if (remaining coins[i]) { int count remaining / coins[i]; printf(%d枚%d元 , count, coins[i]); remaining - count * coins[i]; } } if (remaining 0) { printf(无法找零); } printf(\n); } int main() { int coins1[] {1, 5, 10, 25}; int coins2[] {1, 3, 4}; greedyCoinChange(coins1, 4, 30); greedyCoinChange(coins2, 3, 6); return 0; }运行结果text贪心找零 30 元: 1枚25元 1枚5元 贪心找零 6 元: 1枚4元 2枚1元四、贪心算法的正确性条件4.1 贪心选择性质定义问题的全局最优解可以通过一系列局部最优选择贪心选择得到。证明方法假设有一个最优解证明可以将其改造为包含贪心选择的解用数学归纳法或反证法4.2 最优子结构定义问题的最优解包含子问题的最优解。活动选择问题满足最优子结构去掉贪心选择的活动后剩余子问题的最优解加上这个活动就是全局最优解。五、其他贪心算法经典问题问题贪心策略时间复杂度哈夫曼编码每次合并频率最小的两个节点O(n log n)最小生成树Prim/Kruskal每次选最小权边O(E log V)最短路径Dijkstra每次选距离最小的顶点O(V²) 或 O(E log V)区间覆盖每次选能覆盖最远右端点的区间O(n log n)任务调度最小化总完成时间按处理时间升序O(n log n)六、贪心算法解题模板c// 贪心算法通用框架 void greedy() { // 1. 按某种规则排序如果需要 sort(data); // 2. 初始化结果 result initial; // 3. 贪心选择 for (each element in sorted order) { if (符合条件) { 选择当前元素; 更新状态; } } }七、贪心 vs DP 选择指南问题特征推荐算法可以证明贪心选择性质贪心更高效需要考虑多种可能性DP子问题重叠明显DP只需局部最优决策贪心可分解为独立子问题分治或贪心判断方法尝试贪心策略看能否举出反例如果不能考虑DP如果DP太慢尝试证明贪心正确八、小结这一篇我们学习了贪心算法要点说明核心思想每次选当前最优希望达到全局最优活动选择选结束时间最早的复杂度 O(n log n)找零问题用最大面额优先但不一定正确正确性条件贪心选择性质 最优子结构适用范围图论MST、最短路、调度、哈夫曼编码贪心 vs DP贪心局部最优 → 全局最优需要证明DP考虑所有可能性 → 全局最优保证正确学习建议多练习判断问题是否适合贪心学会举反例推翻错误贪心策略掌握常见贪心问题活动选择、哈夫曼、区间覆盖下一篇我们讲代码调试技巧与常见内存错误排查。九、思考题活动选择问题中如果改成选开始时间最早或持续时间最短能得到最优解吗为什么硬币系统 {1, 5, 10, 25} 中贪心总是正确的但 {1, 3, 4} 中不对。硬币系统满足什么条件时贪心正确如何用贪心算法解决“用最少的箭射爆所有气球”问题如果活动有时间权重每个活动有不同价值如何用DP解决欢迎在评论区讨论你的答案。