贪心辨识¶
方法速览¶
| 任务 | 判断 | 口诀 |
|---|---|---|
| 是不是贪心 | 每步取局部最优、不回头 | 只看眼前 |
| 经典贪心算法 | Dijkstra、Prim、Kruskal、Huffman | 四大贪心 |
| 非贪心的代表 | Floyd（DP 枚举中转点）、普通 0-1 背包 | 全局规划 |
| 贪心失效的问题 | 0-1 背包（不可拆分）、TSP、最长公共子序列 | 拆不了就别贪 |
| 任务调度 | 截止时间最早优先（EDF） penalty 最小 | 早截止先做 |
贪心的边界¶
【是什么】 贪心每一步取当前最优、不做全局回溯——对某些问题结构（贪心选择性质 + 最优子结构）能得全局最优。
经典属于贪心的：Dijkstra（每次取最近点）、Prim / Kruskal（每次取最小边）、Huffman（每次合并最小频率）。
不属于贪心的：Floyd（三重循环枚举中转点，是 DP）、动态规划族、分治族。
贪心不能精确解的（2020 真题）：0-1 背包——物品不可拆分，局部性价比最优可能挤占空间；可拆分的部分背包才可贪心。
任务调度（EDF）¶
【例】（2025 真题）5 任务（时长, 截止）：\(A_1(3,5), A_2(4,10), A_3(2,3), A_4(5,15), A_5(1,11)\)，超时惩罚 = 时长：
| 策略 | 顺序 | 惩罚 |
|---|---|---|
| 最短优先 SPT | \(A_5 A_3 A_1 A_2 A_4\) | \(3\)（\(A_3\) 超时） |
| 最早截止优先 EDF | \(A_3 A_1 A_2 A_5 A_4\) | \(\bf 0\) |
EDF（Earliest Deadline First）是带截止时间调度的经典最优贪心——优先执行截止时间最早的任务（全排列枚举验证惩罚 0 最优）。
练习题目¶
练习 1 · 贪心的定义¶
题目
贪心算法的核心特征是（ ）
- A. 每步取当前局部最优，不回溯
- B. 把问题分成两半递归
- C. 枚举所有解
- D. 记忆化搜索
答案与解析
答案：A
只看眼前、不回头；B 是分治、C 是搜索、D 是记忆化。
练习 2 · 属于贪心的算法¶
题目
下列属于贪心算法的是（ ）
- A. 归并排序
- B. Floyd 全源最短路
- C. Dijkstra 单源最短路
- D. 快速幂
答案与解析
答案：C
Dijkstra 每次取未确定点中最近的；Floyd 是 DP。
练习 3 · 属于贪心的算法（二）¶
题目
下列属于贪心算法的是（ ）
- A. 二分查找
- B. 深度优先搜索
- C. 动态规划
- D. Kruskal 最小生成树
答案与解析
答案：D
每次选不成环的最小边。
练习 4 · 不属于贪心¶
题目
下列不属于贪心算法的是（ ）
- A. Prim
- B. Kruskal
- C. Huffman 编码
- D. Floyd
答案与解析
答案：D
Floyd 枚举中转点做区间 DP——三重循环不是贪心（2019 真题）。
练习 5 · 贪心可解 vs 不可解¶
题目
下列问题不能用贪心精确求解的是（ ）
- A. 部分背包（物品可切割）
- B. 0-1 背包
- C. 最小生成树
- D. 单源最短路（非负权）
答案与解析
答案：B
0-1 背包物品不可拆——经典反例；A 可按性价比装满。
练习 6 · Huffman 是贪心¶
题目
哈夫曼编码的贪心策略是（ ）
- A. 每次取最长的串
- B. 每次合并频率最小的两个结点
- C. 按字典序
- D. 随机合并
答案与解析
答案：B
小频率深放、大频率浅放——WPL 最小。
练习 7 · 贪心的正确性¶
题目
贪心得到全局最优需要满足（ ）
- A. 无条件成立
- B. 数据有序
- C. 问题有多解
- D. 贪心选择性质 + 最优子结构
答案与解析
答案：D
局部最优能导出全局最优（选择性质），且子问题独立最优（子结构）——需要证明。
练习 8 · 找零问题¶
题目
面额 \(\{1, 5, 10, 50\}\) 凑 60 元，贪心（每次取最大面额）得到（ ）张。
- A. \(6\)
- B. \(3\)
- C. \(2\)
- D. \(4\)
答案与解析
答案：C
\(50 + 10\)——此面额体系贪心恰好最优。
练习 9 · 贪心失效的找零¶
题目
面额 \(\{1, 5, 11\}\) 凑 15 元，贪心（最大面额优先）与最优分别是（ ）张。
- A. 都 \(5\)
- B. \(3\) 和 \(5\)
- C. 都 \(3\)
- D. \(5\) 和 \(3\)
答案与解析
答案：D
贪心 \(11+1+1+1+1 = 5\) 张；最优 \(5+5+5 = 3\) 张——面额不“整除”时贪心翻车。
练习 10 · 区间调度¶
题目
n 个活动选最多的互不重叠区间，贪心策略是（ ）
- A. 按时长最短
- B. 按开始时间最早
- C. 按结束时间最早优先
- D. 随机选
答案与解析
答案：C
结束越早给后面留的空间越大——经典可证明贪心。
练习 11 · 部分背包¶
题目
部分背包的贪心策略（ ）
- A. 按价值升序
- B. 按重量升序
- C. 按价值/重量比降序装入，装不下则切割装满
- D. 无法贪心
答案与解析
答案：C
可切割使“每单位容量收益”最大即全局最优。
练习 12 · Dijkstra 的贪心性¶
题目
Dijkstra 每轮从未确定集合中取（ ）
- A. 距离源点最小的顶点
- B. 度数最大的顶点
- C. 编号最小的顶点
- D. 随机顶点
答案与解析
答案：A
非负权下该距离不会再变小——贪心选择成立。
练习 13 · 负权边¶
题目
带负权边的图上 Dijkstra（ ）
- A. 报错
- B. 一定正确
- C. 自动切换 Bellman-Ford
- D. 可能得到错误答案
答案与解析
答案：D
贪心前提“已确定的距离不再变”被负权破坏。
练习 14 · Kruskal 的贪心¶
题目
Kruskal 选边的准则是（ ）
- A. 权最小且不构成环
- B. 任意最小边（即使成环）
- C. 连通度最大
- D. 随机
答案与解析
答案：A
排序后逐条试，成环跳过（并查集判环）。
练习 15 · EDF 调度¶
题目
带截止时间的单机任务调度，最小化超时惩罚的贪心策略是（ ）
- A. 处理时长最短优先
- B. 截止时间最早优先（EDF）
- C. 惩罚最大优先
- D. 字典序
答案与解析
答案：B
早截止先做给后面腾时间（2025 真题，EDF 达到惩罚 0）。
练习 16 · 贪心与 DP 的关系¶
题目
贪心与动态规划都具备最优子结构，区别在于（ ）
- A. 贪心每步只走一条局部最优路、DP 考察所有子状态
- B. DP 不能求最值
- C. 贪心总是慢
- D. 没有区别
答案与解析
答案：A
贪心是“不回头的决策”；DP 是“全子问题表格”。
练习 17 · 贪心反例（跳跃）¶
题目
数组每格表示可跳最大步数，从首格跳到末格求最少步数。贪心“跳到能及最远处”在此问题上是（ ）
- A. 会死循环
- B. 错误策略
- C. 正确策略（区间扩张可证明）
- D. 只对小数组正确
答案与解析
答案：C
每一步覆盖可达区间最大化——可交换论证保证最优。
练习 18 · 排队打水¶
题目
n 人打水、第 i 人耗时 \(t_i\)，最小化总等待时间的策略是（ ）
- A. 耗时短的先打
- B. 耗时长的先打
- C. 任意
- D. 同时打
答案与解析
答案：A
短的先走，后面等待的人少——排序不等式。
练习 19 · 田忌赛马¶
题目
田忌赛马的最优策略属于（ ）
- A. 二分
- B. 纯暴力
- C. DP
- D. 贪心（最弱对最强、其余逐对比较）
答案与解析
答案：D
牺牲最弱消耗对方最强，剩余局部最优——经典贪心构造。
练习 20 · 贪心交换论证¶
题目
证明贪心正确的常用方法是（ ）
- A. 交换论证：任何最优解换成贪心选择不变差
- B. 随机试验
- C. 举一个例子
- D. 无法证明
答案与解析
答案：A
把最优解里的选择换成贪心的选择，证明代价不增。
练习 21 · Huffman 逆命题¶
题目
定长编码（每字符 3 位）与哈夫曼编码的关系（ ）
- A. 哈夫曼总不劣于定长
- B. 定长总更优
- C. 无关
- D. 相等
答案与解析
答案：A
哈夫曼是编码树 WPL 的最优解，定长只是它的一个特例。
练习 22 · 局部最优陷阱¶
题目
“每步选当前数字最大”在数字拼最大数问题上（ ）
- A. 正确（高位贪心）
- B. 错误（要考虑位数与后效）
- C. 无法执行
- D. 只对一位数正确
答案与解析
答案：B
单纯按数值大小选（如先取 9 拼成 956）不一定最大；正确做法是按拼接结果比较（ab 与 ba 谁大）贪心——数值贪心缺这个比较器。
练习 23 · TSP¶
题目
旅行商问题（TSP）用最近邻贪心（ ）
- A. 得到精确最优
- B. 只是近似解，可能远差于最优
- C. 无解
- D. 等价于 MST
答案与解析
答案：B
TSP 是 NP 难问题，贪心只是启发式。
练习 24 · MST 贪心正确性¶
题目
Kruskal 正确性的关键性质是（ ）
- A. 切割性质（横跨任何切割的最小边必在某棵 MST 中）
- B. 三角不等式
- C. 抽屉原理
- D. 容斥原理
答案与解析
答案：A
切割性质（cut property）支撑“最小边安全”。
练习 25 · 贪心复杂度¶
题目
排序后线性扫描的贪心（如活动选择），总复杂度通常是（ ）
- A. \(O(n^2)\)
- B. \(O(n)\)
- C. \(O(n\log n)\)（排序支配）
- D. \(O(2^n)\)
答案与解析
答案：C
排序 \(n\log n\) + 扫描 \(n\)。
练习 26 · 综合判断¶
题目
下列错误的是（ ）
- A. Dijkstra、Prim、Kruskal、Huffman 都是贪心
- B. 0-1 背包不能用贪心精确解
- C. 贪心一定得到全局最优
- D. 贪心需要贪心选择性质才能保证正确
答案与解析
答案：C
贪心不总是最优——这正是 S 卷反向题的考点。
历年真题¶
2019 年 · 第 13 题¶
题目
以下哪些算法不属于贪心算法？（ ）
- A.
Dijkstra算法 - B.
Prim算法 - C.
Kruskal算法 - D.
Floyd算法
答案与解析
答案：D
前三者都是“每步取局部最优”；Floyd 逐个枚举中转点做整个 DP。
2020 年 · 第 6 题¶
题目
下列哪些问题不能用贪心法精确求解？（ ）
- A. 霍夫曼编码问题
- B. \(0\)-\(1\) 背包问题
- C. 最小生成树问题
- D. 单源最短路径问题
答案与解析
答案：B
0-1 背包物品不可拆分，局部性价比选择可能挤占空间；A/C/D 都是经典贪心正确的问题。
2025 年 · 第 15 题¶
题目
有 \(5\) 个独立的、不可抢占的任务 \(A_1, A_2, A_3, A_4, A_5\) 需要在一台机器上执行（从时间 \(0\) 开始执行），每个任务都有对应的处理时长和截止时刻，按顺序分别为 \(3, 4, 2, 5, 1\) 和 \(5, 10, 3, 15, 11\)。如果某一个任务超时，相应的惩罚等于其处理时长。为了最小化总惩罚，应该优先执行哪个任务？
- A. 处理时间最短的任务 \(A_5\)
- B. 截止时间最早的任务 \(A_3\)
- C. 处理时间最长的任务 \(A_4\)
- D. 任意一个任务都可以
答案与解析
答案：B
EDF：按截止时间 \(A_3(3) \to A_1(5) \to A_2(10) \to A_5(11) \to A_4(15)\) 执行，全部不超时、总惩罚 0（SPT 顺序会罚 3；全排列枚举验证 0 最优——对比表见教学节）。
易错小结¶
- 四大贪心：Dijkstra、Prim、Kruskal、Huffman；Floyd 是 DP（2019 反向题）；
- 0-1 背包贪心不可精确解（2020 真题）；部分背包、活动选择、找零（规范面额）可以；
- 贪心正确需要贪心选择性质，常用交换论证；不是所有局部最优都通向全局；
- 带截止时间的调度：截止最早优先（EDF）（2025 真题，惩罚 0）；
- 找零反例 \(\{1,5,11\}\) 凑 15：贪心 5 张、最优 3 张——记住这个反例。