数据结构与算法 / 系统课时
用贪心交换论证局部选择
用贪心交换论证局部选择
贪心题真正难的不是写出排序和循环,而是证明“现在这样选”不会堵死后面的最优解。本篇用交换论证建立一套可复用的证明方法:先假设存在一个最优方案,再把它的第一步替换成贪心选择,并证明答案不会变差。
学习目标
- 理解交换论证为什么能够证明贪心选择安全
- 能从排序后的候选项中找出可交换的局部选择
- 能识别只有直觉、却缺少交换依据的伪贪心
交换论证在证明什么
一个贪心算法通常反复执行某个局部规则,例如“先使用最小够用的资源”。仅仅说明这个规则看起来合理还不够,需要证明:至少存在一个全局最优解,其当前选择与贪心选择相同。
典型证明可以压缩成四步:
- 设贪心算法当前选择为
G。 - 任取一个最优方案
OPT;如果它已经选择G,这一轮无需证明。 - 如果
OPT选择了另一个对象X,尝试用G替换X,或者交换G与X的位置。 - 证明交换后方案仍合法,而且目标值不下降,于是得到一个同样最优、但包含
G的方案。
完成这一步后,就可以固定 G,把剩余问题交给同样的规则继续处理。这个过程比“每一步都最好,所以最后最好”严谨得多,因为后一句本身并不是证明。
用最小够用资源观察交换
以 LeetCode 455“分发饼干”为例。孩子需求为 g[i],饼干尺寸为 s[j],一块饼干最多给一个孩子;目标是让尽可能多的孩子满足。排序后,可以从需求最小的孩子开始,为他寻找当前最小且足够大的饼干。
为什么不应该给这个孩子更大的饼干?假设某个最优方案给当前孩子一块更大的饼干 B,而贪心算法选择了更小但已经足够的 A。把 B 换成 A 后,当前孩子仍然满足,而更大的 B 被释放给后续需求更高的孩子,方案不会因此变差。因此总能找到一个最优方案接受贪心的当前选择。
下面的双指针实现正好对应这个证明:孩子和饼干都按升序处理,不够大的饼干直接跳过,第一块够用的饼干立即分配。
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]))预期输出
2输出为 2:尺寸 1 和 2 可以满足需求 1、2 的两个孩子,剩余尺寸 1 无法满足需求 3。
从代码反推证明
写完贪心代码后,可以用三个问题检查它是否真的有依据。
首先问:局部选择到底是什么? 上例不是泛泛地“先满足小需求”,而是“对当前最小需求,使用最小的可行资源”。描述越精确,越容易找到交换对象。
其次问:如果最优解没有这样选,能交换什么? 这里交换的是两块都能满足当前孩子的饼干。较小饼干替代较大饼干后,当前可行性不变,剩余资源只会更宽裕。
最后问:交换是否会改变目标值? 如果交换后满足人数不减少,就说明贪心选择至少能出现在某个最优方案中。随后删除已经处理的孩子和饼干,剩余部分仍是同类型问题,可以继续贪心。
什么时候交换论证会失败
如果把一个选择替换成另一个选择后,会改变未来候选集合、产生额外代价,或者必须同时修改多个互相依赖的决策,就不能直接套用简单交换论证。例如某选择虽然当前成本更小,却可能导致以后必须支付更高成本,此时“局部更优”未必能保持全局目标。
遇到新题时,可以先尝试写出一句完整证明:“若最优解本轮没有选择 G,我可以把它的 X 换成 G,因为……,并且答案不会变差。”如果这句话无法补全,应该继续寻找不变量、反例,或改用动态规划等方法,而不是先把贪心代码写出来再期待它碰巧正确。