快餐问题HNOI99.docx
《快餐问题HNOI99.docx》由会员分享，可在线阅读，更多相关《快餐问题HNOI99.docx（8页珍藏版）》请在冰点文库上搜索。
快餐问题HNOI99
快餐问题（HNOI’99）
一、问题描述
Peter最近在R市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套餐由A个汉堡，B个薯条和C个饮料组成。
价格便宜。
为了提高产量，Peter从著名的麦当劳公司引进了N条生产线。
所有的生产线都可以生产汉堡，薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡，薯条和饮料的单位生产时间又不同。
这使得Peter很为难，不知道如何安排生产才能使一天中生产的套餐产量最大。
请你编一程序，计算一天中套餐的最大生产量。
为简单起见，假设汉堡、薯条和饮料的日产量不超过100个。
输入：
10
输入文件共四行。
第一行为三个不超过100的正整数A、B、C中间以一个空格分开。
第三行为3个不超过100的正整数p1,p2,p3分别为汉堡，薯条和饮料的单位生产耗时。
中间以一个空格分开。
第三行为N（0<=0<=10），第四行为N个不超过10000的正整数，分别为
各条生产流水线每天提供的生产时间，中间以一个空格分开。
输出：
输出文件仅一行，即每天套餐的最大产量。
输入输出示例：
Input2.txt
222
122
2
66
output.txt
1
二、分析
本题是一个非常典型的资源分配问题。
由于每条生产线的生产是相互独立，不互相影响的，所以此题可以以生产线为阶段用动态规划求解。
状态表示：
用p[I,j,k]表示前I条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。
用r[I,j,k]表示第I条生产线生产j个汉堡，k个薯条的情况下最多可生产饮料的个数。
态转移方程：
p[I,j,k]=Max{p[I-1,j1,k1]+r[I,j-j1,k-k1]}
（0<=j1<=j,0<=k1<=k,且（j-j1）*p1+（k-k1）*p2<=第I条生产线的生产时间）但这样的算法是非常粗糙的，稍加分析可以发现，此算法的时间复杂度为O（N*1004）,当N=10的时候，时间复杂度将达到10*1004=109，这是根本无法承受的。
于是，我们必须对算法进行进一步的优化，经仔细观察可以发现：
这道题中存在着一个上限值（Min{100divA,100divB,100divC}）,这是一个很好的判断条件，他可以帮我们尽早地求出最优解。
为什么这样说呢？
因为，在动态规划开始前，我们可以先用贪心法算出N条生产线可以生产的套数，如果大于上限值则可以直接输出上限值并退出。
否则再调用动态
规划，而在动态规划求解的过程中，也可以在每完成一阶段工作便和上限值进行比较，若大于等于上限值就退出，这样一来，就可以尽早的求出解并结束程序。
具体的算法流程为：
三、小结
动态规划虽然是种高效的算法，但不加优化的话，有可能在时间和空间上仍然有问题，
因此，在做题时要充分发掘题目中的隐含条件，并充分利用已知条件，这样才能令程序更快，
更优。
四．对程序优化的进一步讨论:
本题在具体实现中还有一些优化的余地，在此提出，以供参考：
（1）存储结构：
由于每一阶段状态只与上一阶段状态有关，所以我们可以只用两个
100*100的数组滚动实现。
但考虑到滚动是有大量的赋值，可以改进为动态数组，
每次交换时只需交换指针即可，这样比原来数组间赋值要快。
（2）减少循环：
在计算每一阶段状态过程中无疑要用到4重循环，其实这当中有很多
是可以省掉的，我们可以这样修改每一重循环的起始值：
原起始值：
改进后的起始值：
forI:
=1tondo
begin
forI:
=1tondobegin
forj:
=0totot[I]divp1do
forj:
=0tomin（q1,tot[I]divp1）do
fork:
=0to（tot[I]-p1*j）divp2do
fork:
=0tomin（q2,（tot[I]-p1*j）divp2）do
forj1:
=0tojdoforj1:
=max（0,j-t[I]divp1）to
min（j,tot[I-1]divp1）do
fork1:
=0tokdofork1:
=max（0,k-（t[I]-（j-j1）*p1）divp2）
tomin（k,（tot[I-1]-p1*j1）divp2）do
{注：
具体变量用途请参考程序}
五、参考程序
{$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q+,R+,S+,T-,V+,X+,Y+}
{$M65520,0,655360}
programFastFood;
const
input='input2.txt';
output='output2.txt';
var
f:
text;
r,p,pp:
array[0..100,0..100]ofinteger;｛pp:
滚动数组中存放前一阶段的数组｝
t,tot,tt:
array[0..10]oflongint;{tt:
辅助数组；t:
每条生产线的生产线时间；
tot:
1-I条生产线生产时间的总和}
n,a,b,c,p1,p2,p3:
longint;{a,b,c:
汉堡，薯条，饮料的个数；
p1,p2,p3汉堡，薯条，饮料的生产单位耗时}
procedureinit;
var
i:
integer;
begin
assign（f,input）;
reset（f）;
12
readln（f,a,b,c）;
readlN（f,p1,p2,p3）;
readln（f,n）;
fori:
=1tondoread（f,t[i]）;
close（f）;
ifn=0thenbegin{特殊情况处理}
assign（f,output）;
rewrite（f）;
writeln（f,0）;
close（f）;
halt;
end;
end;
functionmin（i,j:
longint）:
longint;{求两数中较小的一个}
begin
ifi>jthenmin:
=jelsemin:
=i;
end;
functionmax（i,j:
longint）:
longint;{求两数中较大的一个}
begin
ifi>jthenmax:
=ielsemax:
=j;
end;
proceduremain;
var
q,q1,q2,i,j,k,j1,k1:
longint;{q:
上限值；q1,q2:
A,B的上限值}
begin
q:
=min（100diva,min（100divb,100divc））;{求上限值}
q1:
=q*a;
q2:
=q*b;
tt:
=t;
i:
=1;
j:
=q1*p1;
while（j>0）and（i<=n）do{用贪心法求出N条生产线可以生产的套数（可行解）}
ifj>tt[i]thenbegin
dec（j,tt[i]）;tt[i]:
=0;inc（i）;
end
elsebegindec（tt[i],j）;j:
=0;end;
ifj=0thenbegin
j:
=q2*p2;
while（j>0）and（i<=n）do
ifj>tt[i]thenbegin
13
dec（j,tt[i]）;tt[i]:
=0;inc（i）;
end
elsebegindec（tt[i],j）;j:
=0;end;
ifj=0thenbegin{如果可行，直接输出上限值}
assign（f,output）;
rewrite（f）;
writeln（f,q）;
close（f）;
halt;
end;
end;
tot[0]:
=0;
fori:
=1tondotot[i]:
=tot[i-1]+t[i];
iftot[n]div（a*p1+b*p2+c*p3）q:
=tot[n]div（a*p1+b*p2+c*p3）;
q1:
=q*a;
q2:
=q*b;
end;
fori:
=1tondobegin
forj:
=0tomin（q1,t[i]divp1）do
fork:
=0tomin（q2,（t[i]-p1*j）divp2）do
r[j,k]:
=（t[i]-p1*j-p2*k）divp3;
fillchar（p,sizeof（p）,0）;{数组清零}
forj:
=0tomin（q1,tot[i]divp1）do
fork:
=0tomin（q2,（tot[i]-p1*j）divp2）do
forj1:
=max（0,j-t[i]divp1）tomin（j,tot[i-1]divp1）do
fork1:
=max（0,k-（t[i]-（j-j1）*p1）divp2）tomin（k,（tot[i-1]-p1*j1）divp2）do
ifp[j,k]p[j,k]:
=pp[j1,k1]+r[j-j1,k-k1];
ifp[q*a,q*b]>=q*cthenbegin
{如果在此阶段产生了不小于上限值的解，则之际输出上限值，并直接退出}
assign（f,output）;
rewrite（f）;
writeln（f,q）;
close（f）;
halt;
end;
pp:
=p;
forj:
=0tomin（100,tot[i]divp1）do
fork:
=0tomin（100,（tot[i]-p1*j）divp2）do
ifp[j,k]>100thenp[j,k]:
=100;
end;
{out}
k1:
=0;{输出最优值}
14
forj:
=0to100do
if（jdiva>k1）then
fork:
=0to100do
if（kdivb>k1）and（p[j,k]divc>k1）then
k1:
=min（min（jdiva,kdivb）,p[j,k]divc）;
assign（f,output）;
rewrite（f）;
writeln（f,k1）;
close（f）;
end;
begin
init;
main;
end
升级会员 