用贪心算法求解最优服务次序问题(共7页).doc

《用贪心算法求解最优服务次序问题(共7页).doc》由会员分享，可在线阅读，更多相关《用贪心算法求解最优服务次序问题(共7页).doc（7页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上最优服务次序问题：设有n个顾客同时等待同一项服务，顾客i需要的服务时间为ti，n=i=1，应如何安排这n个顾客的服务次序才能使平均等待时间达到最小。平均等待时间是n个顾客等待服务时间的总和除以n。贪心选择策略假设原问题为T，而我们已经知道了某个最优服务系列，即最优解为A=t(1)，t(2)，t(n)(其中t(i)为第i个用户需要的服务时间)，则每个用户等待时间为：T(1)=t(1)；T(2)=t(1)十t(2)：T(n)-t(1)+t(2)十t(3)+t(n)；那么总等待时间，即最优值为：TA=n。t(1)+(rrl)t(2)十+(n+li)t(i)+2t(n-1)+

2、t(n)由于平均等待时问是n个顾客等待时间的总和除以n，故本题实际上就是求使顾客等待时间的总和最小的服务次序。本问题采用贪心算法求解，贪心策略如下：对服务时间最的顾客先服务的贪心选择策略。首先对需要服务时问最短的顾客进行服务，即做完第一次选择后，原问题T变成了需对n-1个顾客服务的新问题T。新问题和原问题相同，只是问题规模由n减小为n一1。基于此种选择策略，对新问题T，选择n-l顾客中选择服务时间最短的先进行服务如此进行下去，直至所有服务都完成为止。#include#nclude#include#includelong n：_1： 顾客数nLong *wait； N各自等待时间void inp

3、utData O输入数据n、waitifstream fin；finopen(*inputtxt，los:nocreate)；if(!fin)cout“File Open Error!n；Wait=new longn；for(1ong i=0；iwaiti；)finclose0；void ShellSort(10ng *a)(/Shell排序，实现数据从小到大排序long i，j，xgap=n2；while(gap0)for(i=gap；i=0)if(aJaj+gap)x=aj；aj=aj+gap；aj+gap=x；j=j-gap； elsej一1；gap=gap2；函数名：AveWait0描

4、述：计算平均等待时问参数：各顾客等待时间double AveWait(10ng *a)double ave=0.0； ShellSort(a)； for(10ng i=0；in；i+)ave+=10*(n-i)*ai；ave=n；return ave；)void outputData(double out)(输出结果ofstream fout；foutopen(outputTxt)；foutsetiosflags(ios：fixed)setprecision(2)outendl；foutclose0；)void main0/主调函数inputData()；if(n!=-1)(double av

5、ewait=AveWait(wait)；outputData(avewait)：试验结果：inputtxt：10 56 12 l 99 1000 234 33 55 99 812outputtxt：53200多处最优服务次序问题：设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti，1=i=n。共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以n。(输入的数据要求从文件input.txt中读到程序中，输出结果要求写入文件output.txt中。)法一：#include#includeusing namespace

6、std;void CountingSort(int t,int n,int r,int e,int q) int i; /计数排序 for( i=0;ie;i+) qi=0;/把数组元素全部赋初值为0for( i=0;in;i+) qti+=1;/判断累计相同等待时间的个数 qti=qti+1; for( i=1;i0;i-)/将顾客等待时间从小到大排列 rqti-1-1=ti-1; qti-1-=1; void main()int i=0,sum=0,n,max=0,u;/n为顾客个数float vt,p;ifstream in(input.txt);if(in.fail() coutinp

7、ut error!n; /new是给指针r分配n长度的空间，设置动态数组r,m，两个数组大小相同int *r=new intn; int *t=new intn;for(i=0;iti;/从文本给等待时间ti数组赋值for(i=0;in;i+) if(maxti) max=ti;/找出最大的等待时间u=max; /u为所有顾客中最长的等待时间int *q=new intu+1; /动态数组用于计数排序,减少排序时间CountingSort(t,n,r,u+1,q);/调用CountingSort（）函数for(i=0;in;i+) sum+=ri*(n-i);/文件尾:p=(float)sum

8、;/顾客等待服务时间的总和sum转换成浮点数赋给pvt=p/n;/ 计算平均等待时间outvtendl; 法二：#include#include#includeusing namespace std;ifstream in(input.txt);ofstream out(output.txt);int Max(int a,int n)int pos=0;for(int i=0;in;i+) if(apos1;size-) int j=Max(a,size); Swap(aj,asize-1);int Partition(int a,int p,int r)int i=p,j=r+1,x=ap;

9、while(true) while(a+ix&ix); if(i=j)break; Swap(ai,aj);ap=aj;aj=x;return j;void Quicksort(int a,int p,int r)if(r-p=9) Selectsort(&ap,r-p+1);else if(pr) int q=Partition(a,p,r); Quicksort(a,p,q-1); Quicksort(a,q+1,r);void main()if(in.fail() coutn;int *a=new int n;for(int i=0;iai;/文件尾:Quicksort(a,0,n-1)

10、;double num=0;for(i=0;in;i+) num+=ai*(n-i);num=num/n;outsetiosflags(ios:fixed);outsetprecision(2)numendl;/*input.txt*102433975531*output.txt*16.90*/最优服务次序#include #include #include #include #include using namespace std; int x10000; int main() int n; cin n; int temp; /vector x; for(int j = 0; j n; j+) / scanf(%d,&temp); / x.push_back(temp); scanf(%d,&xj); / sort(x.begin(),x.end(); sort(x,x+n); for(int i = 1; i n; i+) xi+=xi-1; double t = 0; for(int i = 0; i n; i+) t+=xi; t/=n; cout.setf(ios:fixed); cout setprecision(2) t endl; system(pause); return 0; 专心-专注-专业