3.1.贪心算法导论——为什么“局部最优“能推出“全局最优“？

3.1.贪心算法导论——为什么局部最优能推出全局最优系列贪心算法 | 第 1 篇共 8 篇难度⭐⭐☆☆☆ 入门-中等标签贪心正确性证明交换论证反证法算法思想上一篇…下一篇区间贪心——活动选择、区间调度与区间合并三类经典问题前言有一类题如果你想到了正确的思路代码极短运行极快但如果没想到怎么想都觉得要 DP。这类题叫贪心题。贪心的核心思想是每一步都做当前看起来最优的选择不回头不后悔。听上去很冒险——为什么眼前最优能保证最终最优这篇要讲清楚三件事贪心算法是什么它解决什么类型的问题贪心正确性怎么证明两种主流方法贪心为什么会失效怎么识别伪贪心一、算法思想每步做局部最优选择贪心算法的核心动作就一句话在每个决策点选当前最优的那个选项直到问题结束。最典型的日常例子找零钱时先用面值最大的硬币凑不够再用小的这就是贪心。它的特点是不枚举所有可能不依赖之前做了什么每步只看眼前快速决策贪心能用的两个前提贪心不是万能的。它能给出正确答案需要问题满足1. 贪心选择性质全局最优解可以通过每步的局部最优决策来构造。也就是说当前的最优选择不会让你在未来付出代价。2. 最优子结构问题的最优解包含子问题的最优解。这和动态规划的要求一样。区别在于DP 需要枚举子问题贪心直接从子问题的最优选择出发贪心 vs 动态规划两者都要求最优子结构但选择策略不同对比项贪心动态规划决策方式每步直接选当前最优枚举所有子问题取全局最优是否回退不回退依靠状态记忆所有可能速度更快通常更慢适用范围需证明贪心正确更通用如果一个问题贪心能解就不用 DP但贪心的正确性需要证明。二、完整图解一个能用贪心的例子 vs 一个不能用的能用贪心硬币找零特定面值面值为[1, 5, 10, 25]目标凑出 41 分。选 25剩 16→ 选 10剩 6→ 选 5剩 1→ 选 1结束 共 4 枚每步都选当前能用的最大面值最终用了最少的硬币。✅不能用贪心硬币找零特殊面值面值为[1, 3, 4]目标凑出 6。贪心做法选 4剩 2→ 选 1剩 1→ 选 1结束 共 3 枚最优做法选 3剩 3→ 选 3结束 共 2 枚 ✅贪心给出了错误答案。原因选了 4 之后后续的选择空间被限制了整体反而更差。核心结论贪心失效的根本原因是——局部最优不等于全局最优。三、正确性证明两种主流方法贪心最难的不是代码而是证明它是对的。竞赛中最常用的两种方法方法一交换论证Exchange Argument思路假设存在一个最优解它的某一步选择和贪心不同。证明把那一步改成贪心的选择结果不会变差或更优。例子活动选择问题有若干活动每个活动有开始时间和结束时间只能同时参加一个。目标最多参加多少个活动贪心策略每次选结束时间最早的活动。交换论证假设最优解不选结束最早的活动 A而选了另一个活动 B结束更晚把 B 替换成 AA 结束更早不会影响后续活动的选择空间替换后活动数量不减少因此贪心选择不劣于任何最优解 ✅方法二反证法Contradiction思路假设贪心给出的不是最优解然后推出矛盾。例子任务截止时间问题有 n 个任务每个任务有截止时间 d 和罚款 w每次只能做一个任务耗时 1。目标最小化超期罚款总和。贪心策略按截止时间排序尽量在截止前完成否则调换顺序推迟。反证若存在更优解必然有某两个任务的顺序和贪心相反——但可以证明调整后结果不变或更优矛盾。四、代码结构贪心的通用写法贪心算法没有固定模板但结构上基本都是1. 对问题按某个贪心标准排序 2. 从头到尾扫描按贪心策略做决策 3. 维护当前状态不需要回溯五、复杂度分析大多数贪心算法的时间复杂度来自两部分步骤时间复杂度说明排序如果需要O(n log n)最常见的前置步骤扫描决策O(n) * k线性扫描一遍做每一个选择的时间复杂度是kk有可能是常数也有可能是O(m)、O(logm)等取决于选择的具体情况整体O(n log n) O(n) * k选择简单则瓶颈在排序选择复杂则瓶颈在选择贪心算法几乎不会有空间上的额外开销通常是O(1)或O(n)。六、贪心常见题型分类题型贪心策略典型题目区间调度按结束时间排序活动选择、会议室安排任务调度按截止/权重排序带截止任务、带权完成时间分配问题排序后双端配对糖果分配、救生艇跳跃问题维护最远可达位置跳跃游戏字典序构造单调栈贪心移除k个数字、最小字符串数学贪心利用数学性质最大乘积、分组七、OJ 例题讲解例题 1LeetCode 455 — 分发饼干贪心入门题目来源LeetCode题号 455难度⭐☆☆☆☆ 简单题目链接https://leetcode.cn/problems/assign-cookies/题目描述每个孩子有一个胃口值g[i]每块饼干有一个尺寸s[j]。当饼干尺寸s[j] g[i]时孩子i满足。每个孩子最多分一块饼干求最多满足多少个孩子。输入样例g [1,2,3], s [1,1]输出样例1解题思路贪心策略优先用最小能满足需求的饼干去满足胃口最小的孩子。将g和s分别升序排序双指针扫描饼干能满足当前孩子就分配否则换下一块更大的饼干统计满足孩子数正确性用大饼干满足小胃口的孩子是浪费最小够用的饼干留给最小需求的孩子后续资源更充裕。Python 解法fromtypingimportListclassSolution:deffindContentChildren(self,g:List[int],s:List[int])-int:g.sort()s.sort()ij0whileilen(g)andjlen(s):ifs[j]g[i]:i1# 孩子被满足看下一个孩子j1# 不管满没满足饼干都用掉了returniC 解法classSolution{public:intfindContentChildren(vectorintg,vectorints){sort(g.begin(),g.end());sort(s.begin(),s.end());inti0,j0;while(i(int)g.size()j(int)s.size()){if(s[j]g[i])i;j;}returni;}};代码讲解j始终向前推进表示当前考察的饼干i只在饼干满足孩子时前进表示已满足的孩子数最终i就是答案例题 2LeetCode 860 — 柠檬水找零状态模拟型贪心题目来源LeetCode题号 860难度⭐⭐☆☆☆ 简单题目链接https://leetcode.cn/problems/lemonade-change/题目描述柠檬水每杯 5 美元。顾客按序付款每次付 5、10 或 20 美元。需要找零时判断是否始终能正确找零。输入样例bills [5,5,10,10,20]输出样例false解题思路模拟找零过程关键在于收到 10 元必须找 1 张 5 元收到 20 元优先找 1 张 10 元 1 张 5 元若没有 10 元则找 3 张 5 元贪心收到 20 元时优先消耗 10 元因为 5 元比 10 元更万能这是核心决策点。Python 解法fromtypingimportListclassSolution:deflemonadeChange(self,bills:List[int])-bool:fiveten0forbillinbills:ifbill5:five1elifbill10:iffive0:returnFalsefive-1ten1else:# bill 20iften0andfive0:ten-1;five-1eliffive3:five-3else:returnFalsereturnTrueC 解法classSolution{public:boollemonadeChange(vectorintbills){intfive0,ten0;for(intbill:bills){if(bill5){five;}elseif(bill10){if(!five)returnfalse;five--;ten;}else{if(tenfive){ten--;five--;}elseif(five3){five-3;}elsereturnfalse;}}returntrue;}};代码讲解维护five和ten两个计数器即可收到 20 时先用105找零优先消耗 10 元保留 5 元给更多场景任意时刻找不开直接返回false例题 3HDU 2037 — 今年暑假不 AC活动选择贪心入门题目来源HDU OJ题号 2037难度⭐⭐☆☆☆ 简单题目链接http://acm.hdu.edu.cn/showproblem.php?pid2037题目描述暑假期间有n个节目每个节目有开始时间和结束时间。每次只能看一个节目求最多能看多少个完整节目。输入样例12 1 3 3 4 0 7 3 8 15 19 15 20 10 15 8 18 6 12 5 10 4 14 2 9 0输出样例5解题思路经典活动选择问题按结束时间对所有节目升序排序维护lastEnd当前已选节目的最晚结束时间扫描若节目开始时间 lastEnd选它更新lastEnd按结束时间贪心的正确性每次选最早结束的节目为后续留出最大空间。Python 解法importsysinputsys.stdin.readlinewhileTrue:nint(input())ifn0:breakprograms[]for_inrange(n):s,emap(int,input().split())programs.append((e,s))# 先按结束时间排programs.sort()count0last_end0forend,startinprograms:ifstartlast_end:count1last_endendprint(count)C 解法#includebits/stdc.husingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;while(cinnn){vectorpairint,intprogs(n);// {end, start}for(inti0;in;i){ints,e;cinse;progs[i]{e,s};}sort(progs.begin(),progs.end());// 按结束时间升序intcount0,lastEnd0;for(auto[e,s]:progs){if(slastEnd){count;lastEnde;}}coutcount\n;}return0;}代码讲解以{end, start}形式存储直接按 pair 默认升序排就是按结束时间排lastEnd记录上一个选中节目的结束时间每次遇到不冲突的节目就贪心选择最终count即为答案八、适用场景场景是否适合贪心原因活动选择 / 区间调度✅经典贪心按结束时间排序找零 / 分配✅特定条件下需满足贪心选择性质背包问题0-1 背包❌不满足贪心选择性质用 DP最短路无负权✅Dijkstra满足贪心性质有限制的任务调度✅按截止/权重排序九、常见错误总结错误原因正确做法没有证明正确性就乱用贪心感觉对但其实错先用交换论证或反证法验证贪心标准选错比如区间调度按开始时间而非结束时间想清楚哪个维度是关键忽视排序步骤直接扫描未排序数组大多数贪心需要先排序用贪心解 0-1 背包典型错误0-1 背包是 DP分数背包才能贪心证明时只给举例举例不能证明正确性必须用形式化论证总结要点内容核心思想每步做局部最优不回退成立条件贪心选择性质 最优子结构正确性证明交换论证 / 反证法典型失效场景0-1 背包、特殊面值找零常见前置步骤排序时间复杂度通常O(n log n)瓶颈在排序选择局部最优复杂时瓶颈在遍历选择O(n * k)一句话记住贪心贪心不是随便选而是能证明当前最优不会影响后续最优的有根据的选择。上一篇…下一篇区间贪心——活动选择、区间调度与区间合并三类经典问题看完有收获的话点个赞再走有问题欢迎评论区讨论