用贪心算法求解最优服务次序问题
发布时间：2024-10-30
贪心算法
最优服务次序问题：设有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])
贪心算法
pos=i;
return pos;
}
void Swap(int x,int y)
{
int temp;
temp=x;x=y;y=temp;
}
void Selectsort(int a[],int n)
{
for(int size=n;size>1;size--)
{
int j=Max(a,size);
Swap(a[j],a[size-1]);
}
}
int Partition(int a[],int p,int r) {
int i=p,j=r+1,x=a[p];
while(true)
{
while(a[++i]<x&&i<=r);
while(a[--j]>x);
if(i>=j)break;
Swap(a[i],a[j]);
}
a[p]=a[j];
a[j]=x;
return j;
}
void Quicksort(int a[],int p,int r) {
if(r-p<=9)
Selectsort(&a[p],r-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>>a[i];
}
//文件尾:
Quicksort(a,0,n-1);
double num=0;
for(i=0;i<n;i++)
num+=a[i]*(n-i);
num=num/n;
out<<setiosflags(ios::fixed);
out<<setprecision(2)<<num<<endl;
}
/***************input.txt***************** 10
2
4
3
3
9
7
5
5
3
1
****************output.txt**************** 16.90
*****************************************/
贪心算法
最优服务次序 #include<iostream> #include<cstdio> #include<algorithm> #include<vector> #include<iomanip> using namespace std; int x[10000]; 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",&x[j]); } // sort(x.begin(),x.end()); sort(x,x+n); for(int i = 1; i < n; i++) x[i]+=x[i-1]; double t = 0; for(int i = 0; i < n; i++) t+=x[i]; t/=n; cout.setf(ios::fixed); cout << setprecision(2) << t << endl; system("pause");
return 0;
