用贪心算法求解最优服务次序问题

1、最优服务次序问题：设有n个顾客同时等待同一项服务，顾客i需要的服务时间为ti， n=i=1，应如何安排这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+l i) t(i)+12

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

3、各自等待时间 void inputData O /输入数据 n、wait ifstream fin ； fin ope n(*input txt 、los: no create) ； if(!fi n) cout “ File pOen Error!uendl ； return ； ) finn ； Wait=new longn ； for(1ong i=0 ； ivn ； i -|H )( finwaiti: ) fin closeO ； ) void ShellSort(10ng *a) (/Shell 排序，实现数据从小到大排序 long i，j，x gap=n/2 ； while(ga

4、p0) for(i=gap ； ivn ； i+) j=i-gap ； while(J=0) if(aJaj+gap)(x=aj ； aj=aj+gap ； aj+gap=x ； j=j-gap ； ielsej 一 1 ； lgap=gap/ 2 ； “/函数名：AveWaitO描述：计算平均等待时问参数：各顾客等待时间/ double AveWait(10ng *a) idouble ave=0.0 ； ShellSort(a) ； for(10ng i=0 ； ivn ； i+) ave+=1 O*(n-i)*ai； lave/ =n ； return ave ； void output

5、Data(double out) ( | 输出结果 ofstream tout ； tout open(output Txt) foutsetiosflags(ios : : fixed)setprecision(2) outendl ； fout closeO ； void mainO 主调函数 inputData(): if(n!=-1)( double avewait=AveWait(wait) ； outputData(avewait): 试验结果：input txt : 10 56 12 I 99 1000 234 33 55 99 812 output txt : * 532 00

6、 多处最优服务次序问题：设有n个顾客同时等待一项服务。顾客i需要的服务 时间为ti，1=i=n。共有s处可以提供此项服务。应如何安排n个顾客的服务 次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总 和除以n。（输入的数据要求从文件input.txt中读到程序中，输出结果要求写入 文件 output.txt 中。） #include #include using namespace std; void CountingSort(int t,int nJnt r,int e,int q) inti;计数排序 for( i=0;ive;i+) qi=0; 把数组元素全部赋初值为

7、0 for( i=0;ivn;i+) qti+=1 ； 判断累计相同等待时间的个数qti=qti+1 ； for( i=1 ;ive;i+) qi+=qi-1;/qi=qi+qi-1 for( i=n;i0;i-) /将顾客等待时间从小到大排列 void main() int i=0,sum=0,n,max=0,u;/n 为顾客个数 float vt,p; ifstream in(ninput.txtM)； if(in.fail()( coutinput error!nendl; exit(1);/抛出一个异常窗口 ofstream out(output.txtn); out.setf(ios

8、:fixed);/对输出设置精度 out.precision(2); inn; /new是给指针r分配n长度的空间，设置动态数组r,m，两个数组大小相同int *r=new intn; int *t=new intn; for(i=0;in;i+) inti; 从文本给等待时间 ti数组赋值 for(i=0;ivn;i+) df(maxti) max=ti; /找出最大的等待时间 u=max; /u为所有顾客中最长的等待时间int *q=new intu+1; 动态数组用于计数 排序，减少排序时间 CountingSort(t,n,r,u+1 ,q);/ 调用 CountingSort()函数

9、 for(i=0;ivn;i+) sum+=ri*(n-i); ) 文件尾:p=(float)sum;/顾客等待服务时间的总和sum转换成浮点数赋给p vt=p/n;/计算平均等待时间outvtendl; )法二： #include #include #include using namespace std; ifstream in(”input.txt”)； ofstream out(output.txtn); int Max(int a,int n) dnt pos=0; for(int i=0;in;i+) if(apos1 ;size-) int j=Max(a,size); Swap

10、(aj,asize-1); ) int Partition(int a,int p,int r) int i=p,j=r+1 ,x=ap; while(true) iwhile(a+ix if(i=j)break; Swap(ai,aj); jap=aj; aj=x; return j; ) void Quicksort(int a,int p,int r) df(r-p=9) Selectsort( else if(pai; 文件尾： Quicksort(a,0,n-1); double num=0; for(i=0;ivn;i+) nu m+=ai*(n-i); num=num/n; ou

11、tvvsetiosflags(ios:fixed); outsetprecision(2) vnu mendl; ) /* in put.txt 10 2 5 5 3 1 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”, / x.push_back(temp); scanf(,%d, ) / sort(x.begin(),x.end(); s