🍬 贪心算法

有一排糖果只能从一头拿，每次都伸手拿最大的那颗，最后拿到的总数是不是最多？有些问题是！「每步都选眼前看起来最好的，走一步就不回头」就是贪心算法。这一页学会贪心的套路，也要学会分辨——不是所有题贪心都对，它需要一种叫「最优子结构」的魔法。

考纲知识点：贪心算法的相关概念
最优子结构

📖

考纲 · 知识点详述

摘自《CCF编程能力等级认证 C++&Python 认证标准》C++ 五级

(8)掌握贪心算法的基本原理，理解最优子结构，能够使用贪心算法解决相关问题。

📚

先学一学

花 5 分钟读完下面 5 课，再去闯关就不慌啦

🍬 贪心 = 每步选眼前最优，走了不回头

贪心算法做选择时只看眼前这一步：选最大、最小、最快、最早的那个，选完就往前走、不反悔，把剩下的问题继续用同样规则处理。它不「向后看」也不「全局搜索」，所以特别快。

🍭 生活类比：自助餐拿水果

自助餐规定一次只能拿一种水果、每种最多拿一次，想凑出最多的重量。贪心的做法是：每次都拿当前剩下的最重那种。这个「每次拿最大」的规则，在很多题里真的能凑出全局最优。

💡 口诀：贪心三字诀：眼前好、选完走、不回头。

🆚 贪心 vs 枚举

把所有可能都试一遍一定对，但慢；贪心快，但只在满足条件时保证最优。所以贪心题的考点常是：「这个题用贪心选哪条规则？贪心能不能保证最优？」

💡 口诀：枚举稳但慢，贪心快但挑题；判断对不对，先验证反例。

🎬 经典贪心：一天最多看几场电影

一天有好几场电影可选，每场有开始和结束时间，同一时间只能看一场，想看得最多。贪心的妙招是：每次都选「结束最早」且不冲突的那场——结束得早，给后面留的时间最多，于是能看到更多场。

🧪 例子

场次：A(9:00~11:00)、B(8:00~9:30)、C(9:30~12:00)、D(8:30~10:00)。
先把它们按结束时间排序：B 结束最早(9:30) → 选 B。
下一个开始时间 ≥ 9:30 的是 C(9:30~12:00) → 选 C。
结果：B + C 两场，贪心得到最优。

💡 口诀：选结束最早的先看，给后面的电影多留时间——活动安排贪心法。

🧩 最优子结构：局部最优能拼出全局最优

最优子结构是说：一个问题的最优解里，包含的子问题也一定是最优解。贪心能用，前提正是「每步选眼前最优，拼起来就是整体最优」——也就是局部最优能组成全局最优。

🏗️ 类比：盖塔楼

如果每一层都盖到最高，整座塔就最高——这就有「最优子结构」，贪心放心用。
如果一层盖太高会压垮下面的结构，那「每层最高」反而全塌——没有最优子结构，贪心就不靠谱。

💡 口诀：最优子结构 = 每步最优拼起来仍最优；子问题最优，大问题才最优。

✅ 怎么验证能用贪心

① 猜一条「眼前最优」的规则；② 试着找反例——如果找不到，大概率能用；③ 严谨点要证明「交换论证」或「归纳」，考试判断正误时，想想有没有让贪心失手的特例。

💡 口诀：贪心规则先猜后验；找不到反例才敢放心用。

⚠️ 贪心会翻车：不是每道题都能贪

🪙 反例：奇怪面额的硬币

假设硬币面额只有 1、4、5，要凑出 8 元。贪心会先拿最大的 5，再拿 1、1、1 → 一共 4 枚（5+1+1+1）。但正确答案是 4+4 两枚！贪心第一步选「眼前最大的 5」，结果全局不是最优。

💡 口诀：面额不整，贪心会翻车；硬币凑数要先看面额能不能贪。

🆚 贪心 vs 动态规划

· 贪心：只看眼前，做一次决定不回头；快，但要求最优子结构 + 贪心选择性质。
· 动态规划：把子问题的解都记下来，比较后再选；更全面（六级会学），适合贪心不灵的问题。
这道硬币题就是动态规划比贪心靠谱的典型。

💡 口诀：贪心快、会挑题；动态规划慢而全；贪心翻车的地方，常常要 DP 出马。

🌐 贪心用在哪儿

🧭 常见贪心题套路

· 活动/会议安排：按结束时间排序，选最早结束的。
· 排队接水/做作业：让用时短的先做，大家总等待最少。
· 背包可拆分（能切一部分）：单位重量价值高的先装。
· 区间覆盖、任务调度……多半先排序，再按规则一个个选。

💡 口诀：贪心三步曲：先排序、定规则、逐个选；规则对不对，反例验一验。

🌟 行业实际

网络里路由器转发数据包、操作系统给任务排队、地图导航的近似路线、压缩算法的哈夫曼编码（六级会学），都有贪心思想。它不一定永远给出理论最优，但「够快 + 大多数情况够好」，正是很多真实系统的选择。

💡 口诀：又快又够好，贪心受青睐；但要记得——它只在最优子结构下才保最优。

🎯

闯关小锦囊 · 考点提醒

贪心：每步选眼前最优，选完不回头；快，但只在满足条件时保证全局最优。
活动安排用「先按结束时间排序，选最早结束不冲突」的贪心规则。
最优子结构：全局最优里包含的子问题也是最优，局部最优拼成全局最优。
贪心可能翻车（如面额 1、4、5 凑 8：贪心给 4 枚，最优只要 2 枚）——猜规则要找反例验证。
贪心 vs 动态规划：贪心快会挑题；DP 慢而全，贪心不灵的题常交给 DP。
最优子结构只是必要条件：有最优子结构也不一定能贪心（如 0/1 背包要 DP）；贪心还要满足「贪心选择性质」。

🎮

学完了？来闯关！

下面 15 个小挑战，点一点就能玩

Demo 原型 · 每个知识点独立页面 · 暂不含真实编译与进度存储。