最优服务次序问题
设有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
八、收获及体会
本题将顾客平均等待时间最小,转化为服务等待时间总和最小。利用局部最优,通过贪心算法来解决该题。
通过本题,也更深入了解贪心算法的本质,今后对于其他类似的局部最优问题、最优子结构问题,都可采用贪心算法解决。
最优服务次序问题
设有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
八、收获及体会
本题将顾客平均等待时间最小,转化为服务等待时间总和最小。利用局部最优,通过贪心算法来解决该题。
通过本题,也更深入了解贪心算法的本质,今后对于其他类似的局部最优问题、最优子结构问题,都可采用贪心算法解决。