交换论证

一句话理解

交换论证：证明存在最优解可以一步步换成贪心解。

为什么要学

贪心正确性的常见证法。

讲解

假设最优解和贪心在第一处不同，交换后不变差，于是可变成贪心。

例子

活动安排：把最优解里第一个不同的活动换成结束更早的。

常见错误

• 交换后变差还硬说正确。
• 不会写证明就当对。