首页  >  文章  >  php教程  >  活动选择问题,活动选择

活动选择问题,活动选择

WBOY
WBOY原创
2016-06-13 08:51:241417浏览

活动选择问题,活动选择

问题描述:

设有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si

从图中可以看出S中共有11个活动,最大的相互兼容的活动子集为:{a1,a4,a8,a11,}和{a2,a4,a9,a11}。

2、动态规划解决过程

(1)活动选择问题的最优子结构

定义子问题解空间Sij是S的子集,其中的每个获得都是互相兼容的。即每个活动都是在ai结束之后开始,且在aj开始之前结束。

为了方便讨论和后面的计算,添加两个虚构活动a0和an 1,其中f0=0,sn 1=∞。

结论:当i≥j时,Sij为空集。

如果活动按照结束时间单调递增排序,子问题空间被用来从Sij中选择最大兼容活动子集,其中0≤i<j≤n 1,所以其他的Sij都是空集。

最优子结构为:假设Sij的最优解Aij包含活动ak,则对Sik的解Aik和Skj的解Akj必定是最优的。

通过一个活动ak将问题分成两个子问题,下面的公式可以计算出Sij的解Aij

(2)一个递归解

  设c[i][j]为Sij中最大兼容子集中的活动数目,当Sij为空集时,c[i][j]=0;当Sij非空时,若ak在Sij的最大兼容子集中被使用,则则问题Sik和Skj的最大兼容子集也被使用,故可得到c[i][j] = c[i][k] c[k][j] 1。

当i≥j时,Sij必定为空集,否则Sij则需要根据上面提供的公式进行计算,如果找到一个ak,则Sij非空(此时满足fi≤sk且fk≤sj),找不到这样的ak,则Sij为空集。

c[i][j]的完整计算公式如下所示:

亲测代码:

1 #include 2 #define max_size 10010 3 int s[max_size]; 4 int f[max_size]; 5 int c[max_size][max_size]; 6 int ret[max_size][max_size]; 7 8 使用 命名空间 std; 9 10 void DP_SELECTOF(int *s,int *f,int n,int c[][max_size],int ret[][max_size]) 11 { 12 int i,j,k; 13 int 温度; 14 对于(j=2;j) 15 对于(i=1;i) 16 { 17 对于(k=i 1;k) 18 { 19 if(s[k]>=f[i]&&f[k]s[j]) 20 { 21 temp=c[i][k] c[k][j] 1; 22 if(c[i][j]temp) 23 { 24 c[i][j]=温度; 25 ret[i][j]=k; 26 } 27 } 28 } 29 } 30 } 31 32 int main() 33 { 34 int n; 35 printf("输入活动数 n: "); 36 同时(~scanf("%d",&n) ) 37 { 38 memset(c,0,sizeof(0)); 39 memset(ret,0,sizeof(ret)); 40 printf("n输入活动开始以及结束时间n"); 41 int i,j; 42 对于 (i=1;i) 43 { 44 scanf("%d%d",&s[i],&f[i] ); 45 } 46 DP_SELECTOF(s,f,n,c,ret); 47 printf("最大子集的个数=%dn",c[1][n] 2); 48 返回 0; 49 } 查看代码

下面是贪心法的代码:

  

1 #include 2 #define max_size 10010 3 int s[max_size]; 4 int f[max_size]; 5 int ret[max_size]; 6 int c[max_size][max_size]; 7 使用 命名空间 std; 8 9 void GREEDY_ACTIVITY_SELECTOR(int *s,int *f,int n,int *ret) 10 { 11 int k,m; 12 *ret =1; 13 k=1; 14 对于(m=2;m) 15 如果(s[m]>=f[k]) 16 { 17 *ret =米; 18 k=米; 19 } 20 } 21 int main() 22 { 23 int n; 24 printf("输入活动数 n: "); 25 同时(~scanf("%d",&n) ) 26 { 27 memset(s,0,sizeof(s)); 28 memset(f,0,sizeof(f)); 29 memset(c,0,sizeof(0)); 30 memset(ret,0,sizeof(ret)); 31 printf("n输入活动开始以及结束时间n"); 32 int i,j; 33 对于 (i=1;i) 34 { 35 scanf("%d%d",&s[i],&f[i] ); 36 } 37 GREEDY_ACTIVITY_SELECTOR(s,f,n,ret); 38 对于 (i=0;i) 39 { 40 if(ret[i]!=0) 41 printf("a%d ",ret[i]); 42 } 43 printf("n"); 44 } 45 } 查看代码

 

声明:
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn