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

实验名称：贪心算法实例编程求解最优服务次序问题1、实验目的：1）理解贪心算法的概念2）掌握贪心算法的基本要素3）掌握设计贪心算法的一般步骤4）针对具体问题，能应用贪心算法设计有效算法5）用C++实现算法，并且分析算法的效率2、实验设备及材料：硬件设备：PC机机器配置:双核cpu频率2.2GHz,内存2G操作系统：Windows7开发工具：VC++6.03、实验内容：①问题描述设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti,l<i<no应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n恶搞顾客等待服务时间的总和除以no②编程任务对于给定的n个顾客需要的服务时间，计算最优服务次序。③样例例如，现在有5个顾客，他们需要的服务时间分别为：56,12,5,99,33o那么，按照所需服务时间从小到大排序为：5,12,33,56,99。排序后的顾客等待服务完成的时间为:5,17,50,106,205；和为：383；平均等待时间为:76.6。4、实验方法步骤及注意事项：①实验步骤c>d、分析问题，确定最优的贪心选择；针对贪心选择过程进行算法设计；举例验证算法的正确性；上机调试算法。②解题思路1）求解最优服务次序问题的贪心策略为：先为所需服务时间最短的顾客服务。2）使用贪心算法求解最优服务次序问题的算法，用C++语言描述。①,最优值：（贪心算法）text（intn,intx[],ints口）〃s[]为保存每个顾客等待时间的数组inti;11intsum=O;for(i=0;i<n;i++){if(i>0){}s[i]=x[i]+s[i-l];sum+=s[i];}else{}s[i]=x[i];sum+=s[i];returnsum/n;}②,最优解：(快速排序)voidQuickSort(inte[],intfirst,intend)(inti=firstJ=end,key=e[first];while(i<j)(while(i<j&&e[j]>=key)j-；e[i]=eD]；while(i<j&&e[i]<=key)i++；3/11e[i]=key;if(first<i-l)QuickSort(e,first,i-1);if(end>i+l)QuickSort(e,i+l,end);}实验数据：3.5010203034414243444546474849202122232098124689565768131498457172648354546981112121415168019802345678987643219681020303441424344454647484920212223209812468956576813149845717264835454/114698111212141516121314151617181920352.序号15124689565768131498457输入文件(input.txt)输出文件(output.txt)等待时间从小到大排序:445678899121314565768最小平均等待时间为：77201246895657681314984571726483545等待时间从小到大排序:4456788991213141726354548565768最小平均等待时间为:130等待时间从小到大排序:4445667888899991011121212131414151617202020212223263034354142434445454647484849565768最小平均等待时间为：363等待时间从小到大排序：1223344444556666677788888889999991011121212121313141414151516161717181919202020202122232630343535414243444545464748484956576880最小平均等待时间为：4321.4.5.1005/1113121434353434352221232428343344554499101980234567898764321968102030344142434445464748492021222320981246895657681314984571726483545469811121214151612131415161718192035等待时间从小到大排序：12233444445566666777888888899999910101112121212121313131414141415151616171718191920202020212122222323242628303334343434343535353541424344444445454647484849555657688099最小平均等待时间为:633根据对上述贪心算法数据的分析，解决此问题还可以用其他方法。text2(intn,intx[]){inti/sum=0;〃总等待时间for(i=0;i<n;i++)sum+=x[i]*(n-i);returnsum/n;}算法思想：假如顾客的所需要的服务时间分别为：1,2,3,4,5那么等待时间是6/11第一位顾客：1第二位顾客：1,2第三位顾客：1,2,3第四位顾客：1,2,3,4第五位顾客：1,2,3,4,5则总等待时间可写成：1*5+2*4+3*3+4*2+5*1源程序:(以下采用文件输入，如需手动输入请将fin改为cino并去掉主函数中cout的注释)#include<iostream.h>#include<fstream.h>text(intn,intx[],ints[]){inti;intsum=0;for(i=0;i<n;i++){if(i>0){s[i]=x[i]+s[i-l];sum+=s[i];}else{7/11sum+=s[i];}returnsum/n;}text2(intnjntx[]){}inti,sum=O;for(i=0;i<n;i++)sum+=x[i]*(n-i);returnsum/n;voidQuickSort(inte[],intfirst,intend){inti=firstJ=end,key=e[first];while(i<j){while(i<j&&e[j]>=key)j-；e[i]=eD]；while(i<j&&e[i]<=key)i++；8/11e[j]=e[i];)e[i]=key;if(first<i-l)QuickSort(e,first,i-1);if(end>i+l)QuickSort(e,i+l,end);)/*voidsort(intnjntx口)〃冒泡排序{intij,c;for(j=0;j<n;j++){for(i=0;i<(n-l);i++)(}if(x[i]>x[i+l]){c=x[i];x[i]=x[i+l];x[i+l]=c;})9/11cout<<”等待时间从小到大排序：“；for(i=0;i<n;i++)cout«x[i]«'}*/voidmain(){}ifstreamfin("D:\\c++\\waitl.in");intx[1000];ints[1000]={0};intn;〃cout<<”请输入顾客的个数十;fin»n;〃cout<<”请输入顾客的等待时间：”；for(inti=0;i<n;i++)fin