最優服務次序問題

問題描述： 設有n個顧客同時等待一項服務。顧客i需要的服務時間為ti, 1≦i ≦n 。共有s處可以提供此服務。應如何安排n個顧客的服務次序才能使平均等待時間達到最小平均等待時間是n個顧客等待服務時間的總和除以n。

算法設計：對于給定的n個顧客需要的服務時間，計算最優服務次序。

數據輸入：由文件input.txt給出輸入數據。第一行是正整數n，表示有n個顧客。接下來的1行中，有n個正整數，表示n個顧客需要的服務時間。

結果輸出：將計算的最小平均等待時間輸出到文件output.txt中。

輸入文件示例 輸出文件示例input.txt output.txt10 56 12 1 99 1000 234 33 55 99 812 532.00

問題分析：假設原問題為T（先假設只有一個服務點），我們已知某個最優服務系列，即最優解為 A={t(1)，t(2)，…．t(n)} (其中t(i)為第i個用戶需要的服務時間)，則每個用戶等待時間為： T(1)=t(1)；T(2)=t(1)+t(2)；…T(n)=t(1)+t(2)+t(3)+…+t(n)；則總等待時問，即最優值為：

TA=T(1)+T(2)+T(3)+…+T(n)=n*t(1)+(n-1)*t(2)+…+(n+1-j)*t(i)+…+2*t(n-1)+t(n)；由于平均等待時間是n個顧客等待時間的總和除以n，故本題實際上就是求使顧客等待時間的總和最小的服務次序。

貪心策略： 最短服務時間優先，先將服務時間排序，然后注意后面的等待服務時間既包括等待部分，也包括服務部分。對服務時間最短的顧客先服務的貪心選擇策略，首先對需要服務時間最短的顧客進行服務，即做完第一次選擇后，原問題T變成了需對n-1個顧客服務的新問 題T’。新問題和原問題相同，只是問題規模由n減小為n-1。基于此種選擇策略，對新問題T’，選擇n-1顧客中選擇服務時間最短的先進行服務，如此進行 下去，直至所有服務都完成為止 。

算法實現： 采用最短服務時間優先的貪心策略。首先將每個顧客所需要的服務時間從小到大排序。然后申請2個數組： st[]是服務數組，st[j]為第j個隊列上的某一個顧客的等待時間；su[]是求和數組，su[j]的值為第j個隊列上所有顧客的等待時間。

算法復雜性分析 : 程序主要是花費在對各顧客所需服務時間的排序和貪心算法，即計算平均服務時間上面。其中，貪心算法部分只有一重循環影響時間復雜度，其時間復雜度為O(n)：而排序算法的時間復雜度為O(nlogn)。因此，綜合來看算法的時間復雜度為O(nlogn)。

代碼實現：

#include<iostream> #include <vector> #include<algorithm> using namespace std; using std::vector; double greedy(vector<int>x,int s){ vector<int>st(s+1,0); vector<int>su(s+1,0); int n=x.size(); sort(x.begin(),x.end()); int i=0,j=0; while(i<n){ st[j]+=x[i]; su[j]+=st[j]; i++; j++; if(j==s)j=0; } double t=0; for(i=0;i<s;i++) t+=su[i]; t/=n; return t; } int main(){ int n;//等待服務的顧客人數 int s;//服務點的個數 int i; int a; int t;//平均服務時間 vector<int>x; cout<<"請輸入顧客的人數: "<<endl; cin>>n; cout<<"請輸入服務點的個數: "<<endl; cin>>s; cout<<"請輸入每個顧客需要服務的時間: "<<endl; for(i=1;i<=n;i++){ cout<<"第"<<i<<"顧客: "<<endl; cin>>a; x.push_back(a); } t=greedy(x, s); cout<<"最小平均等待時間為: "<<t<<endl; }

運行結果：

汽車加油問題

問題描述：一輛汽車加滿油后,可行使nkm。旅途中有若干個加油站。設計一個有效算法，指出應在哪些加油站停靠加油才能使加油次數最少。并證明算法產生一個最優解。

算法設計：對于給定的n和k個加油站位置，計算最少加油次數。

數據輸入：由文件inpput.txt給出輸入數據。第1行有2個正整數n和k，表示汽車加滿油后可行駛nkm，且旅途中有k個加油站。接下來的1行中，有k+1個整數，表示第k個加油站與第k-1個加油站之間的距離。第0個加油站表示出發地，汽車已加滿油。第k+1個加油站表示目的地。

結果輸出：將計算的最少加油次數輸出到文件output.txt.如果無法到達目的地，則輸出”No Solution!”。

輸入文件示例 輸出文件示例input.txt output.txt7 7 41 2 3 4 5 6 6

問題分析： 有幾種情況：設加油次數為k，每個加油站間距離為a[i]；i=0，1，2，3……n

（1）始點到終點的距離小于n，則加油次數k=0。

（2）始點到終點的距離大于n。

A 加油站間的距離相等，即ａ[i]=a[j]=L=N，則加油次數最少k=n； B 加油站間的距離相等，即ａ[i]=a[j]=L>N，則不可能到達終點； C 加油站間的距離相等，即ａ[i]=a[j]=L<N，則加油次數k=n/N(n%N==0)或k=[n/N]+1(n%N！=0)； D 加油站間的距離不相等，即ａ[i]！=a[j]，則加油次數k通過以下算法求解。

算法思路：汽車行駛過程中，應走到自己能走到并且離自己最遠的那個加油站，在那個加油站加油后再按照同樣的方法貪心。

算法實現：先檢測各加油站之間的距離，若發現其中有一個距離大于汽車加滿油能跑的距離，則輸出no solution。否則，對加油站間的距離進行逐個掃描，盡量選擇往遠處走，不能走了就讓num++，最終統計出來的num便是最少的加油站數。

算法復雜性分析 ：想要知道在哪個加油站加油必須遍歷所有的加油站，且不需要重復遍歷，所以時間復雜度問O（n）。

代碼實現：

/*汽車加油問題 先檢測各加油站之間的距離，若發現其中有一個距離大于汽車加滿油能跑的距離，則輸出no solution否則，對加油站間的距離進行逐個掃描，盡量選擇往遠處走，不能走了就讓num++，最終統計出來的num便是最少的加油站數 */ #include <stdio.h> void greedy(int d[],int n,int k){ FILE *fp; int num = 0; for(int i = 0;i <= k;i++){ if(d[i] > n){ printf("no solution!其中有一個距離大于汽車加滿油能跑的距離！\n"); return; } } for(int i=0,s=0;i<=k;i++){ s += d[i]; if(s > n) { num++; s = d[i]; } } printf("最少加油次數為：%d\n",num);fp=fopen("output.txt","w");fprintf(fp,"%d",num); } int main(){ int i,n,k; int d[1000]; FILE *fp;fp=fopen("input.txt","r");fscanf(fp,"%d%d",&n,&k);printf("汽車加滿油后可行駛: %d km\n旅途中加油站個數為: %d \n",n,k); for(i=0;i<=k;i++)fscanf(fp,"%d",&d[i]); greedy(d,n,k);fclose(fp); return 0; }

文件input.txt的內容（運行程序前）：

output.txt內容（運行程序后）：

運行結果：

總結

以上是生活随笔為你收集整理的最优服务次序问题 和 汽车加油问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。