欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

活动选择问题,活动选择_PHP教程

程序员文章站 2022-05-17 15:03:48
...

活动选择问题,活动选择

问题描述:

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

活动选择问题,活动选择_PHP教程

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

2、动态规划解决过程

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

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

活动选择问题,活动选择_PHP教程

为了方便讨论和后面的计算,添加两个虚构活动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

活动选择问题,活动选择_PHP教程

(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]的完整计算公式如下所示:

活动选择问题,活动选择_PHP教程

亲测代码:

活动选择问题,活动选择_PHP教程活动选择问题,活动选择_PHP教程 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 using namespace 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 temp; 14 for(j=2;j)

相关标签: 选择性