pascal DAP问题

来源：百度知道 编辑：UC知道 时间：2024/05/20 04:06:07
DAP就是有个n数，从中选出几个，和正好为m。输出最少加数的个数，并在下一行输出加数。要求用动态规划!

var
n,m,x,i,j:longint;
a,l:array[0..1000]of longint;{l指加的路径}
begin
readln(n,m);
for i:=1 to m do a[i]:=-1;
a[0]:=0;
for i:=1 to n do begin
readln(x);
for j:=m-x downto 0 do
if a[j]>=0 then
if (a[j+x]>a[j]-1)or(a[j+x]=-1) then begin
a[j+x]:=a[j]+1;
l[j+x]:=j;
end;
end;
writeln(a[m]);
x:=m;
repeat
write(x-l[x],' '); x:=l[x];
until x=0;
writeln;
end.