反悔贪心
先维护一个可行解,用堆、链表或残余结构保存反悔项;出现更优交换时替换旧选择,正确性由交换论证保证。标签 算法 / 贪心 / 反悔贪心 / 堆 / 交换论证
问题形式
设 有限, 对子集封闭,。按 的全序 处理,维护 。加入 后若 ,允许删除或替换 中若干元素;目标是最小化
核心思想
对每个 记录反悔项 :移除 可节省的代价;简单情形 。处理 时,比较 与最大的 ;若
满足 且 ,就执行替换。堆、链表和残余网络维护这些交换选项。
堆实现通常为 ,空间 ;具体复杂度取决于交换结构。
正确性
反悔贪心仍要求安全选择:每次替换得到的 必须包含于某个最优解。证明使用交换论证;拟阵是 的一类充分结构,不是必要条件。
单机最小逾期任务是反悔贪心的标准实例,见 最小逾期任务。
易错点
- 堆中存的常是变换后的反悔项,不是 本身。
- 一次替换可能不足以恢复可行,需要多步增广。
- 只按 贪心可能错,必须比较反悔项。
- 相同键、不可行状态和终止条件需要单独处理。