《最优服务次序》由会员分享，可在线阅读，更多相关《最优服务次序（3页珍藏版）》请在金锄头文库上搜索。
1、最优服务次序、实验目的1) 理解贪心算法的概念2) 掌握贪心算法的基本要素3) 掌握设计贪心算法的一般步骤4) 针对具体问题，能应用贪心算法设计有效算法二、实验内容问题描述：设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti, iWi Wn。应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待 时间是n恶搞顾客等待服务时间的总和除以n。编程任务 ：对于给定的 n 个顾客需要的服务时间,计算最优服务次序 三、算法设计算法思想：对服务时间最短的顾客先服务的贪心选择策略。首先对需要服务时 间最短的顾客进行服务，即做完第一次选择后，原问题T变成了需对n-1个顾客 服务的新问题T。新问
2、题和原问题相同，只是问题规模由n减小为n-1。基于 此种选择策略，对新问题T,选择n-1顾客中选择服务时间最短的先进行服务, 如此进行下去，直至所有服务都完成为止 。核心算法的设计描述：cin n;for (int j = 0; j n; j+)cin xj;sor t(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 t endl;算法策略：假设原问题为T,而我们已经知道了某个最优
3、服务系列，即最优解 为A= t(l), t (2),.t(n)(其中t(i)为第i个用户需要的服务时间)，则每 个用户 等待时间为：T(1)= t(l) ； T(2)= t(l)+1(2) ； .T(n):t(1)+1(2)+1(3)+ t(n)； 那么总等待时问，即最优值为：TA=n*t (1) + (n-1) *t(2)+(n+lj) *t(i)+2*t (n-1)+ t(n)；由于平均等待时 间是n个顾客等待时间的总和除以n,故本题实际上就是求使顾客等待时间的总 和最小的服务次序。四、程序调试及运行结果分析C:WINDOWSsystem3Z1056 12 1 99 1QQ0 23M 33
4、 55 99 B12532五、实验总结 通过这次实验，使我对贪心算法有了更深的理解与认识。但是，通过这次试验， 我深刻认识到自己编码能力的缺失，以后一 定多加锻炼。在看懂代码的基础上 自己多加动手，不能仅仅满足 于看懂听懂的基础上，只有这样自己才能得到真 正的提高。六、程序清单#includestdafx.h#includeiostream#includeusingnamespace std;int x10000;int main()int n;cin n;for (int j = 0; j n; j+)cin xj;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 t endl;sys tem (pause);return 0;
