7.2 贪心正确性的证明

这一节回答什么问题？

直觉上贪心是对的，但如何严格证明？

假设存在一个最优解不含贪心选择。我们把这个最优解中的元素换成贪心选择——结果不更差。

因此，贪心选择一定在某个最优解中。

如何证明贪心算法的正确性？

交换论证法：把最优解换成贪心选择，证明不更差。

贪心选择性质 + 最优子结构 → 贪心有效。

当问题缺乏最优子结构或贪心选择性质时。