快餐问题HNOI99.docx

1、快餐问题HNOI99快餐问题（HNOI99）一、问题描述Peter 最近在R 市开了一家快餐店，为了招揽顾客，该快餐店准备推出一种套餐，该套餐由A 个汉堡，B 个薯条和C 个饮料组成。价格便宜。为了提高产量，Peter 从著名的麦当劳公司引进了N 条生产线。所有的生产线都可以生产汉堡，薯条和饮料，由于每条生产线每天所能提供的生产时间是有限的、不同的，而汉堡，薯条和饮料的单位生产时间又不同。这使得Peter 很为难，不知道如何安排生产才能使一天中生产的套餐产量最大。请你编一程序，计算一天中套餐的最大生产量。为简单起见，假设汉堡、薯条和饮料的日产量不超过100 个。输入：10输入文件共四行。第一行

2、为三个不超过100 的正整数A、B、C 中间以一个空格分开。第三行为3 个不超过100 的正整数p1,p2,p3 分别为汉堡，薯条和饮料的单位生产耗时。中间以一个空格分开。第三行为N(0=0=10)，第四行为N 个不超过10000 的正整数，分别为各条生产流水线每天提供的生产时间，中间以一个空格分开。输出：输出文件仅一行，即每天套餐的最大产量。输入输出示例：Input2.txt2 2 21 2 226 6output.txt1二、分析本题是一个非常典型的资源分配问题。由于每条生产线的生产是相互独立，不互相影响的，所以此题可以以生产线为阶段用动态规划求解。状态表示： 用pI,j,k表示前I 条生

3、产线生产j 个汉堡，k 个薯条的情况下最多可生产饮料的个数。用rI,j,k表示第I 条生产线生产j 个汉堡，k 个薯条的情况下最多可生产饮料的个数。态转移方程： pI,j,k = MaxpI-1,j1,k1+rI,j-j1,k-k1(0=j1=j,0=k1=k,且（j-j1）*p1+(k-k1)*p2j then min := j else min := i;end;function max(i,j : longint) : longint; 求两数中较大的一个beginif ij then max := i else max := j;end;procedure main;varq,q1,q

4、2,i,j,k,j1,k1 : longint; q:上限值；q1,q2 : A,B 的上限值beginq := min( 100 div a,min( 100 div b, 100 div c ) ); 求上限值q1 := q*a;q2 := q*b;tt := t;i := 1;j := q1*p1;while (j0) and (itti then begindec(j,tti); tti := 0; inc(i);endelse begin dec(tti,j); j := 0; end;if j=0 then beginj := q2*p2;while (j0) and (itti

5、then begin13dec(j,tti) ;tti := 0; inc(i);endelse begin dec(tti,j); j := 0; end;if j=0 then begin 如果可行，直接输出上限值assign(f,output);rewrite(f);writeln(f,q);close (f);halt;end;end;tot0 := 0;for i := 1 to n do toti := toti-1 + ti;if totn div (a*p1+b*p2+c*p3)q then begin 否则修改上限值q := totn div (a*p1+b*p2+c*p3)

6、;q1 := q*a;q2 := q*b;end;for i := 1 to n do beginfor j := 0 to min(q1,ti div p1) dofor k := 0 to min(q2,(ti-p1*j) div p2) dorj,k := (ti-p1*j-p2*k) div p3;fillchar(p,sizeof(p),0); 数组清零for j := 0 to min(q1,toti div p1) dofor k := 0 to min(q2,(toti-p1*j) div p2) dofor j1 := max(0,j-ti div p1) to min(j,

7、toti-1 div p1) dofor k1 := max(0,k-(ti-(j-j1)*p1) div p2) to min(k,(toti-1-p1*j1) div p2) doif pj,k =q*c then begin如果在此阶段产生了不小于上限值的解，则之际输出上限值，并直接退出assign(f,output);rewrite(f);writeln(f,q);close (f);halt;end;pp := p;for j := 0 to min(100,toti div p1) dofor k := 0 to min(100,(toti-p1*j) div p2) doif pj,k 100 then pj,k := 100;end; out k1 := 0; 输出最优值14for j := 0 to 100 doif (j div a k1) thenfor k := 0 to 100 doif (k div b k1) and (pj,k div c k1 ) thenk1 := min( min( j div a, k div b), pj,k div c );assign(f,output);rewrite(f);writeln(f,k1);close (f);end;begininit;main;end