贪心算法解活动安排实验报告文档格式.doc

贪心算法解活动安排实验报告文档格式.doc

《贪心算法解活动安排实验报告文档格式.doc》由会员分享，可在线阅读，更多相关《贪心算法解活动安排实验报告文档格式.doc（4页珍藏版）》请在冰点文库上搜索。

stdio.h>

stdlib.h>

algorithm>

#defineN50

#defineTURE1

#defineFALSE0

ints[N];

/*开始时间*/

intf[N];

/*结束时间*/

intA[N];

/*用A存储所有的*/

intPartition（int*b,int*a,intp,intr）;

voidQuickSort（int*b,int*a,intp,intr）;

voidGreedySelector（intn,int*s,int*f,int*A）;

intmain（）

{

intn=0,i;

while（n<

=0||n>

50）

{

printf（"

\n"

）;

请输入活动的个数,n="

scanf（"

%d"

&

n）;

if（n<

=0）printf（"

请输入大于零的数!

"

elseif（n>

50）printf（"

请输入小于50的数!

}

printf（"

\n请分别输入开始时间s[i]和结束时间f[i]:

\n\n"

for（i=1;

i<

=n;

i++）

s[%d]="

i,i）;

scanf（"

s[i]）;

f[%d]="

f[i]）;

}

QuickSort（s,f,1,n）;

//按结束时间非减序排列

printf（"

按结束时间非减序排列如下:

/*输出排序结果*/

printf（"

\n序号\t开始时间结束时间\n"

-------------------------\n"

i++）

%d\t%d\t%d\n"

i,s[i],f[i]）;

GreedySelector（n,s,f,A）;

//贪心算法实现活动安排

安排的活动序号依次为：

if（A[i]）

printf（"

\n%d%d-->

}

system（"

pause"

return0;

//快速排序

voidQuickSort（int*b,int*a,intp,intr）

intq;

if（p<

r）

q=Partition（b,a,p,r）;

QuickSort（b,a,p,q-1）;

/*对左半段排序*/

QuickSort（b,a,q+1,r）;

/*对右半段排序*/

//产生中间数

intPartition（int*b,int*a,intp,intr）

intk,m,y,i=p,j=r+1;

intx=a[p];

y=b[p];

while

（1）

while（a[++i]<

x）;

while（a[--j]>

if（i>

=j）

break;

else

{

k=a[i];

a[i]=a[j];

a[j]=k;

m=b[i];

b[i]=b[j];

b[j]=m;

}

a[p]=a[j];

b[p]=b[j];

a[j]=x;

b[j]=y;

returnj;

voidGreedySelector（intn,int*s,int*f,int*A）

//用集合A来存储所选择的活动

A[1]=TURE;

//默认从第一次活动开始执行

intj=1;

//j记录最近一次加入到A中的活动

for（inti=2;

{

//f[j]为当前集合A中所有活动的最大结束时间

//活动i的开始时间不早于最近加入到集合A中的j的时间f[j]

if（s[i]>

=f[j]）

{

A[i]=TURE;

//当A[i]=TURE时，活动i在集合A中

j=i;

}

elseA[i]=FALSE;

}

四、运行结果

五、实验小结

贪心算法总是做出在当前看来最好的选择，也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。

活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合。

该问题要求高效地安排一系列争用某一公共资源的活动。

贪心算法提供了一个简单、漂亮的方法使得尽可能多的活动能兼容地使用公共资源。