贪心算法 —— 跟WilliamYan一起学算法

大家好!欢迎来到《跟WilliamYan一起学算法》。今天我们来讲解贪心算法。贪心算法在解简单的背包问题和线段覆盖问题时是非常有用的。

仅在没有后向性的情况下才能使用贪心算法

定义

贪心算法(Greedy algorithm)是一种对某些求最优解问题的更简单、更迅速的设计技术。用贪心算法设计算法的特点是一步一步地进行,常以当前情况为基础根据某个优化测度作最优选择,而不考虑各种可能的整体情况,它省去了为找最优解要穷尽所有可能而必须耗费的大量时间,它采用自顶向下,以迭代的方法做出相继的贪心选择,每做一次贪心选择就将所求问题简化为一个规模更小的子问题,通过每一步贪心选择,可得到问题的一个最优解,虽然每一步上都要保证能获得局部最优解,但由此产生的全局解有时不一定是最优的,所以贪心算法不要回溯。 (via 360百科

例题

排队接水

题目要求说要平均等待时间最短,也就是总等待时间最短。所以令接水需求最小的人排在前面,最大的排在后面。

证明:对于任意 $T_1 ,…… ,Tk,T{k+1},…..,Tn(1\leq k<k+1\leq n)$ 若 $T{k+1} < T_{k}$ 将两者互换,则 $Tk$ 前总等待时间不变,$T{k+1}$ 后总等待时间不变,$Tk$ 与 $T{k+1}$等待时间变小,由此可证由接水时间升序排列时总等待时间最短。


合并果子(NOIP 2004)

这道题只需要每次把最小的两个果堆加起来就可以了.

证明:略 我懒了(好吧别打我!画合并树就好了!)


纪念品分组

该题有多种贪心策略。

  1. 如果最轻的+最重的<限制,两者分一组,否则最重的单独一组。
  2. 最重的和能与它匹配的最重的分一组

删数问题

找最大的k个数显然是错的,$n^2$的做法是相邻位两两比较,删去较大的。

正解是每次从左往右扫,如果数字递增,就删最后一个,否则删掉第一个递减区间的第一位,重复k次,复杂度$k$,注意特判前导0.

证明:略 (怎么又略啊喂!)


其他经典问题

  1. 有若干个闭区间,求最多的不相交区间

    分析: 我们就是想提高教室地利用率,尽可能多地安排活动。

    考虑容易想到的几种贪心策略:

    (1) 开始最早的活动优先,目标是想尽早结束活动,让出教室。

    然而, 这个显然不行,因为最早的活动可能很长,影响我们进行后面的活动。例如活动开始和结束时间分别为[0, 100), [1,2) ,[2, 3), [3, 4),[4,5],安排[0,100)的这个活动之后,其他活动无法安排,可是最优解是安排除它外的4个活动。

    (2) 短活动优先, 目标也是尽量空出教室。但是不难构造如下反例: [0,5) [5,10) [3, 7), 这里[3,7)最短,但如果我们安排了[3,7),其它两个无法安排了。但是最优解显然是安排其它两个,而放弃[3,7),可见这个贪心策略也是不行的。

    (3) 最少冲突的活动优先, 既然上面安排活动是想减少冲突,那么如果我们优先安排冲突最少的活动可以么?至少从(1)和(2)看来,这个策略是有效的。真是对的么? 尝试这个例子:

    [0,2) [2,4) [4,6) [6,8)
    [1,3) [1,3) [1,3) [3,5) [5,7) [5,7) [5,7)

    看一下[0,2) 和3个活动冲突——3个[1,3)

    [2,4)和4个活动冲突3个[1,3)和一个[3,5)
    [4,6)和也和4个活动冲突3个[5,7)和一个[3,5)
    [6,8)和3个活动冲突——3个[5,7)

    下面[1,3)和[5,7)每个都和5个活动冲突,
    而[3,5)只和两个活动冲突——[2,4)和[4,6)。

    那按照我们的策略应该先安排[3,5), 可是一旦选择了[3,5),我们最多只可能安排3个活动。
    但明显第一行的4个活动都可以安排下来,所以这种策略也是不对的。

    (4) 看似最不对的策略——结束时间越早的活动优先。这个策略是有效的,我们可以证明。假设最优解OPT中安排了m个活动,我们把这些活动也按照结束时间由小到大排序,显然是不冲突的。假设排好顺序后,这些活动是a(1) , a(2), a(3)….am

    假设按照我们的贪心策略,选出的活动自然是按照结束时间排好顺序的,并且也都是不冲突的,这些活动是b(1), b(2) …b(n)

    问题关键是,假设a(1) = b(1), a(2) = b(2)…. a(k) = b(k),但是a(k+1) != b(k+1),回答几个问题:

    (1)b(k+1)会在a(k+2), a(k+3), …. a(m)中出现么?
    不会。因为b(k+1)的结束时间是最早的,即f(b(k+1)) <= f(a(k+1)),而a(k+2), a(k+3), …. a(m)的开始时间和结束时间都在f(a(k+1))之后,所以b(k+1)不在其中。

    (2)b(k+1)和a(1), a(2), …. a(k) 冲突么?
    不冲突,因为a(1), a(2), …. a(k)就是b(1), b(2), …. b(k)

    (3)b(k+1)和a(k+2), a(k+3), …. a(m)冲突么?
    不冲突,因为f(b(k+1)) <= f(a(k+1)),而a(k+2), a(k+3), …. a(m)的开始时间都在f(a(k+1))之后,更在f(b(k+1))之后。

    因此我们可以把a(k+1) 换成b(k+1), 从而最优解和我们贪心得到的解多了一个相同的,经过一个一个替换,我们可以把最优解完全替换成我们贪心策略得到的解。 从而证明了这个贪心策略的最优性。

    最后,我们来提供输入输出数据,由你来写一段程序,实现这个算法。

输入

第1行:1个数N,线段的数量(2 <= N <= 10000)
第2 – N + 1行:每行2个数,线段的起点和终点(-10^9 <= S,E <= 10^9)

输出

输出最多可以选择的线段数量。

输入示例

3
1 5
2 3
3 6

输出示例

2

代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 1e4+10;
const int INF = 0x3f3f3f3f;

struct D{
    int S,E;
    bool operator <(const struct D &b)const{
        return E < b.E;
    }
}board[MAXN];

int main(){

    int N;
    while(scanf("%d",&N) == 1){
        for(int i=1 ; i<=N ; ++i){
            scanf("%d %d",&board[i].S,&board[i].E);
        }
        sort(board+1,board+1+N);
        int sum = 0;
        int t = -INF;
        for(int i=1 ; i<=N ; ++i){
            if(board[i].S >= t){
                ++sum;
                t = board[i].E;
            }
        }
        printf("%d\n",sum);
    }

    return 0;
}
  1. 有若干活动,每个活动的时间是一个闭区间,每个活动都需要借用一个教室,求最少需要的教室总数。

    分析:能否按照之一问题的解法,每个教室安排尽可能多的活动,即按结束时间排序,再贪心选择不冲突的活动,安排一个教室之后,剩余的活动再分配一个教室,继续贪心选择……

    反例: A:[1,2) B:[1,4) C:[5,6) D:[3,7)

    已经按结束时间排好顺序,我们会选择
    教室1: A C
    教室2: B
    教室3: D
    需要3个教室。
    但是如果换一种安排方法,我们可以安排AD在一个教室,而BC在另外一个教室,两个教室就够了。

    所以之前的贪心策略解决不了这个问题。

    怎么办?之前的策略是用一个教室找所有它能安排下的活动,即用教室找活动,我们能不能用活动找教室呢?

    策略: 按照开始时间排序优先安排活动,如果冲突,则加一个教室。
    简单地理解一下,策略是这样,我们把活动按照开始时间有小到大的顺序排序。假设目前已经分配了k个教室(显然k初始等于0),对于当前这个活动,
    (1) 如果它能安排在k个教室里的某一个,则把它安排在其中的任何一个教室里,k不变。
    (2) 否则它和每个教室里的活动都冲突,则增加一个教室,安排这个活动。

    这个策略是最优么?

    我们想像一下k增加1的过程: 因为我们是按照开始时间排序的,意味着当前考虑的这个活动开始的时候,k个教室里都有活动没结束(因为如果有一个教室的活动结束了,我们就可以安排这个活动进入那个教室而不冲突,从而不用增加k)。这就意味着在这个活动开始的时间点,算上目前考虑的这个活动,有(k + 1)个活动正在进行,同一时刻有(k + 1)个活动在进行,无论我们如何安排教室,都至少需要(k + 1)个教室。因为每个教室里不能同时进行两个活动。而我们的策略恰好需要(k + 1)个教室,所以是最优的。

    这个策略也告诉我们,如果从时间轴上“宏观”考虑这个问题。考虑每个时间点同时进行的活动个数,作为这个时间点的厚度(把活动开始和结束时间想像成线段,那么每个时间点有多少条线段覆盖它,可以简单理解为“厚度”),我们至少需要最大厚度那么多个教室——因为那时恰好有最大厚度那么多个活动同时进行,而我们这个贪心策略恰好给了我们一个用最大厚度那么多个教室安排全部活动的一个方案。

    如果只需要教室的个数,我们可以把所有开始时间和结束时间排序,遇到开始时间就把厚度加1,遇到结束时间就把厚度减1,显然最初始和最后结束时的厚度是0,在一系列厚度变化的过程中,峰值(最大值)就是最多同时进行的活动数,也是我们至少需要的教室数。

    最后,我们来提供输入输出数据,由你来写一段程序,实现这个算法。

输入

第一行一个正整数n (n <= 10000)代表活动的个数。
第二行到第(n + 1)行包含n个开始时间和结束时间。
开始时间严格小于结束时间,并且时间都是非负整数,小于1000000000

输出

一行包含一个整数表示最少教室的个数。

输入示例

3
1 2
3 4
2 9

输出示例

2

代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 1e4+10;

struct D{
    int V;
    int flag;
    bool operator <(const struct D &b)const{
        return V < b.V;
    }
}board[MAXN*2];

int Re[MAXN*2];

int main(){

    int N;
    while(scanf("%d",&N) == 1){
        for(int i=1 ; i<=N*2 ; i+=2){
            scanf("%d %d",&board[i].V,&board[i+1].V);
            board[i].flag = 1;
            board[i+1].flag = -1;
        }
        sort(board+1,board+1+N*2);
        for(int i=N*2 ; i>0 ; --i){
            if(board[i].V == board[i-1].V){
                board[i-1].flag += board[i].flag;
                board[i].flag = 0;
            }
        }
        for(int i=1 ; i<=N*2 ; ++i){
            Re[i] = board[i].flag;
        }
        int ma = 0;
        int t = 0;
        for(int i=1 ; i<=N*2 ; ++i){
            t += Re[i];
            if(t > ma)ma = t;
        }
        printf("%d\n",ma);
    }

    return 0;
}

参考:51NOD贪心教程(活动安排典型题+详细解析) 作者:Assassin_poi君

总结

贪心算法是指在对问题求解时总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,作出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择。必须注意的是,贪心算法不是对所有问题都能得到整体最优解,选择的贪心策略必须具备无后效性,即某个状态以后的过程不会影响以前的状态,只与当前状态有关。
所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。
很显然,它有目光短浅的问题,但是在我们证明了策略没有后向性后,便可以放心大胆的使用贪心算法了。

© 2019 William Yan

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据