贪心算法解决会场安排问题、多处最优服务次序问题

1、精选优质文档-倾情为你奉上 西 安 邮 电 大 学 （计算机学院）课内实验报告实验名称： 贪心算法 专业名称： 计算机科学与技术班 级： 学生姓名： 学号（8位）： 指导教师： 实验日期： 2014年5月22日1 实验目的及实验环境 实验目的：通过实际应用熟悉贪心算法，并解决会场安排问题、多出最优服务次序问题 实验环境：Visual C+ 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 <fi 。如果选择了活动i，则它在半开时间区间si, fi)内占用资源。若区间si, fi)与区间sj, fj)不相交

3、，则称活动i与活动j是相容的。也就是说，当sifj或sjfi时，活动i与活动j相容。由于输入的活动以其完成时间的非减序排列，所以算法greedySelector每次总是选择具有最早完成时间的相容活动加入集合A中。直观上，按这种方法选择相容活动为未安排活动留下尽可能多的时间。也就是说，该算法的贪心选择的意义是使剩余的可安排时间段极大化，以便安排尽可能多的相容活动。算法greedySelector的效率极高。当输入的活动已按结束时间的非减序排列，算法只需O(n)的时间安排n个活动，使最多的活动能相容地使用公共资源。如果所给出的活动未按非减序排列，可以用O(nlogn)的时间重排。 1.会场安排问题

4、源代码#include <iostream>#include <vector>#include <algorithm>using namespace std;struct point int t; bool f;bool cmp(point x,point y) return x.t<y.t;int greedy(vector<point> x) int max=0,cur=0,n=x.size(); sort(x.begin(),x.end(),cmp); for(int i=0;i<n;i+) if(xi.f) cur+; els

5、e cur-; if(cur>max) max=cur; return max; int main() vector<point> x; int n,i; point temp; while(cin>>n,n) for(i=0;i<n;i+) temp.f=true; cin>>temp.t; x.push_back(temp); temp.f=false; cin>>temp.t; x.push_back(temp); cout<<greedy(x)<<endl; x.clear(); return 0;2.

6、 多处最优服务次序问题源代码：#include<stdio.h>#include<stdlib.h>main()int *window,*timewindow,*array,num,serve,i,j,k,temp;double min;printf("请输入等待服务人数n");scanf("%d",&num);printf("请输入服务窗口数n");scanf("%d",&serve);array = (int *)malloc(num + 1) * sizeof(int)

7、;timewindow = (int *)malloc(serve + 1) * sizeof(int);window = (int *)malloc(serve + 1) * sizeof(int *);for(i = 0; i <= serve;i+) windowi = (int *)malloc(num + 1) * sizeof(int *);printf("请依次输入服务等待时间n");for(i = 1; i <= num;i+) scanf("%d",&arrayi);for(i = 0; i <= serve;

8、i+) timewindowi = 0; for(j = 0; j <= num; j+) windowij = 0;for(i = 1; i <= num; i+)/排序 for(k = i,j = i + 1; j < num; j+) if(arrayj < arrayk) k = j; temp = arrayk; arrayk = arrayi; arrayi = temp;for(i = 1; i <= num; i+) for(k = 1,j = 2; j <= serve;j+) if(timewindowk > timewindowj

9、) k = j; timewindowk +=arrayi; windowk+windowk0 = arrayi; for(min = 0.0,i = 1; i <= serve;i+) for(j = 1; j <= windowi0;j+) min += windowij * (windowi0 - j + 1); min /= num; printf("n此方案最优服务次序为%fn",min); getch();4 运行结果 1.2.五心得体会 通过本次实验，我了解了贪心算法的性质与解题思路。会场安排问题和多出最优服务次序问题很好的利用了贪心算法，我进一步理解了贪心算法的性