HUGEKNAP - Cái túi ( Hard version )
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+}
uses math;
const
FINP='';
FOUT='';
MAXN=10000;
MAXM=1000;
type
list=^node;
node=record
u,v,val:longint;
next:list;
end;
arr=array[1..MAXN,1..MAXM] of longint;
arr2=array[0..MAXN] of longint;
arr3=array[0..MAXM] of longint;
var
f1,f2:text;
luuu,luuv,kq,m,n,test:longint;
v,w:^arr2;
ln,last:arr3;
trace:^arr;
procedure openF; inline;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
close(f1); close(f2);
end;
procedure inp; inline;
var
i:longint;
begin
read(f1,n,m);
for i:=1 to n do read(f1,w^[i]);
for i:=1 to n do read(f1,v^[i]);
end;
procedure solve;
var
i,x,temp:longint;
begin
fillchar(ln,sizeof(ln),0);
fillchar(last,sizeof(last),0);
for i:=1 to n do
for x:=m downto w^[i] do
if (x=w^[i]) or (last[x-w^[i]]<>0) then
begin
temp:=ln[x-w^[i]]+v^[i];
if temp>ln[x] then
begin
ln[x]:=temp;
last[x]:=i;
trace^[i,x]:=last[x-w^[i]];
end;
end;
kq:=0;
for i:=1 to m do
if ln[i]>kq then
begin
kq:=ln[i];
luuu:=last[i];
luuv:=i;
end;
end;
procedure ans; inline;
var
u,v,k,count:longint;
begin
write(f2,kq,' ');
u:=luuu; v:=luuv;
count:=0;
while v>0 do
begin
k:=trace^[u,v];
inc(count);
v-=w^[u]; u:=k;
end;
writeln(f2,count);
u:=luuu; v:=luuv;
while v>0 do
begin
k:=trace^[u,v];
write(f2,u,' ');
v-=w^[u];
u:=k;
end;
writeln(f2);
end;
begin
openF;
read(f1,test);
getMem(trace,MAXM*MAXN*sizeof(longint));
getMem(v,sizeof(arr2));
getMem(w,sizeof(arr2));
for test:=1 to test do
begin
inp;
solve;
ans;
end;
freeMem(trace,MAXN*MAXM*sizeof(longint));
freeMem(v,sizeof(arr2));
freeMem(w,sizeof(arr2));
closeF;
end.