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

《贪心算法求解最优服务次序问题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、实验名称：贪心算法实例编程求解最优服务次序问题1、实验目的：1)理解贪心算法的概念2)掌握贪心算法的基本要素3)掌握设计贪心算法的一般步骤4)针对具体问题，能应用贪心算法设计有效算法5)用C++实现算法，并且分析算法的效率2、实验设备及材料：硬件设备：PC机机器配置：双核cpu频率2.2GHz,内存2G操作系统：Windows7开发工具：VC++6.03、实验内容：①问题描述设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti，1≤i≤n。应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n恶搞顾客等待服务时间的总和除以n。②编

2、程任务对于给定的n个顾客需要的服务时间，计算最优服务次序。③样例例如，现在有5个顾客，他们需要的服务时间分别为：56，12，5，99，33。那么，按照所需服务时间从小到大排序为：5,12,33,56,99。排序后的顾客等待服务完成的时间为：5，17，50，106，205；和为：383；平均等待时间为：76.6。4、实验方法步骤及注意事项：①实验步骤a、分析问题，确定最优的贪心选择；b、针对贪心选择过程进行算法设计；c、举例验证算法的正确性；d、上机调试算法。②解题思路1)求解最优服务次序问题的贪心策略为：先为所需服务时间最短的顾客服务。2)使用贪心算法

3、求解最优服务次序问题的算法，用C++语言描述。①.最优值：(贪心算法)text(intn,intx[],ints[])//s[]为保存每个顾客等待时间的数组{inti;intsum=0;for(i=0;i0){s[i]=x[i]+s[i-1];sum+=s[i];}else{s[i]=x[i];sum+=s[i];}}returnsum/n;}②.最优解：（快速排序）voidQuickSort(inte[],intfirst,intend){inti=first,j=end,key=e[first];while(i

4、ile(i=key)j--;e[i]=e[j];while(ii+1)QuickSort(e,i+1,end);}实验数据:序号输入文件(input.txt)输出文件(output.txt)1.15124689565768131498457等待时间从小到大排序：445678899121314565768最小平均等待时间为：772.20124689565768131498457

5、1726483545等待时间从小到大排序：4456788991213141726354548565768最小平均等待时间为：1303.501020303441424344454647484920212223209812468956576813149845717264835454698111212141516等待时间从小到大排序：4445667888899991011121212131414151617202020212223263034354142434445454647484849565768最小平均等待时间为：3634.80198023456789

6、8764321968102030344142434445464748492021222320981246895657681314984571726483545469811121214151612131415161718192035等待时间从小到大排序：1223344444556666677788888889999991011121212121313141414151516161717181919202020202122232630343535414243444545464748484956576880最小平均等待时间为：4325.10013121434

7、353434352221232428343344554499101980234567898764321968102030344142434445464748492021222320981246895657681314984571726483545469811121214151612131415161718192035等待时间从小到大排序：1223344444556666677788888889999991010111212121212131313141414141515161617171819192020202021212222232324262830

8、33343434343435353535414243444444454546474848495