贪心算法解决会场安排问题、多处最优服务次序问题(含源代码)

西安邮电大学（计算机学院）课内实验报告实验名称：贪心算法专业名称：计算机科学与技术班级：学生姓名：学号（8位）：指导教师：实验日期：2014年5月22日一．实验目的及实验环境实验目的：通过实际应用熟悉贪心算法，并解决会场安排问题、多出最优服务次序问题实验环境：VisualC++6.0二.实验内容1.会场安排问题.假设要在足够多的回厂里安排一批活动，并希望使用尽可能少的会场，设计一个有效的贪心算大进行安排（这个问题实际上是注明的图着色问题。若将每一个活动作为图的一个顶点，不相容活动间用边相连。使相邻顶点着有不同颜色的最小着色数，相应于要找的最小会场数）2.多处最优服务次序问题设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti，1=i=n。共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以n。三．方案设计1、设有n个活动的集合E={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且sifi。如果选择了活动i，则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交，则称活动i与活动j是相容的。也就是说，当si≥fj或sj≥fi时，活动i与活动j相容。由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。1.会场安排问题源代码#includeiostream#includevector#includealgorithmusingnamespacestd;structpoint{intt;boolf;};boolcmp(pointx,pointy){returnx.ty.t;}intgreedy(vectorpointx){intmax=0,cur=0,n=x.size();sort(x.begin(),x.end(),cmp);for(inti=0;in;i++){if(x[i].f)cur++;elsecur--;if(curmax)max=cur;}returnmax;}intmain(){vectorpointx;intn,i;pointtemp;while(cinn,n){for(i=0;in;i++){temp.f=true;cintemp.t;x.push_back(temp);temp.f=false;cintemp.t;x.push_back(temp);}coutgreedy(x)endl;x.clear();}return0;}2.多处最优服务次序问题源代码：#includestdio.h#includestdlib.hmain(){int**window,*timewindow,*array,num,serve,i,j,k,temp;doublemin;printf(请输入等待服务人数\n);scanf(%d,&num);printf(请输入服务窗口数\n);scanf(%d,&serve);array=(int*)malloc((num+1)*sizeof(int));timewindow=(int*)malloc((serve+1)*sizeof(int));window=(int**)malloc((serve+1)*sizeof(int*));for(i=0;i=serve;i++)window[i]=(int*)malloc((num+1)*sizeof(int*));printf(请依次输入服务等待时间\n);for(i=1;i=num;i++)scanf(%d,&array[i]);for(i=0;i=serve;i++){timewindow[i]=0;for(j=0;j=num;j++)window[i][j]=0;}for(i=1;i=num;i++)//排序{for(k=i,j=i+1;jnum;j++)if(array[j]array[k])k=j;temp=array[k];array[k]=array[i];array[i]=temp;}for(i=1;i=num;i++){for(k=1,j=2;j=serve;j++)if(timewindow[k]timewindow[j])k=j;timewindow[k]+=array[i];window[k][++window[k][0]]=array[i];}for(min=0.0,i=1;i=serve;i++)for(j=1;j=window[i][0];j++)min+=window[i][j]*(window[i][0]-j+1);min/=num;printf(\n此方案最优服务次序为%f\n,min);getch();}四．运行结果1.2.五．心得体会通过本次实验，我了解了贪心算法的性质与解题思路。会场安排问题和多出最优服务次序问题很好的利用了贪心算法，我进一步理解了贪心算法的性质：考虑问题时从局部出发，虽然贪心算法不是对所有问题都能得到最优解，但对于大多数问题都能得到最优解。这种方法很容易理解又能很好地使用于实际。并且在自身实际编码的过程中也发现自己所存在的问题，比如总会忽略细节，每一次实验都意味着一次进步，我收获到很多包括知识以外的道理。