专题进阶 · 贪心策略推荐总顺序 · 第 76 / 148 课

把局部选择与全局证明连接,学会用交换论证检查一个贪心规则。

先学会这些,再进入本课 插入排序 时间复杂度
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 贪心策略

贪心思想Greedy

每步固定一个局部最优选择,常通过交换论证或割性质证明安全。

建议 40 分钟 · 含手算、代码与三层练习

本课要建立的能力

把局部选择与全局证明连接,学会用交换论证检查一个贪心规则。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

若任务耗时为 [3,1,2],所有任务同时到达且不可抢占,怎样安排顺序让总等待时间最小?

02一步步得到方法

贪心先作出不可撤回的选择

尝试每次先执行耗时最短的任务。直觉是短任务先走能让更多人较早开始,但直觉不是证明。我们需要说明:任何最优顺序都能调整成这个选择而不变差。

比较相邻两项 a、b,前面已经等待 T。先 a 后 b,两项等待为 T 与 T+a;换成 b 后 a,为 T 与 T+b。后面任务等待的总 a+b 不变,所以当 a>b 时交换会减少总等待 a−b。

把局部交换推广到全局

只要还有较长任务排在较短任务前,就可以通过相邻交换减少或不增加成本。反复交换最终得到耗时升序,因此存在按升序的最优解。这是交换论证,不是仅靠跑几个例子。

贪心规则依赖目标函数和输入条件。若任务有不同到达时间、截止期限或权重,刚才的相邻比较式可能改变;不能把短的先做用于所有调度问题。

局部规则需要一条全局桥梁

设计贪心时先问:为什么存在某个最优解愿意采用我的第一步?交换论证常从任意最优解出发,把它的某个选择替换成贪心选择,并证明可行且不更差。

完成第一步后还要说明剩余问题仍具有相同结构,才能递归使用相同规则。几个小例子成功只能帮助发现候选规则,不能替代覆盖所有合法输入的论证。

03把一个小例子完全算清楚

任务耗时 [3,1,2]。

步骤计算与状态为什么这样做
原顺序等待 0、3、4,总和 7先做长任务
交换成 [1,3,2]等待 0、1、4,总和 5减少 2
升序 [1,2,3]等待 0、1、3,总和 4消除全部逆序

窄屏可左右滑动表格,阅读完整计算与理由。

正确贪心的核心是一条可重复使用的安全选择理由。

04为什么这个方法成立

  1. 相邻逆序 a>b 交换后,两任务等待总和减少 a−b,其他任务不受影响。
  2. 任何非升序排列都可通过交换消除逆序。
  3. 最终升序成本不大于任意初始顺序,因此最优。

05把推导翻译成代码

Python · 可独立运行的教学实现

def minimum_waiting(durations):
    assert all(x >= 0 for x in durations)
    elapsed = total = 0
    for duration in sorted(durations):
        total += elapsed
        elapsed += duration
    return total

逐个理解关键决定

total += elapsed
等待时间是任务开始前已经过去的时间,不包含自身处理时间。
sorted(durations)
规则只在本课同时到达、相同权重的条件下已证明。

06时间、空间与实现范围

排序 O(n log n),扫描 O(n),排序副本 O(n)。

贪心可能比 DP 状态少,但必须存在安全选择证明;不是所有最优问题都能如此简化。

07改变条件,检查哪里会出错

挑几个样本都正确就算证明

需要覆盖任意合法输入的交换、不变量或割性质论证。

换了目标函数仍沿用旧排序键

最大数量、最大收益和最小等待可能需要不同规则,旧证明不一定继续成立。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

[2,2,2] 总等待多少?

需要一点提示

前缀和。

查看解析与答案

0+2+4=6,等长任务顺序不影响。

练习 2 · 边界与辨析

任务有优先级权重时仍只按耗时吗?

需要一点提示

交换后的目标差是否相同?

查看解析与答案

不一定,权重改变等待成本;可重新推导按耗时与权重比值的规则,但不能直接沿用。

练习 3 · 变式与迁移

如何快速否定一个可疑贪心?

需要一点提示

构造局部收益与未来冲突。

查看解析与答案

找一个小输入,让当前最优选择阻塞多个更好组合;硬币 [1,3,4]、金额 6 就能否定总选最大面值。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

MIT 6.006 · 算法讲义

理解之后,继续递进

继续当前专题:区间贪心 →。跨专题先修要求会在下一课顶部提示。

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。