一、问题描述
已知三个函数A,B,C值如下表所示。自变量取值为0-10的整数。 请用动态规划的方法求出一组x,y,z。使得A(x)+B(y)+C(z)为最大,并且满足x*x+y*y+z*z<N，N由键盘输入。
X 0 1 2 3 4 5 6 7 8 9 10
A(x) 2 4 7 11 13 15 18 22 18 15 11
B(x) 5 10 15 20 24 18 12 9 5 3 1
C(x) 8 12 17 22 19 16 14 11 9 7 4
二、思路分析
本题已经说明了算法是动态规划，我们接下来要做的就是求他的状态转移方程。稍加分析可得到状态转移方程：
F[I,j]=max(f[i-1,j-x*x]+p[I,x]);
其中，A(X)=p[1,x], B(X)=P[2,X], C(X)=P[3,X];
F[I,J]表示前I个函数的自变量平方和为j时函数和的最大值。易证，此规划方程满足无后效性。得到函数最大值后，我们再用自底向上追溯的方法求出X,Y,Z,的值,具体实现请看程序。
三、参考程序
program CTSC_95_4;
const
f : array[1..3,0..10] of integer = {函数}
((2, 4, 7, 11, 13, 15, 18, 22, 18, 15, 11),
(5, 10, 15, 20, 24, 18, 12, 9, 5, 3, 1),
(8, 12, 17, 22, 19, 16, 14, 11, 9, 7, 4));
var
s : array[1..3,0..300] of longint; {状态S[I,J]表示前I个函数自变量值的平方和为j时函数和的最大值}
pre: array[1..3,0..300] of integer; {前驱数组，保存该状态是由上阶段哪个状态得到的}
n : longint;
procedure main;
var
i,j,k,p,x,y,z : integer;
begin
write('n='); readlN(n);
if n>301 then n:=301; {如果N>301(10*10+10*10+10*10)则N=301}
fillchar(s,sizeof(s),0);
fillchar(pre,sizeof(pre),0);
for i := 0 to 10 do s[1,i*i] := f[1,i];
for i := 1 to 2 do
for j := 0 to n-1 do begin
if s[i,j] > s[i+1,j] then
begin s[i+1,j] := s[i,j]; pre[i+1,j] := j; end;
for k := 0 to 10 do
if s[i,j]+f[i+1,k]>s[i+1,j+k*k] then begin
p := j+k*k;
if p>=n then break;
pre[i+1,p] := j;
s[i+1,p] := s[i,j]+f[i+1,k];
end;
end;
p := 0; k := 0;
for i := 0 to n-1 do
if s[3,i]>k then begin
k := s[3,i]; p := i;
end;
z := trunc(sqrt(p-pre[3,p])); p := pre[3,p]; {求出Z}
y := trunc(sqrt(p-pre[2,p])); p := pre[2,p]; {求出Y}
x := trunc(sqrt(p)); {求出X}
writeln('Max=',k);
writeln('A=',x,',','B=',y,',','C=',z);
end;
begin
main;
end.