数据结构与算法 / 系统课时
贪心选择思想
贪心选择思想
本课解决“为什么某个局部最优选择可以直接保留”的问题。你将从任务装载示例理解贪心算法只向前推进、不回溯的执行方式,并学会判断一条规则是可证明的贪心策略,还是仅凭经验有效的启发式。
学习目标
- 解释贪心算法如何通过连续的局部选择构造完整解。
- 使用贪心选择性质和最优子结构判断策略是否可靠。
- 区分可证明的贪心策略与只在部分输入上有效的启发式规则。
贪心选择的本质
贪心算法在每一步都从当前可行候选中选择一个最符合规则的对象,然后把问题缩小为剩余子问题。已经作出的选择不会被撤销,因此算法通常只需排序和一次扫描,执行路径清晰、状态数量少。
考虑“在总耗时不超过 10 的前提下完成尽可能多的同价值任务”。任务耗时为 6、2、4、1、3 时,优先选择耗时最短的任务,可以依次装入 1、2、3、4,恰好完成 4 个任务。每次选择后只更新剩余预算,不重新组合此前任务。

正确性与启发式的边界
局部规则看起来合理,并不代表它一定得到全局最优解。一个可靠的贪心算法通常需要同时满足两个条件:存在某个最优解包含当前贪心选择;作出该选择后,剩余部分仍是同类型的最优子问题。
| 判断维度 | 可证明的贪心策略 | 简单启发式 |
|---|---|---|
| 选择依据 | 与目标函数直接对应 | 来自经验或直觉 |
| 正确性 | 能用交换论证、归纳等方法证明 | 只能通过样例观察效果 |
| 失败处理 | 在定义域内保证最优 | 可能在特殊输入上失效 |
| 是否回溯 | 通常不回溯 | 也可能不回溯,但不保证最优 |
在任务数量最大化问题中,设某个最优方案选择的第一个任务耗时为 x,全局最短任务耗时为 g,则必有 g <= x。用 g 替换 x 不会增加总耗时,也不会减少可选任务数量,因此至少存在一个最优方案包含 g。这就是交换论证的核心。
排序需要 O(n log n) 时间,随后扫描需要 O(n) 时间。若输入已经按耗时升序排列,扫描本身只需要 O(n)。
完整可运行示例
下面的程序分别执行“最短优先”和“最长优先”。前者与“最大化任务数量”的目标一致并可证明最优;后者只是一个看似积极但效果较差的启发式。
将代码保存为 GreedyChoiceDemo.java。
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
public class GreedyChoiceDemo {
record Task(String name, int duration) {
@Override
public String toString() {
return name + "(" + duration + ")";
}
}
static List<Task> selectTasks(List<Task> tasks, int budget, boolean shortestFirst) {
List<Task> sorted = new ArrayList<>(tasks);
Comparator<Task> comparator = Comparator.comparingInt(Task::duration);
sorted.sort(shortestFirst ? comparator : comparator.reversed());
List<Task> selected = new ArrayList<>();
int used = 0;
// 接受当前顺序下仍能放入预算的任务,不撤销此前选择。
for (Task task : sorted) {
if (used + task.duration() <= budget) {
selected.add(task);
used += task.duration();
}
}
return selected;
}
static int totalDuration(List<Task> tasks) {
return tasks.stream().mapToInt(Task::duration).sum();
}
public static void main(String[] args) {
List<Task> tasks = List.of(
new Task("T1", 6),
new Task("T2", 2),
new Task("T3", 4),
new Task("T4", 1),
new Task("T5", 3)
);
int budget = 10;
List<Task> shortestFirst = selectTasks(tasks, budget, true);
List<Task> longestFirst = selectTasks(tasks, budget, false);
System.out.println("按耗时升序选择: " + shortestFirst);
System.out.println("已选数量: " + shortestFirst.size());
System.out.println("总耗时: " + totalDuration(shortestFirst));
System.out.println("按耗时降序选择: " + longestFirst);
System.out.println("已选数量: " + longestFirst.size());
}
}编译并运行:
javac GreedyChoiceDemo.java
java GreedyChoiceDemo预期输出
按耗时升序选择: [T4(1), T2(2), T5(3), T3(4)]
已选数量: 4
总耗时: 10
按耗时降序选择: [T1(6), T3(4)]
已选数量: 2常见错误
1. 把“局部最好”直接等同于“全局最优”
例如硬币面额为 1、3、4,金额为 6 时,优先取最大面额会得到 4 + 1 + 1,但最优解是 3 + 3。修复方法不是给规则增加更多特例,而是重新证明贪心选择性质,证明失败时应考虑动态规划等方法。
2. 选择后又尝试撤销
一旦算法需要枚举此前选择并频繁回滚,它就不再是典型贪心过程。应先明确局部规则是否足以保证安全选择,再决定是否需要搜索、回溯或动态规划。
3. 只计算扫描复杂度
“每个元素只访问一次”并不代表总复杂度一定是 O(n)。当贪心顺序依赖排序时,总时间通常由排序阶段决定,即 O(n log n)。
本课练习
- 给定任务耗时
8、1、5、2、3、4和预算11,手工执行最短优先策略,记录每一步的剩余预算。验收条件是给出最终任务数量、总耗时和选择顺序。 - 构造一个“优先选择耗时最接近剩余预算”的启发式规则,并给出至少一组使其少选任务的反例。验收条件是同时展示启发式结果和真正的最优结果。
本课总结
- 贪心算法通过不可撤销的局部选择持续缩小问题,通常具有排序加扫描的结构。
- 一条规则只有在贪心选择性质和最优子结构得到证明后,才能称为可靠的贪心策略。
- 启发式也可以很快,但它只描述“怎么选”,不自动提供最优性保证。
下一课预告
下一课将学习“活动选择问题”,把本课的判断框架应用到时间区间上,并证明“每次选择最早结束的兼容活动”为什么能够得到最多活动。