設有n個顧客同時等待同壹項服務。顧客i需要的服務時間為ti,1
參考答案
壹、最優服務次序問題
二、運行環境（軟、硬件環境）
運行軟件：Window7 64位
硬件：華碩PC機
編寫程序：C++語言
編譯環境：VC++6.0
三、算法設計的思想
首先，要使n個顧客平均等待時間最小，即為：讓n個顧客等待服務時間總和最小。因為，平均等待時間=等待服務時間總和/n。
接著，由於每個顧客i的服務時間為ti,要實現等待服務時間總和最小，應該盡可能安排ti值小的顧客，進行服務。
因此，本題屬於局部最優的設計問題，即為貪心算法。
四、算法的流程圖
第
五、算法設計分析
假設原問題的時間為T，已經知道了某個最優服務系列，最優解為min={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(n)；
那麽，總的等待時間，即為最優解
T min=n*t(1)+(n-1)*t(2)+(n-2)*t(3)......+(n+1-i)*t(i)+......+2*t(n-1)+1*t(n)；
由於，平均等待時間是n個顧客等待時間總和除以n，則本題轉化為求使得顧客等待時間總和最小的服務次序問題。
六、源代碼
#include
#include
#include
#include
long n=-1； //顧客數為n
long *wait； //顧客各自等待時間wait
void inputData ()
{ //輸入數據n，等待時間wait
ifstream fin；
fin．open(*input．txt’，los::nocreate)；
if(!fin){
cout
return；
}
fin>>n；
wait==new long[n]；
for(1ong i=0；i
{
fin>>wait[i]；
)
fin．close0；
}
void ShellSort(long *x)
( //Shell排序，實現數據從小到大排序 long i，j，temp．gap=n／2；
while(gap>0){
for(i=gap；i
j=i-gap；
while(j>=0){
if(x[j]>x[j+gap])
{
temp=x[j]；x[j]=x[j+gap]；x[j+gap]=temp； //實現大小交換
j=j-gap；
}
else{j=-1；}
}
}
gap=gap／2；
}
}
／**
函數名：AveWait0
描述：計算平均等待時問
參數：各顧客等待時間
**／
double AveWait(long *x)
{
double ave=0.0；
ShellSort(x)；
for(long i=0；i
{
ave+=1.0*(n-i)*x[i]；
}
ave／=n； //求平均等待時間
return ave；
)
void outputData(double out)
( //輸出結果
ofstream fout；
fout．open("output．txt")；
fout
fout．close0；
)
void main0
{ //主調函數
inputData()；
if(n!=-1)(
double avewait=AveWait(wait)；
outputData(avewait)：
}
}
七、運行結果分析
試驗結果：
input．txt：
12 56 22 l9 90 1002 234 33 45 97 810
output．txt：
532．00
八、收獲及體會
本題將顧客平均等待時間最小，轉化為服務等待時間總和最小。利用局部最優，通過貪心算法來解決該題。
通過本題，也更深入了解貪心算法的本質，今後對於其他類似的局部最優問題、最優子結構問題，都可采用貪心算法解決。