贪心算法，动态规划 源码解析

贪心算法讲解例题：活动选择问题问题描述

有一个需要使用每个资源的n个活动组成的集合S= {a1，a2，···，an },资源每次只能由一个活动使用。每个活动a都有一个开始时间和结束时间，且 0<= s < f < 。一旦被选择后，活动a就占据半开时间区间[s,f]。如果[s,f]和[s,f]互不重叠，则称两个活动是兼容的。该问题就是要找出一个由互相兼容的活动组成的最大子集。

11个活动按结束时间排序好，之后为：

s[]={1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12}; //开始时间

f[]={4, 5, 6, 7, 8, 9,10,11,12, 13,14}; //结束时间（递增）

动态规划求解：O(n3)

#include"stdio.h"
int c[13][13];//活动的个数 用来表示 从 i 到 j 符合规则的有几个活动
int partition[13][13];//partition[i][j] 表示 使用哪个k 使得s[i][j]到最大兼容集合

void dynamic_Activity_select(int s[],int f[],int n)
{
int i,j,k;
for(i=0;i<=n;i++)//初始化 情况下 没有一个活动
for(j=0;j<=n;j++)
{
if(i==j)
c[i][j]=1;// 这个地方其实很关键 ，往往 贪心求解时 初始化容易初始化为 0
else
c[i][j]=0;
}

for(i=1;i<=n;i++)
{
for(j=2;j<=n;j++)
{
if(i>=j) //前面的 活动不能超过后面的活动
c[i][j]=0;
else
{
for(k=i+1;k<=j-1;k++) //从前面的下一个 活动开始
{
if(s[k] >= f[i] && f[k] <= s[j])// k 开始后 i 结束 k 结束 s 还没有开始
if(c[i][j]<c[i][k]+c[k][j]+1)
{
c[i][j]=c[i][k]+c[k][j]+1;
partition[i][j]=k;
}
}
}
}
}
}

int main()
{
int s[]={0,1,3,0,5,3,5,6,8,8,2,12}; //这个地方容易出错
int f[]={0,4,5,6,7,8,9,10,11,12,13,14};
dynamic_Activity_select(s,f,11);
int m=11;
int n=11;

for(int i=1;i<n;i++) //这里可以自定义输出
{
for (int j=1;j<m;j++)
printf("%3d", partition[i][j]);

printf("\n");
}
}<wbr></wbr>

由于动态规划时间复杂度高，用来求解这类问题，大材小用。所以提供以下贪心算法

#include"stdio.h"

void recursive_activity_select(int s[],int f[],int i,int n)//递归的贪心算法
{
int m=i+1;
while(m<=n&&s[m]<f[i]) //找出第一个符合条件的 （有时候第一个并不是符合条件的）
m++;

if(m<=n)
{
printf("%4d",m);
recursive_activity_select(s,f,m,n);

}
else
return ;

}
/*这个方法思想：寻找最早结束且与前一个 兼容的 活动加入集合 i 在前 m 在后*/
void greedy_activity_select(int s[],int f[],int n)//迭代方法
{
int i=1;
/*由于是按照最早结束时间来排序 所以第一个肯定是最早结束的活动*/
printf("%4d",1);
for(int m=2;m<=n;m++) //也可以按照递归方法 中使用 while 循环（一个道理）
{
if(s[m]>=f[i])
{
printf("%4d",m);
i=m;
}
}
}
int main()
{
int s[]={0,1,3,0,5,3,5,6,8,8,2,12}; //这个地方容易出错
int f[]={0,4,5,6,7,8,9,10,11,12,13,14};
printf("要选择的活动为：");
// recursive_activity_select(s,f,0,11);//之所以注释掉 是因为跟下面的方法重复 一次只能调试一个
greedy_activity_select(s,f,11);
}

评论这张

转发至微博

转发至微博