数据结构与算法 / 系统课时

用贪心交换论证局部选择

用贪心交换论证局部选择

贪心题真正难的不是写出排序和循环,而是证明“现在这样选”不会堵死后面的最优解。本篇用交换论证建立一套可复用的证明方法:先假设存在一个最优方案,再把它的第一步替换成贪心选择,并证明答案不会变差。

学习目标

  • 理解交换论证为什么能够证明贪心选择安全
  • 能从排序后的候选项中找出可交换的局部选择
  • 能识别只有直觉、却缺少交换依据的伪贪心

交换论证在证明什么

一个贪心算法通常反复执行某个局部规则,例如“先使用最小够用的资源”。仅仅说明这个规则看起来合理还不够,需要证明:至少存在一个全局最优解,其当前选择与贪心选择相同。

典型证明可以压缩成四步:

  1. 设贪心算法当前选择为 G。
  2. 任取一个最优方案 OPT;如果它已经选择 G,这一轮无需证明。
  3. 如果 OPT 选择了另一个对象 X,尝试用 G 替换 X,或者交换 G 与 X 的位置。
  4. 证明交换后方案仍合法,而且目标值不下降,于是得到一个同样最优、但包含 G 的方案。

完成这一步后,就可以固定 G,把剩余问题交给同样的规则继续处理。这个过程比“每一步都最好,所以最后最好”严谨得多,因为后一句本身并不是证明。

用最小够用资源观察交换

以 LeetCode 455“分发饼干”为例。孩子需求为 g[i],饼干尺寸为 s[j],一块饼干最多给一个孩子;目标是让尽可能多的孩子满足。排序后,可以从需求最小的孩子开始,为他寻找当前最小且足够大的饼干。

为什么不应该给这个孩子更大的饼干?假设某个最优方案给当前孩子一块更大的饼干 B,而贪心算法选择了更小但已经足够的 A。把 B 换成 A 后,当前孩子仍然满足,而更大的 B 被释放给后续需求更高的孩子,方案不会因此变差。因此总能找到一个最优方案接受贪心的当前选择。

下面的双指针实现正好对应这个证明:孩子和饼干都按升序处理,不够大的饼干直接跳过,第一块够用的饼干立即分配。

python
from typing import List


def find_content_children(g: List[int], s: List[int]) -> int:
    g.sort()
    s.sort()
    child = 0
    cookie = 0

    # 第一块能满足当前孩子的饼干,就是应该保留的最小可行选择。
    while child < len(g) and cookie < len(s):
        if s[cookie] >= g[child]:
            child += 1
        cookie += 1

    return child


if __name__ == "__main__":
    print(find_content_children([1, 2, 3], [1, 1, 2]))

预期输出

text
2

输出为 2:尺寸 1 和 2 可以满足需求 1、2 的两个孩子,剩余尺寸 1 无法满足需求 3。

从代码反推证明

写完贪心代码后,可以用三个问题检查它是否真的有依据。

首先问:局部选择到底是什么? 上例不是泛泛地“先满足小需求”,而是“对当前最小需求,使用最小的可行资源”。描述越精确,越容易找到交换对象。

其次问:如果最优解没有这样选,能交换什么? 这里交换的是两块都能满足当前孩子的饼干。较小饼干替代较大饼干后,当前可行性不变,剩余资源只会更宽裕。

最后问:交换是否会改变目标值? 如果交换后满足人数不减少,就说明贪心选择至少能出现在某个最优方案中。随后删除已经处理的孩子和饼干,剩余部分仍是同类型问题,可以继续贪心。

什么时候交换论证会失败

如果把一个选择替换成另一个选择后,会改变未来候选集合、产生额外代价,或者必须同时修改多个互相依赖的决策,就不能直接套用简单交换论证。例如某选择虽然当前成本更小,却可能导致以后必须支付更高成本,此时“局部更优”未必能保持全局目标。

遇到新题时,可以先尝试写出一句完整证明:“若最优解本轮没有选择 G,我可以把它的 X 换成 G,因为……,并且答案不会变差。”如果这句话无法补全,应该继续寻找不变量、反例,或改用动态规划等方法,而不是先把贪心代码写出来再期待它碰巧正确。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用贪心交换论证局部选择

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通