贪心算法求解最优服务次序问题.docx
- 文档编号:3864852
- 上传时间:2023-05-06
- 格式:DOCX
- 页数:9
- 大小:16.35KB
贪心算法求解最优服务次序问题.docx
《贪心算法求解最优服务次序问题.docx》由会员分享,可在线阅读,更多相关《贪心算法求解最优服务次序问题.docx(9页珍藏版)》请在冰点文库上搜索。
贪心算法求解最优服务次序问题
实验名称:
贪心算法实例编程
求解最优服务次序问题
1、实验目的:
1)理解贪心算法的概念
2)掌握贪心算法的基本要素
3)掌握设计贪心算法的一般步骤
4)针对具体问题,能应用贪心算法设计有效算法
5)用C++实现算法,并且分析算法的效率
2、实验设备及材料:
硬件设备:
PC机
机器配置:
双核cpu频率2.2GHz,内存2G
操作系统:
Windows7
开发工具:
VC++6.0
3、实验内容:
①问题描述
设有n个顾客同时等待一项服务。
顾客i需要的服务时间为t
i,1≤i≤n。
应如何安排n个顾客的服务次序才能使平均等待时间达到最小?
平均等待时间是n恶搞顾客等待服务时间的总和除以n。
②编程任务
对于给定的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)使用贪心算法求解最优服务次序问题的算法,用C++语言描述。
①.最优值:
(贪心算法)
text(intn,intx[],ints[])//s[]为保存每个顾客等待时间的数组
{
inti;
intsum=0;
for(i=0;i {if(i>0){ }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 { while(i j--; e[i]=e[j]; while(i i++; e[j]=e[i]; } e[i]=key; if(first QuickSort(e,first,i-1); if(end>i+1) QuickSort(e,i+1,end);} 实验数据: 3.50 1020303441424344454647 4849202122232098 124689565768131498457 1726483545 4698111212141516 80 1980234567898764321 968 1020303441424344454647 4849202122232098 124689565768131498457 1726483545 4698111212141516121314 15161718192035 2. 序号 15 124689565768131498457输入文件(input.txt)输出文件(output.txt)等待时间从小到大排序: 4456788991213145657 68 最小平均等待时间为: 7720 124689565768131498457 1726483545等待时间从小到大排序: 4456788991213141726 354548565768最小平均等待时间为: 130等待时间从小到大排序: 44456678888999910111212121314141516172020202122232630343541424344454546 47484849565768最小平均等待时间为: 363等待时间从小到大排序: 122334444455666667 778888888999999101112121212131314141415151616171718 191920202020212223263034353541424344454546474848495657 6880 最小平均等待时间为: 432 1. 4. 5.100 13121434353434352221 23242834334455449910 19802345678987643 21968 10203034414243444546 474849202122232098 124689565768131498 4571726483545 469811121214151612 131415161718192035等待时间从小到大排序: 12233444445566666777888888899999910101112121212121313131414141415151616171718191920202020212122222323242628303334343434343535353541424344444445454647484849555657688099最小平均等待时间为: 633 根据对上述贪心算法数据的分析,解决此问题还可以用其他方法。 text2(intn,intx[]) { inti,sum=0;//总等待时间 for(i=0;i sum+=x[i]*(n-i); returnsum/n; }算法思想: 假如顾客的所需要的服务时间分别为: 1,2,3,4,5那么等待时间是 第一位顾客: 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改为cin。 并去掉主函数中cout的注释)#include #include text(intn,intx[],ints[]) { inti; intsum=0; for(i=0;i { if(i>0) { s[i]=x[i]+s[i-1]; sum+=s[i]; } else{ }s[i]=x[i]; sum+=s[i]; } returnsum/n; } text2(intn,intx[]) { }inti,sum=0; for(i=0;i sum+=x[i]*(n-i); returnsum/n; voidQuickSort(inte[],intfirst,intend) { inti=first,j=end,key=e[first]; while(i { while(i j--; e[i]=e[j]; while(i i++; e[j]=e[i]; } e[i]=key; if(first QuickSort(e,first,i-1); if(end>i+1) QuickSort(e,i+1,end); } /*voidsort(intn,intx[])//冒泡排序 { inti,j,c; for(j=0;j { for(i=0;i<(n-1);i++) { }if(x[i]>x[i+1]) { c=x[i]; x[i]=x[i+1]; x[i+1]=c;} } cout<<"等待时间从小到大排序: "; for(i=0;i cout< }*/ voidmain() { }ifstreamfin("D: \\c++\\wait1.in"); intx[1000]; ints[1000]={0}; intn; //cout<<"请输入顾客的个数: "; fin>>n; //cout<<"请输入顾客的等待时间: "; for(inti=0;i fin>>x[i]; QuickSort(x,0,n-1);//快速排序 cout<<"等待时间从小到大排序: "; for(i=0;i cout< //sort(n,x);//冒泡排序 cout<<'\n'<<"最小平均等待时间为: "< //cout<<'\n'<<"最小平均等待时间为: "<
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 贪心 算法 求解 最优 服务 次序 问题