贪心算法会场安排

⑴ 贪心算法 活动安排问题

这道题的贪心算法比较容易理解，我就不多说明了，只是提到一下算法思路1、建立数学模型描述问题。我在这里将时间理解成一条直线，上面有若干个点，可能是某些活动的起始时间点，或终止时间点。在具体一下，如果编程来实现的话，将时间抽象成链表数组，数组下标代表其实时间，该下标对应的链表代表在这个时间起始的活动都有哪些，具体参照程序注释。2、问题分解。为了安排更多的活动，那么每次选取占用时间最少的活动就好。那么从一开始就选取结束时间最早的，然后寻找在这个时间点上起始的活动，以此类推就可以找出贪心解。程序代码：#include<stdio.h>
struct inode //自定义的结构体
{
int end; //表示结束时间
inode *next; //指向下一个节点的指针
};int main()
{
inode start[10001],*pt;
int a,b,i,num=0; //num负责计数，i控制循环，a，b输入时候使用
for(i=0;i<10001;i++) //初始化
{
start[i].next=NULL;
}
while(scanf("%d %d",&a,&b)) //输入并建立数据结构
{
if(a==0&&b==0) break;
pt=new inode; //创建新的节点，然后将该节点插入相应的位置
pt->end=b;
pt->next=start[a].next;
start[a].next=pt;
}
i=0;
while(i<10001) //进行贪心算法，i表示当前时间
{
if(start[i].next==NULL)
{
i++; //该时间无活动开始
}
else
{
int temp=10001; //临时变量，存储该链表中最早的终止时间
for(pt=start[i].next;pt!=NULL;pt=pt->next)
{
if(pt->end<temp)
{
temp=pt->end;
}
}
i=temp; //将当前时间设置成前一子问题的终止时间
num++;
}
}
printf("%d\n",num); //打印结果
return 0;
}代码并不一定是最快速的，但是可以求出贪心解，如果你做的是ACM编程题目，不保证能AC注释我尽力写了，希望对你有帮助。

⑵ 贪心算法之会场安排问题

三星算法之间最好还是不要安排互相的问题，这样不利于你们俩的关系的便有好。

⑶ 贪心算法几个经典例子

贪心算法经典例子如下：

活动安排问题是可以用贪心算法有效求解的一个很好的例子，该问题要求高效地安排一系列争用某一公共资源的活动。贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。

设有n个活动的集合e=（1，2，…，n），其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi，且si<fi。如果选择了活动i，则它在半开时间区间（si，fi）内占用资源。

活动安排问题

若区间（si，fi）与区间（sj，fj）不相交，则称活动i与活动j是相容的。也就是说，当si≥fi或sj≥fj时，活动i与活动j相容。活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

在下面所给出的解活动安排问题的贪心算法gpeedyselector中，各活动的起始时间和结束时间存储于数组s和f中且按结束时间的非减序：f1≤f2≤…≤fn排列。如果所给出的活动未按此序排列，我们可以用o（nlogn）的时间将它重排。

⑷ 请高手进来解答一下这道算法设计与分析的题目，谢谢了！！

设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<fi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。

在下面所给出的解活动安排问题的贪心算法greedySelector:

publicstaticintgreedySelector(int[]s,int[]f,booleana[])

{

intn=s.length-1;

a[1]=true;

intj=1;

intcount=1;

for(inti=2;i<=n;i++){

if(s[i]>=f[j]){

a[i]=true;

j=i;

count++;

}

elsea[i]=false;

}

returncount;

}

由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。

算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。

例：设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下：

i 1 2 3 4 5 6 7 8 9 10 11

S[i] 1 3 0 5 3 5 6 8 8 2 12

f[i] 4 5 6 7 8 9 10 11 12 13 14