POJ 2184(01背包+滚动数组）

01背包 模板题

Program dd;
const
   maxn=1000;
   maxv=100000;
   minv=-100000;
   NULL=-2139062144;
var
   n,i,j,ans,p,np:longint;
   ts,tf:array[1..maxn] of longint;
   f:array[0..1,minv..maxv] of longint;
function max(a,b:longint):longint;
begin
   if a<b then exit(b) else exit(a);
end;
begin
   read(n);
   for i:=1 to n do read(ts[i],tf[i]);
   fillchar(f,sizeof(f),128);
   f[0,0]:=0;
   for i:=1 to n do
   begin
      p:=i mod 2;
      fillchar(f[p],sizeof(f[p]),128);
      np:=(p+1) mod 2;

      for j:=maxv downto minv do
      begin
         f[p,j]:=f[np,j];
         if (minv<=j-ts[i]) and (j-ts[i]<=maxv) then
            if (f[np,j-ts[i]]<>NULL) then
               f[p,j]:=max(f[p,j],f[np,j-ts[i]]+tf[i]);



      end;
   end;


   ans:=0;
   for i:=0 to maxv do
      if (f[n mod 2,i]>=0) and (ans<f[n mod 2,i]+i) then ans:=f[n mod 2,i]+i;

   writeln(ans);

end.