贪心算法讲解例题:活动选择问题问题描述
有一个需要使用每个资源的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);
}
相关推荐
基于C语言实现贪心算法背包问题动态规划源码.zip基于C语言实现贪心算法背包问题动态规划源码.zip基于C语言实现贪心算法背包问题动态规划源码.zip基于C语言实现贪心算法背包问题动态规划源码.zip基于C语言实现贪心...
贪心算法、分治算法和动态规划的区别 贪心算法和动态规划.pdf
贪心算法和动态规划以及分治法的区别? (1) 贪心算法和动态规划.pdf
【数据结构】贪心算法和动态规划 贪心算法和动态规划.pdf
贪心算法和动态规划(Java实现) 贪心算法和动态规划.pdf
贪心算法和动态规划的区别与联系 贪心算法和动态规划.pdf
会议安排(贪心算法和动态规划) 贪心算法和动态规划.pdf
贪心算法和动态规划以及分治法的区别? 贪心算法和动态规划.pdf
基于C语言实现贪心算法背包问题源码.zip基于C语言实现贪心算法背包问题源码.zip基于C语言实现贪心算法背包问题源码.zip基于C语言实现贪心算法背包问题源码.zip基于C语言实现贪心算法背包问题源码.zip基于C语言实现...
动态规划和贪心算法的区别 贪心算法和动态规划.pdf
主要针对贪心算法原理及实现和在动态规划中的应用
动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法动态规划算法与贪心算法
算法分析与设计实验-基于Vue3和Typescript实现的排序、动态规划、贪心算法、检索源码.zip算法分析与设计实验-基于Vue3和Typescript实现的排序、动态规划、贪心算法、检索源码.zip算法分析与设计实验-基于Vue3和...
网上搜的贪心算法和动态规划算法课件,主要分析了这两类算法的解法。包括:程序员代码面试指南-第四章递归和动态规划[牛客试网试读版],7.贪心法和动态规划。
活动安排问题的动态规划、贪心算法和树搜索算法求解。 比如有一个多媒体教室,现在有四个待举办活动A、B、C、D。A是在8:00到10:00举行,简单记为[8, 10];B是[12, 14];C是[15, 17];D是[11, 19]。为了让尽可能多的...
动态规划算法-多边形游戏。回溯法-符号三角形问题。贪心算法-计算加油次数。包括流程图+代码+实验结果截屏+实验总结。
贪心算法 贪心算法 贪心算法 贪心算法 贪心算法 贪心算法
有关动态规划和贪心的算法,新手可以看看!我是新手!
贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法贪心算法
ES6的JavaScript算法思想实现之分而治之,动态规划,贪心算法和回溯算法 贪心算法和动态规划.pdf