算法基础算法

反悔贪心与反悔堆的思想，带截止时间的任务选择问题

字数统计: 2.8k字   |   阅读时长: 10分
,

摘要: 反悔贪心的思想，带截止时间的任务选择问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

对于具有最优子结构的问题，如果整体最优解可通过一系列局部最优解的选择达到，并且每次选择可以依赖以前作出的选择，但不依赖于后面要作出的选择，称该问题具有贪心选择性质，可以用贪心算法解决。

当问题不具备贪心选择性质时，如果还按照贪心选择，则选到的局部最优解可能不是全局最优解，此时就不能用贪心解决，但在某些问题中，可以通过反悔操作将局部最优解纠正到全局最优解上，也就是当我们发现此前所做的若干选择并不是全局最优解时，反悔此前的一个或多个选择，使得结果更好。这是反悔贪心的大致思路。

根据反悔操作的不同，可以用不同的数据结构维护反悔贪心算法，其中堆是最常见的一种。本文我们通过带截止时间的任务选择问题来看一下这种通过堆来维护反悔贪心的做法。

抽象问题：从 N 个对象中选出若干个

假设有 N 个对象，我们要从中选出若干个对象，满足一些约束条件，同时最优化某个指标。

枚举这 N 个对象，每轮枚举的过程如下：

  • step1: 放出一个对象（即当前枚举的对象）进入候选集；
  • step2: 根据约束条件和最优化指标，如果有必要，则从候选集淘汰一个（如果淘汰的是当前枚举的对象，则相当于跳过当前对象；如果淘汰的是此前枚举的对象，相当于反悔操作）。

候选集中的对象始终是取到局部最优解的选择，每次候选集出现变化，都相当于取到一个新的局部最优解，在这些取到的局部最优解中取一个最好的作为全局最优解的答案。但注意，全局最优解一定出现在这些局部最优解中这件事需要证明。

从反悔贪心的角度理解上述流程就是：一个对象如果满足进候选集的约束条件，就先让它进，后续当我们找到不满足进候选集的条件但能使得最优化指标变得更好的对象时，就放弃候选集中的某个对象使得当前对象可以进，放弃候选集中的对象就相当于一次反悔。

在放弃对象时，放弃那个对最优化的指标贡献最小的，这样就可以用堆来维护已选择的对象，对最优化指标贡献最小的放在堆顶，构成最小堆。

这就是用堆维护反悔贪心的场景，根据约束条件和最优化指标的不同，会有很多种不同的问题，下面我们来看一下带截止时间的任务选择问题，大致描述如下：

有 N 个任务，每个任务有一个持续时间和一个价值，同一时间只能做一个任务，从 N 个任务重中选择若干个任务去做，使得每个任务都在截止时间前做完，问最大价值。

耗时相同、价值不同

下面两个问题本质上完全相同，代码可以共用，我们放到一起看。

每项工作花一单位时间，工作日从 0 时刻开始，共有 1e9 单位时间。

在任一时刻，可以选择编号 1 到 N 的 N 项工作中的任意一项完成，每单位时间只能做一项。

每项工作都有截止时间，因此不一定能完成所有 N 个工作。对于第 $i$ 个工作，截止时间为 $D_{i}$，如果能完成该工作则可以获利 $P_{i}$。

求能够获得的最大利润。

超市里有 N 件商品，每件商品都有利润 pi 和过期时间 di，每天只能卖一件商品，过期商品不能再卖。

求合理安排每天卖的商品的情况下，可以得到的最大收益是多少。

算法：反悔贪心

反悔贪心的思想是：一个商品如果有时间卖，就先卖了（即选择该商品），当我们找到一个没时间卖但利润更高的商品时，就放弃此前已选择商品中利润最低的，而改卖这个利润更高的商品。这步放弃就相当于一次反悔。

首先将 N 件商品按照截止时间排序，然后从前到后枚举，过程中用一个最小堆维护已选择工作的利润。具体细节如下：

对象池中有 N 件商品，每件商品有一个利润 p 和一个截止时间 d：

1
2
3
4
5
6
struct Item
{
    int p;
    int d;
    Item(int p, int d):p(p),d(d){}
};

按照过期时间从前到后枚举物品，这样候选集中商品的过期时间均小于等于当前枚举的商品。

首先将当前枚举的商品压入堆中，相当选择了当前商品，当前已选商品数就加 1，如果当前已选商品数小于等于当前枚举商品的过期时间，则不需要淘汰。

如果当前已选商品数大于当前枚举的结束时间，就需要从候选集中淘汰一个。因为要最大化的是利润，所以参选的对象(过期时间小于等于当前枚举值)中，保留的物品利润越大越好。

这样堆中的比较规则如下（最小堆）：

1
2
3
4
5
6
7
struct HeapCmp
{
    bool operator()(const Item& i1, const Item& i2) const
    {
        return i1.p > i2.p;
    }
};

代码 (C++)

以下代码是题目 145. 超市 的，题目 P2949 [USACO09OPEN] Work Scheduling G 的代码在此基础上简单修改下输入输出和精度即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <queue>

