个人博客

秦琦琛

0%

活动安排问题-贪心思想

发表于 更新于 分类于

活动安排问题-贪心

一、贪心

贪心算法是通过一系列的选择来得到一个问题的解，而它所做的每一次选择都是当前状态下的最好选择，即贪心选择。

即希望通过问题的局部最优解来求出整个问题的最优解。

二、问题描述

设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一个资源，如演讲会场等，而在同一时间内只有一个活动能够同时使用这一资源。每个活动i都会有一个要求使用该资源的起始时间s_i和一个结束时间f_i，且s_i<f_i。如果选择了活动i，则它在半开半闭的时间区间[s_i,f_i)内占用资源。若区间[s_i,f_i)与区间[s_j,f_j)不相交，则称活动i与活动j是相容的。也就是说，当s_i≥f_j或s_j≥f_i时，活动i与活动j相容。

活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

分析

活动i在集合b中，当且仅当b[i]的值为true。变量preIndex用来记录最近一次添加到集合b中的活动，也就是上一个已安排的活动。
算法ArrangeActivity首先选择活动(这里的活动0指按照结束时间升序排序后的第一个活动)，并将preIndex指针初始化为0，然后依次检查活动i是否与当前已经选择的所有活动相容。若相容则将活动i加入到集合b中，否则放弃，继续遍历剩余活动。
由于输入的活动按结束时间升序排序，所以算法ArrangeActivity每次总是选择具有最早完成时间的相容活动加入到集合b中。直观上，按照这种方法选择相容活动为未安排活动留下了尽可能多的时间。该算法的贪心选择意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。
最后根据数组b的值输出选中的活动编号。

贪心算法并不总能求得问题的整体最优解，但对于活动安排问题，贪心算法ArrangeActivity却总能求得整体最优解，即它最终所确定的相容内容活动集合b的规模最大。

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
struct activity{
    int start ;
    int end ;
    int index;
}

bool cmp(const struct activity &a , const struct activity &b){
    if(a.end < b.end ){
        return true ;
    }else{
        return false ;
    }
}

void ArrangeActivity(struct activity A[] , int n , bool b[]){
    //按照结束时间从小到大排序
    sort(A, a+n , cmp );
    b[0] = true ;
    int preIndex = 0 ;
    for(int i = 1 ; i < n ; i ++ ){
        if( A[preIndex].end <= A[i].start ){
            preIndex = i ;
            b[i] = ture ;
        }
    }
    //输出安排结果
    for(int i = 0 ; i < n ; i ++ ){
        if(b[i]){
            printf("%d ",i+1);
        }
    }
}