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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上最優(yōu)服務(wù)次序問題：設(shè)有n個(gè)顧客同時(shí)等待同一項(xiàng)服務(wù)，顧客i需要的服務(wù)時(shí)間為ti，n>=i>=1，應(yīng)如何安排這n個(gè)顧客的服務(wù)次序才能使平均等待時(shí)間達(dá)到最小。平均等待時(shí)間是n個(gè)顧客等待服務(wù)時(shí)間的總和除以n。貪心選擇策略假設(shè)原問題為T，而我們已經(jīng)知道了某個(gè)最優(yōu)服務(wù)系列，即最優(yōu)解為A=t(1)，t(2)，t(n)(其中t(i)為第i個(gè)用戶需要的服務(wù)時(shí)間)，則每個(gè)用戶等待時(shí)間為：T(1)=t(1)；T(2)=t(1)十t(2)：T(n)-t(1)+t(2)十t(3)+t(n)；那么總等待時(shí)間，即最優(yōu)值為：TA=n。t(1)+(rrl)t(2)十+(n+li)t(i)+

2、2t(n-1)+t(n)由于平均等待時(shí)問是n個(gè)顧客等待時(shí)間的總和除以n，故本題實(shí)際上就是求使顧客等待時(shí)間的總和最小的服務(wù)次序。本問題采用貪心算法求解，貪心策略如下：對(duì)服務(wù)時(shí)間最的顧客先服務(wù)的貪心選擇策略。首先對(duì)需要服務(wù)時(shí)問最短的顧客進(jìn)行服務(wù)，即做完第一次選擇后，原問題T變成了需對(duì)n-1個(gè)顧客服務(wù)的新問題T。新問題和原問題相同，只是問題規(guī)模由n減小為n一1。基于此種選擇策略，對(duì)新問題T，選擇n-l顧客中選擇服務(wù)時(shí)間最短的先進(jìn)行服務(wù)如此進(jìn)行下去，直至所有服務(wù)都完成為止。#include<fstreamh>#nclude<iostreamh>#include<stdli

3、bh>#include<iomaniph>long n：_1： 顧客數(shù)nLong *wait； N各自等待時(shí)間void inputData O輸入數(shù)據(jù)n、waitifstream fin；finopen(*inputtxt，los:nocreate)；if(!fin)cout<<“File Open Error!"<<endl；return；fin>>n；Wait=new longn；for(1ong i=0；i<n；i十十)fin>>waiti；)finclose0；void ShellSort(10ng *a

