HUGEKNAP - Cái túi ( Hard version )

Tác giả: flashmt

Ngôn ngữ: Pascal

const fi='';
      fo='';
      maxn=10001;
var n,re,s,test,it:longint;
    w,v,res:array[1..maxn] of longint;
    f:array[0..1,0..1000] of longint;
    tr:array[0..maxn,0..1000] of boolean;

procedure rf;
var i:longint;
begin
     read(n,s);
     for i:=1 to n do read(w[i]);
     for i:=1 to n do read(v[i]);
end;

procedure pr;
var i,j,z:longint;
begin
     fillchar(f,sizeof(f),0);
     for i:=1 to n do
     begin
          z:=i and 1;
          for j:=0 to w[i]-1 do 
          begin
               f[z,j]:=f[1-z,j];
               tr[i,j]:=false; 
          end;
          for j:=w[i] to s do
              if f[1-z,j]<f[1-z,j-w[i]]+v[i] then
              begin
                   f[z,j]:=f[1-z,j-w[i]]+v[i];
                   tr[i,j]:=true;
              end
              else
              begin
                   f[z,j]:=f[1-z,j];
                   tr[i,j]:=false;
              end;
     end;
end;

procedure wf;
var i,j,dem,jj:longint;
begin
     re:=0;
     for jj:=0 to s do
         if f[n and 1,jj]>re then
         begin
              re:=f[n and 1,jj];
              j:=jj;
         end;
     dem:=0; i:=n;
     while j>0 do
     begin
          if tr[i,j] then
          begin
               dem:=dem+1;
               res[dem]:=i;
               j:=j-w[i];
          end;
          dec(i);
     end;
     writeln(re,' ',dem);
     for j:=dem downto 1 do write(res[j],' ');
     writeln;
end;

begin
     assign(input,fi); reset(input);
     assign(output,fo); rewrite(output);
     read(test);
     for it:=1 to test do
     begin
          rf;
          pr;
          wf;
     end;
     close(input); close(output);
end.

Download