反悔贪心#

普通贪心的特点是：做出每一步选择后都不再更改。而反悔贪心允许先暂时接受一个选择，当未来出现更优选择，或者发现资源不足的时候，再撤销、替换或重新解释过去的某个选择。

维护方式#

反悔贪心不需要暴力回溯，也不需要把所有方案搜一遍，只需要维护一个简单的数据结构，例如：

一个计数器
一个栈
一个优先队列
一个当前已选择的集合

引例#

假设有一个行李箱最多承重 10kg，下面有五件物品，重量为 $6,5,2,2,1, 1$ ，我们希望装进尽可能多件物品。

假如普通贪心，只能装下 $6,2,2$ 三个物品，实际上最优方案是 $5,2,1,1$ 或者 $2,2,1,1$ ，可以装下四个。

考虑使用反悔贪心，我们仍然先接受当前物品，但如果超重，就从已经装入的物品中扔掉最重的那个。

当前物品	暂时接受后	是否超重	反悔操作
(6)	(6)	否	无
(5)	(6,5)	是	扔掉 (6)，保留 (5)
(2)	(5,2)	否	无
(2)	(5,2,2)	否	无
(1)	(5,2,2,1)	否	无
(1)	(5,2,2,1,1)	是	扔掉 (5)

最终得到 $2,2,1,1$ ，一共装下了 $4$ 件。

这里的关键是：当资源不足时，不一定拒绝当前物品，但可能应该撤销过去代价最大的选择。

思路	做出选择后能否修改	常见操作
普通贪心	通常不能	直接接受或拒绝
反悔贪心	可以修改	删除过去最差选择、替换过去选择、延迟解释过去选择
动态规划	保存多种可能状态	同时维护多条决策路径
回溯搜索	枚举并撤销选择	尝试大量分支

反悔贪心的三种写法#

形式一：超出资源后，删除代价最大的选择#

模型：给定一些任务，每个任务消耗时间 $t_i$ 。我们希望在时间限制内完成尽可能多的任务。

策略：

遍历任务；
暂时接受当前任务；
如果总时间超限，则删除耗时最大的任务。

1
priority_queue<int> pq;
2
long long sum = 0;
3

4
for (int x : a)
5
{
6
    pq.push(x);
7
    sum += x;
8

9
    if (sum > limit)
10
    {
11
        sum -= pq.top();
12
        pq.pop();
13
    }
14
}

删除最大值的原因：因为如果必须删除一个任务，为了给未来留下尽可能多的容量，显然应当删除代价最大的任务。

形式二：遇到更优选择时，替换过去较差的选择#

模型：只能选择 $k$ 个元素，且希望总代价最小

遍历到当前元素 $x$ 时：

如果当前选择数量不足 $k$ ，直接加入；
如果已经选满，且 $x$ 比当前选中的最大值更小，则替换最大值。

1
priority_queue<int> pq;
2

3
for (int x : a)
4
{
5
    pq.push(x);
6

7
    if ((int)pq.size() > k)
8
        pq.pop();
9
}

最后堆中保留的就是最小的 $k$ 个元素。

这里的反悔思路是：先前选中的某个较差元素，被后来出现的更优元素替换。

形式三：延迟决策，未来需要时再决定过去如何解释#

例题：Problem - C2 - Codeforces

有三类朋友， $I$ 必须坐空桌， $E$ 必须坐非空桌， $A$ 可以坐任意桌。

我们看到 $A$ 时不急着决定他坐在已有桌子，还是坐在一张新桌子。而是尽量将它视作坐在已有桌子。等未来容量不足时再反悔，将此前的某个 $A$ 重新解释为坐在新桌子上，这种方案可以归类为修改过去选择的角色。