4、)(/Shell排序，實(shí)現(xiàn)數(shù)據(jù)從小到大排序long i，j，xgap=n2；while(gap>0)for(i=gap；i<n；i+) j=i-gap；while(J>=0)if(aJ>aj+gap)x=aj；aj=aj+gap；aj+gap=x；j=j-gap； elsej一1；gap=gap2；函數(shù)名：AveWait0描述：計(jì)算平均等待時(shí)問參數(shù)：各顧客等待時(shí)間double AveWait(10ng *a)double ave=0.0； ShellSort(a)； for(10ng i=0；i<n；i+)ave+=10*(n-i)*ai；ave=n；return

5、 ave；)void outputData(double out)(輸出結(jié)果ofstream fout；foutopen("outputTxt")；fout<<setiosflags(ios：fixed)<<setprecision(2)<<out<<endl；foutclose0；)void main0/主調(diào)函數(shù)inputData()；if(n!=-1)(double avewait=AveWait(wait)；outputData(avewait)：試驗(yàn)結(jié)果：inputtxt：10 56 12 l 99 1000 234

6、33 55 99 812outputtxt：53200多處最優(yōu)服務(wù)次序問題：設(shè)有n個(gè)顧客同時(shí)等待一項(xiàng)服務(wù)。顧客i需要的服務(wù)時(shí)間為ti，1<=i<=n。共有s處可以提供此項(xiàng)服務(wù)。應(yīng)如何安排n個(gè)顧客的服務(wù)次序才能使平均等待時(shí)間達(dá)到最?。科骄却龝r(shí)間是n個(gè)顧客等待服務(wù)時(shí)間的總和除以n。(輸入的數(shù)據(jù)要求從文件input.txt中讀到程序中，輸出結(jié)果要求寫入文件output.txt中。)法一：#include<iostream>#include<fstream>using namespace std;void CountingSort(int t,int n,int

7、r,int e,int q) int i; /計(jì)數(shù)排序 for( i=0;i<e;i+) qi=0;/把數(shù)組元素全部賦初值為0for( i=0;i<n;i+) qti+=1;/判斷累計(jì)相同等待時(shí)間的個(gè)數(shù) qti=qti+1; for( i=1;i<e;i+) qi+=qi-1;/qi=qi+qi-1 for( i=n;i>0;i-)/將顧客等待時(shí)間從小到大排列 rqti-1-1=ti-1; qti-1-=1; void main()int i=0,sum=0,n,max=0,u;/n為顧客個(gè)數(shù)float vt,p;ifstream in("input.txt&

8、quot;);if(in.fail() cout<<"input error!"<<endl; exit(1);/拋出一個(gè)異常窗口ofstream out("output.txt");out.setf(ios:fixed); /對(duì)輸出設(shè)置精度out.precision(2);in>>n; /new是給指針r分配n長度的空間，設(shè)置動(dòng)態(tài)數(shù)組r,m，兩個(gè)數(shù)組大小相同int *r=new intn; int *t=new intn;for(i=0;i<n;i+) in>>ti;/從文本給等待時(shí)間ti數(shù)組賦值f

9、or(i=0;i<n;i+) if(max<ti) max=ti;/找出最大的等待時(shí)間u=max; /u為所有顧客中最長的等待時(shí)間int *q=new intu+1; /動(dòng)態(tài)數(shù)組用于計(jì)數(shù)排序,減少排序時(shí)間CountingSort(t,n,r,u+1,q);/調(diào)用CountingSort（）函數(shù)for(i=0;i<n;i+) sum+=ri*(n-i);/文件尾:p=(float)sum;/顧客等待服務(wù)時(shí)間的總和sum轉(zhuǎn)換成浮點(diǎn)數(shù)賦給pvt=p/n;/ 計(jì)算平均等待時(shí)間out<<vt<<endl; 法二：#include<iostream>#

10、include<fstream>#include<iomanip>using namespace std;ifstream in("input.txt");ofstream out("output.txt");int Max(int a,int n)int pos=0;for(int i=0;i<n;i+) if(apos<ai) pos=i; return pos;void Swap(int x,int y)int temp;temp=x;x=y;y=temp;void Selectsort(int a,int n)

11、for(int size=n;size>1;size-) int j=Max(a,size); Swap(aj,asize-1);int Partition(int a,int p,int r)int i=p,j=r+1,x=ap;while(true) while(a+i<x&&i<=r); while(a-j>x); if(i>=j)break; Swap(ai,aj);ap=aj;aj=x;return j;void Quicksort(int a,int p,int r)if(r-p<=9) Selectsort(&ap,r-

12、p+1);else if(p<r) int q=Partition(a,p,r); Quicksort(a,p,q-1); Quicksort(a,q+1,r);void main()if(in.fail() cout<<"the input.txt is not exist!" exit(1);int n;in>>n;int *a=new int n;for(int i=0;i<n;i+) in>>ai;/文件尾:Quicksort(a,0,n-1);double num=0;for(i=0;i<n;i+) num+=

13、ai*(n-i);num=num/n;out<<setiosflags(ios:fixed);out<<setprecision(2)<<num<<endl;/*input.txt*102433975531*output.txt*16.90*/最優(yōu)服務(wù)次序#include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<iomanip> using namespace std; int x10000; int main() int n; cin >> n; int temp; /vector<int> x; for(int j = 0; j< n; j+) / scanf("%d",&temp); / x.push_back(temp); scanf("%d",&xj); / sort(x.begin(),x.end(); sort(x,x+n); f