貪心算法求解最優(yōu)服務(wù)次序問題

實(shí)驗(yàn)名稱：貪心算法實(shí)例編程求解最優(yōu)服務(wù)次序問題1、實(shí)驗(yàn)?zāi)康模?）理解貪心算法的概念2）掌握貪心算法的基本要素3）掌握設(shè)計(jì)貪心算法的一般步驟4）針對具體問題，能應(yīng)用貪心算法設(shè)計(jì)有效算法5）用C++實(shí)現(xiàn)算法，并且分析算法的效率2、實(shí)驗(yàn)設(shè)備及材料：硬件設(shè)備：PC機(jī)機(jī)器配置:雙核cpu頻率2.2GHz,內(nèi)存2G操作系統(tǒng)：Windows7開發(fā)工具：VC++6.03、實(shí)驗(yàn)內(nèi)容：①問題描述設(shè)有n個(gè)顧客同時(shí)等待一項(xiàng)服務(wù)。顧客i需要的服務(wù)時(shí)間為ti,l<i<no應(yīng)如何安排n個(gè)顧客的服務(wù)次序才能使平均等待時(shí)間達(dá)到最?。科骄却龝r(shí)間是n惡搞顧客等待服務(wù)時(shí)間的總和除以no②編程任務(wù)對于給定的n個(gè)顧客需要的服務(wù)時(shí)間，計(jì)算最優(yōu)服務(wù)次序。③樣例例如，現(xiàn)在有5個(gè)顧客，他們需要的服務(wù)時(shí)間分別為：56,12,5,99,33o那么，按照所需服務(wù)時(shí)間從小到大排序?yàn)椋?,12,33,56,99。排序后的顧客等待服務(wù)完成的時(shí)間為:5,17,50,106,205；和為：383；平均等待時(shí)間為:76.6。4、實(shí)驗(yàn)方法步驟及注意事項(xiàng)：①實(shí)驗(yàn)步驟c>d、分析問題，確定最優(yōu)的貪心選擇；針對貪心選擇過程進(jìn)行算法設(shè)計(jì)；舉例驗(yàn)證算法的正確性；上機(jī)調(diào)試算法。②解題思路1）求解最優(yōu)服務(wù)次序問題的貪心策略為：先為所需服務(wù)時(shí)間最短的顧客服務(wù)。2）使用貪心算法求解最優(yōu)服務(wù)次序問題的算法，用C++語言描述。①,最優(yōu)值：（貪心算法）text（intn,intx[],ints口）〃s[]為保存每個(gè)顧客等待時(shí)間的數(shù)組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;}②,最優(yōu)解：(快速排序)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);}實(shí)驗(yàn)數(shù)據(jù)：3.5010203034414243444546474849202122232098124689565768131498457172648354546981112121415168019802345678987643219681020303441424344454647484920212223209812468956576813149845717264835454/114698111212141516121314151617181920352.序號15124689565768131498457輸入文件(input.txt)輸出文件(output.txt)等待時(shí)間從小到大排序:445678899121314565768最小平均等待時(shí)間為：77201246895657681314984571726483545等待時(shí)間從小到大排序:4456788991213141726354548565768最小平均等待時(shí)間為:130等待時(shí)間從小到大排序:4445667888899991011121212131414151617202020212223263034354142434445454647484849565768最小平均等待時(shí)間為：363等待時(shí)間從小到大排序：1223344444556666677788888889999991011121212121313141414151516161717181919202020202122232630343535414243444545464748484956576880最小平均等待時(shí)間為：4321.4.5.1005/1113121434353434352221232428343344554499101980234567898764321968102030344142434445464748492021222320981246895657681314984571726483545469811121214151612131415161718192035等待時(shí)間從小到大排序：12233444445566666777888888899999910101112121212121313131414141415151616171718191920202020212122222323242628303334343434343535353541424344444445454647484849555657688099最小平均等待時(shí)間為:633根據(jù)對上述貪心算法數(shù)據(jù)的分析，解決此問題還可以用其他方法。text2(intn,intx[]){inti/sum=0;〃總等待時(shí)間for(i=0;i<n;i++)sum+=x[i]*(n-i);returnsum/n;}算法思想：假如顧客的所需要的服務(wù)時(shí)間分別為：1,2,3,4,5那么等待時(shí)間是6/11第一位顧客：1第二位顧客：1,2第三位顧客：1,2,3第四位顧客：1,2,3,4第五位顧客：1,2,3,4,5則總等待時(shí)間可寫成：1*5+2*4+3*3+4*2+5*1源程序:(以下采用文件輸入，如需手動輸入請將fin改為cino并去掉主函數(shù)中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<<”等待時(shí)間從小到大排序：“；for(i=0;i<n;i++)cout?x[i]?'}*/voidmain(){}ifstreamfin("D:\\c++\\waitl.in");intx[1000];ints[1000]={0};intn;〃cout<<”請輸入顧客的個(gè)數(shù)十;fin?n;〃cout<<”請輸入顧客的等待時(shí)間：”；for(inti=0;i<n;i++)fin