using namespace std;

struct Item
{
    int p;
    int d;
    Item(int p, int d):p(p),d(d){}
};

struct Cmp
{
    bool operator()(const Item& i1, const Item& i2) const
    {
        return i1.d < i2.d;
    }
};

struct HeapCmp
{
    bool operator()(const Item& i1, const Item& i2) const
    {
        return i1.p > i2.p;
    }
};

int main()
{
    int N;
    while(cin >> N)
    {
        vector<Item> items;
        for(int i = 0; i < N; ++i)
        {
            int p, d;
            cin >> p >> d;
            items.emplace_back(p, d);
        }
        sort(items.begin(), items.end(), Cmp());
        priority_queue<Item, vector<Item>, HeapCmp> pq;
        int left = 0;
        int ans = 0;
        for(const Item& i: items)
        {
            pq.push(i);
            ++left;
            ans += i.p;
            if(left > i.d)
            {
                ans -= pq.top().p;
                pq.pop();
                --left;
            }
        }
        cout << ans << endl;
    }
}

耗时不同、价值相同

这里有 n 门不同的在线课程，按从 1 到 n 编号。给你一个数组 courses ，其中 courses[i] = [durationi, lastDayi] 表示第 i 门课将会 持续 上 durationi 天课，并且必须在不晚于 lastDayi 的时候完成。

你的学期从第 1 天开始。且不能同时修读两门及两门以上的课程。

返回你最多可以修读的课程数目。

示例 1：
输入：courses = [[100, 200], [200, 1300], [1000, 1250], [2000, 3200]]
输出：3
解释：
这里一共有 4 门课程，但是你最多可以修 3 门：
首先，修第 1 门课，耗费 100 天，在第 100 天完成，在第 101 天开始下门课。
第二，修第 3 门课，耗费 1000 天，在第 1100 天完成，在第 1101 天开始下门课程。
第三，修第 2 门课，耗时 200 天，在第 1300 天完成。
第 4 门课现在不能修，因为将会在第 3300 天完成它，这已经超出了关闭日期。

示例 2：
输入：courses = [[1,2]]
输出：1

示例 3：
输入：courses = [[3,2],[4,3]]
输出：0

提示:

1
2
1 <= courses.length <= 1e4
1 <= durationi, lastDayi <= 1e4

算法：反悔贪心

在上面的用时相同，价值不同的问题中，我们用堆维护性价比最低的任务，也就是价值最低的任务，用于反悔操作。

这里是用时不同，价值相同的问题，依然可以用堆维护性价比最低的任务，即耗时最长的任务，如果不做耗时长的任务而去做耗时短的任务，就可以留更多时间给后续的任务。

因此本题的反悔贪心的思想是：一个任务如果有时间做，就先做了（即选择该任务），当我们找到一个没时间做但耗时更短的任务时，就放弃此前已选择任务中耗时最长的，而改做这个耗时更短的任务。这步放弃就相当于一次反悔。

首先将 N 个任务按照截止时间排序，然后从前到后枚举，过程中用一个最大堆维护已选择工作的利持续市场。具体细节如下：

对象池中有 N 门课，每门课有一个持续时长 t 和一个截止时间 d：

1
2
3
4
5
6
struct Course
{
    int t;
    int d;
    Course(int t, int d):t(t),d(d){}
};

按照过期时间从小到大枚举课程，这样候选集中课的过期时间均小于等于当前枚举的课。

首先将当前枚举的课 item 压入堆中，相当选择了当前课，当前已选课的总时间就加 item.t，如果当前已选课的总时间小于等于当前枚举课的过期时间，则不需要淘汰。

如果当前已选课的总时间大于当前枚举的课的结束时间，就需要从候选集中淘汰一个性价比最低的，即从参选的对象(过期时间小于等于当前枚举值)中，淘汰持续时间最长的。

这样堆中的比较规则如下（最大堆）：

1
2
3
4
5
6
7
struct HeapCmp
{
    bool operator()(const Course& c1, const Course& c2) const
    {
        return c1.t < c2.t;
    }
};

代码 (C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
struct Course
{
    int t;
    int d;
    Course(int t, int d):t(t),d(d){}
};

struct Cmp
{
    bool operator()(const Course& c1, const Course& c2) const
    {
        return c1.d < c2.d;
    }
};

struct HeapCmp
{
    bool operator()(const Course& c1, const Course& c2) const
    {
        return c1.t < c2.t;
    }
};

class Solution {
public:
    int scheduleCourse(vector<vector<int>>& courses) {
        int n = courses.size();
        vector<Course> cs;
        for(int i = 0; i < n; ++i)
            cs.emplace_back(courses[i][0], courses[i][1]);
        sort(cs.begin(), cs.end(), Cmp());
        priority_queue<Course, vector<Course>, HeapCmp> pq;
        int left = 1;
        for(const Course& c: cs)
        {
            pq.push(c);
            left += c.t;
            if(left - 1 > c.d)
            {
                left -= pq.top().t;
                pq.pop();
            }
        }
        return pq.size();
    }
};
Share