贪心算法

最优服务次序问题：设有n个顾客同时等待同一项服务，顾客i需要的服务时间为ti，n>=i>=1，应如何安排这n个顾客的服务次序才能使平均等待时间达到最小。平均等待时间是n个顾客等待服务时间的总和除以n。

贪心选择策略

假设原问题为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=n。t(1)+(rrl)‘t(2)十…+(n+l—i)‘t(i)+…2’t(n-1)+t(n)

由于平均等待时问是n个顾客等待时间的总和除以n，故本题实际上就是求使顾客等待时间的总和最小的服务次序。本问题采用贪心算法求解，贪心策略如下：对服务时间最的顾客先服务的贪心选择策略。首先对需要服务时问最短的顾客进行服务，即做完第一次选择后，原问题T变成了需对n-1个顾客服务的新问题T’。新问题和原问题相同，只是问题规模由n减小为n一1。基于此种选择策略，对新问题T’，选择n-l顾客中选择服务时间最短的先进行服务．如此进行下去，直至所有服务都完成为止。

#include<fstream．h>

#nclude<iostream．h>

#include<stdlib．h>

#include<iomanip．h>

long n：_1： ／／顾客数n

Long *wait； N各自等待时间

void inputData O

{／／输入数据n、wait

ifstream fin；

fin．open(*input．txt’，los::nocreate)；

if(!fin){

cout<<“File Open Error!"<<endl；

return；

}

fin>>n；

Wait==new long[n]；

for(1ong i=0；i<n；i十十)

{

fin>>wait[i]；

)

fin．close0；

}

void ShellSort(10ng *a)

(//Shell排序，实现数据从小到大排序

贪心算法

long i，j，x．gap=n／2；

while(gap>0){

for(i=gap；i<n；i++){

j=i-gap；

while(J>=0){

if(a[J]>a[j+gap])

{

x=a[j]；a[j]=a[j+gap]；a[j+gap]=x；

j=j-gap；

}

else{j一1；}

}

}

gap=gap／2；

}

}

／

函数名：AveWait0

描述：计算平均等待时问

参数：各顾客等待时间

／

double AveWait(10ng *a)

{

double ave=0.0； ’

ShellSort(a)； ．

for(10ng i=0；i<n；i++)

{

ave+=1．0*(n-i)*a[i]；

}

ave／=n；

return ave；

)

void outputData(double out)

(∥输出结果

ofstream fout；

fout．open("output．Txt")；

fout<<setiosflags(ios：：fixed)<<setprecision(2)

<<out<<endl；

fout．close0；

)

void main0

{//主调函数

inputData()；

贪心算法

if(n!=-1)(

double avewait=AveWait(wait)；

outputData(avewait)：

}

}

试验结果：

input．txt：

10 56 12 l 99 1000 234 33 55 99 812

output．txt：’

532．00

多处最优服务次序问题：设有n个顾客同时等待一项服务。顾客i需要的服务时间为ti，1<=i<=n。共有s处可以提供此项服务。应如何安排n个顾客的服务次序才能使平均等待时间达到最小？平均等待时间是n个顾客等待服务时间的总和除以n。(输入的数据要求从文件input.txt中读到程序中，输出结果要求写入文件output.txt中。)

法一：

#include<iostream>

#include<fstream>

using namespace std;

void CountingSort(int t[],int n,int r[],int e,int q[])

{

int i; //计数排序

for( i=0;i<e;i++)

q[i]=0;//把数组元素全部赋初值为0

for( i=0;i<n;i++)

q[t[i]]+=1;//判断累计相同等待时间的个数 q[t[i]]=q[t[i]]+1;

for( i=1;i<e;i++)

q[i]+=q[i-1];//q[i]=q[i]+q[i-1]

for( i=n;i>0;i--)//将顾客等待时间从小到大排列

{

r[q[t[i-1]]-1]=t[i-1];

q[t[i-1]]-=1;

}

}

void main()

{

int i=0,sum=0,n,max=0,u;//n为顾客个数

float vt,p;

贪心算法

ifstream in("input.txt");

if(in.fail())

{

cout<<"input error!"<<endl;

exit(1);//抛出一个异常窗口

}

ofstream out("output.txt");

out.setf(ios::fixed); //对输出设置精度

out.precision(2);

in>>n;

//new是给指针r分配n长度的空间，设置动态数组r,m，两个数组大小相同 int *r=new int[n];

int *t=new int[n];

for(i=0;i<n;i++)

in>>t[i];//从文本给等待时间t[i]数组赋值

for(i=0;i<n;i++)

{

if(max<t[i])

max=t[i];//找出最大的等待时间

}

u=max; //u为所有顾客中最长的等待时间

int *q=new int[u+1]; //动态数组用于计数排序,减少排序时间

CountingSort(t,n,r,u+1,q);//调用CountingSort（）函数

for(i=0;i<n;i++)

{

sum+=r[i]*(n-i);

}

//文件尾:

p=(float)sum;//顾客等待服务时间的总和sum转换成浮点数赋给p vt=p/n;// 计算平均等待时间

out<<vt<<endl;

}

法二：

#include<iostream>

#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(a[pos]<a[i])

贪心算法