讨论 / 正解
烂笔头 2010-10-31 03:07:00
点我顶贴 收藏 删除
因为本题有明显的阶段性,又是最优化问题,故首先考虑用动态规划求解。定义F[i](n)为n克原料做第i至第m次试验所或最大利润。

X[i](n)为第i次实验做A的原料重量,并令p=1-p; q:=1-q;

则F[i](n)=aX[i]+b(n-Xi)+f[i+1](pX[i]+q(n-X[i]))

=(a-b)X[i]+bn+F[i+1]((p-q)X[i]+qn)

边界条件:F[m](n)=max{a,b}*n

但发现F[i](n)中,n、X[i]都是实数,无法一一枚举,故不能直接求解。

让我们换个方向思考:

因为F[m](n)=max{a,b}*n

若设C[m]=max(a,b),则F[m](n)=C[m]*n

那么,F[m-1](n)=(a-b)X[m-1]+bn+F[m]((p-q)X[m-1]+qn)

=(a-b)X[m-1]+bn+C[m]*((p-q)X[m-1]+qn)

=(a-b+C[m]p-C[m]q)X[m-1]+(b+C[m]q)n

因为0<=X[m-1]<=n,所以,当a-b+C[m]p-C[m]q<=0时,X[m-1]取0,此时F[m-1](n)=(b+C[m]q)n,

否则,X[m-1]取n,此时F[m-1](n)=(a+C[m]p)n。

我们设C[m-1]=max{a-b+C[m]p-C[m]q,0}+b+C[m]q,则F[m-1](n)=C[m-1]*n

一般的,我们已知C[i],可以计算出C[i-1],而C[m]已知,所以可以算出C[1],那么F[1](n)=C[1]*n。

程序:

var

a,b,n,m,i:integer;

p,q,c,d:real;

f:array[1..10000] of real;

begin

assign(input,'b.in');

reset(input);

readln(m,n,a,b,p,q);

close(input);

p:=1-p;

q:=1-q;

if a>b

then f[m]:=a

else f[m]:=b;

for i:=m-1 downto 1 do

begin

c:=(a-b)+f[i+1]*(p-q);

d:=b+f[i+1]*q;

if c<=0

then f[i]:=d

else f[i]:=c+d;

end;

assign(output,'b.out');

rewrite(output);

writeln(f[1]*n:0:5);

close(output);

end.

查看更多回复
提交回复