13.活动选择问题

1.问题解释

假定有n个活动要求只能在同一间教室里面举办，要求怎么安排才能使给定的任务数内做最多的活动。

输入：按每个活动完成时间排序（升序），开始时间数组S，完成时间数组F

输出：表示最大活动数的数组{X1,X2,...Xn},其中Xi=0（没选择）或者1（选择）

2.贪心选择

如上图所示，一开始先由排序结果确定第一个要做的活动，然后遍历剩下的活动，如果发现有下一个活动的举办时间发生在现有活动结束时间之后的，就记录下来，然后再遍历剩下的活动开始时间在第二个活动结束时间之后的，重复记录，多次比较后，当遍历所有活动结束后就能得到最优解。

算法伪代码：

RECURSIVE-ACTIVITY-SELECTOR(S,F,i,j)

1.    m<-i+1

2.    while m<j 且 Sm<Fi  //一开始比较的是第一个

3.      do Xm<-0

4.           m<-m+1

5.    if m<j

6.      then Xm<-1

7.              RECURSIVE-ACTIVITY-SELECTOR(S,F,m,j)

 

C:

actsel.h

#define _actsel_h
#include<stdio.h>
int *x;
void recurciveactivityselector(int *s,int *f,int i,int j){
int m=i+1;
while(m<j&&s[m]<f[i])
    x[m++]=0;
if(m<j){
x[m]=1;
recurciveactivityselector(s,f,m,j);
}
}

 

main.cpp

#include<stdlib.h>
#include"actsel.h"
#include<limits.h>
int main(){
    x=(int*)malloc(12*sizeof(int));
    int s[]={0,1,3,0,5,3,5,6,8,8,2,12,INT_MAX},
        f[]={0,4,5,6,7,8,9,10,11,12,13,14,INT_MAX},i;
    recurciveactivityselector(s,f,0,12);
    for(i=1;i<12;i++)
        printf("%d",x[i]);
    printf("\n");
    free(x);
}

输出结果：

C++：

Actselcpp.h

#define _Actselcpp_h
int* recurciveactivityselector(int *s,int *f,int i,int j){
static int*x=new int(j);
int m=i+1;
while(m<j&&s[m]<f[i])
    x[m++]=0;
if(m<j){
x[m]=1;
recurciveactivityselector(s,f,m,j);
}
return x;
}

 

main.cpp

#include<iostream>
#include"Actselcpp.h"
#include<limits>
using namespace std;
int main(){
    int *x;
    int s[]={0,1,3,0,5,3,5,6,8,8,2,12,numeric_limits<int>::max()},
        f[]={0,4,5,6,7,8,9,10,11,12,13,14,numeric_limits<int>::max()};
    x=recurciveactivityselector(s,f,0,12);
    for(int i=1;i<12;i++)
        cout<<x[i]<<" ";
    cout<<endl;
    delete []x;
}

 

JAVA:

Activityselector.java

package Jamin;

public class Activityselector {
public static int[] x;
public static void recurciveactivityselector(int[] s,int[] f,int i,int j) {
    int m=i+1;
    while(m<j&&s[m]<f[i])
        x[m++]=0;
    if(m<j) {
        x[m]=1;
        recurciveactivityselector(s,f,m,j);
    }
}
}
 

Test.java

package Jamin;

public class Test {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
Activityselector.x=new int[12];
int s[]= {0,1,3,0,5,3,5,6,8,8,2,12,Integer.MAX_VALUE},
f[]= {0,4,5,6,7,8,9,10,11,12,13,14,Integer.MAX_VALUE};
Activityselector.recurciveactivityselector(s, f, 0, 12);
for(int i=1;i<12;i++) {
    System.out.print(Activityselector.x[i]+" ");}
System.out.println();
}
}
输出结果：

1 0 0 1 0 0 0 1 0 0 1