欢迎来到天天文库
浏览记录
ID:6445069
大小:51.61 KB
页数:5页
时间:2018-01-14
《贪心算法解决会场安排问题、多处最优服务次序问题(含源代码)》由会员上传分享,免费在线阅读,更多相关内容在学术论文-天天文库。
1、西安邮电大学(计算机学院)课内实验报告实验名称:贪心算法专业名称:计算机科学与技术班级:学生姓名:学号(8位):指导教师:实验日期:2014年5月22日一.实验目的及实验环境实验目的:通过实际应用熟悉贪心算法,并解决会场安排问题、多出最优服务次序问题实验环境:VisualC++6.0二.实验内容1.会场安排问题.假设要在足够多的回厂里安排一批活动,并希望使用尽可能少的会场,设计一个有效的贪心算大进行安排(这个问题实际上是注明的图着色问题。若将每一个活动作为图的一个顶点,不相容活动间用边相连。使相邻
2、顶点着有不同颜色的最小着色数,相应于要找的最小会场数)2.多处最优服务次序问题设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti,1<=i<=n。共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小?平均等待时间是n个顾客等待服务时间的总和除以n。三.方案设计1、设有n个活动的集合E={1,2,…,n},其中每个活动都要求使用同一资源,如演讲会场等,而在同一时间内只有一个活动能使用这一资源。每个活动i都有一个要求使用该资源的起始时间si和一个结束时间fi,且si<
3、fi。如果选择了活动i,则它在半开时间区间[si,fi)内占用资源。若区间[si,fi)与区间[sj,fj)不相交,则称活动i与活动j是相容的。也就是说,当si≥fj或sj≥fi时,活动i与活动j相容。由于输入的活动以其完成时间的非减序排列,所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上,按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说,该算法的贪心选择的意义是使剩余的可安排时间段极大化,以便安排尽可能多的相容活动。算法greedySe
4、lector的效率极高。当输入的活动已按结束时间的非减序排列,算法只需O(n)的时间安排n个活动,使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列,可以用O(nlogn)的时间重排。1.会场安排问题源代码#include#include#includeusingnamespacestd;structpoint{intt;boolf;};boolcmp(pointx,pointy){returnx.t5、dy(vectorx){intmax=0,cur=0,n=x.size();sort(x.begin(),x.end(),cmp);for(inti=0;imax)max=cur;}returnmax;}intmain(){vectorx;intn,i;pointtemp;while(cin>>n,n){for(i=0;i>temp.t;x.6、push_back(temp);temp.f=false;cin>>temp.t;x.push_back(temp);}cout<#includemain(){int**window,*timewindow,*array,num,serve,i,j,k,temp;doublemin;printf("请输入等待服务人数");scanf("7、%d",&num);printf("请输入服务窗口数");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*));pri8、ntf("请依次输入服务等待时间");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;j
5、dy(vectorx){intmax=0,cur=0,n=x.size();sort(x.begin(),x.end(),cmp);for(inti=0;imax)max=cur;}returnmax;}intmain(){vectorx;intn,i;pointtemp;while(cin>>n,n){for(i=0;i>temp.t;x.
6、push_back(temp);temp.f=false;cin>>temp.t;x.push_back(temp);}cout<#includemain(){int**window,*timewindow,*array,num,serve,i,j,k,temp;doublemin;printf("请输入等待服务人数");scanf("
7、%d",&num);printf("请输入服务窗口数");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*));pri
8、ntf("请依次输入服务等待时间");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;j
此文档下载收益归作者所有