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

Tác giả: ladpro98

Ngôn ngữ: Pascal

uses    math;
var     n, m, i, z, vv, t, tt, j: longint;
        f: array[0..10005, 0..1005] of longint;
        w, v, res: array[0..10005] of longint;

begin
        read(t);
        while (t > 0) do begin
                read(n, m);
                for i := 1 to n do read(w[i]);
                for i := 1 to n do read(v[i]);
                for i := 0 to m do f[0][i] := 0;
                for i := 1 to n do
                for j := 0 to m do begin
                        f[i][j] := f[i - 1][j];
                        if (j >= w[i]) then
                                f[i][j] := max(f[i - 1][j], f[i - 1][j - w[i]] + v[i]);
                end;
                vv := f[n][m];
                z := 0;
                while (n <> 0) do begin
                        if (f[n][m] <> f[n - 1][m]) then begin
                                z := z + 1;
                                res[z] := n;
                                dec(m, w[n]);
                        end;
                        n := n - 1;
                end;
                writeln(vv, ' ' , z);
                for i := 1 to z do write(res[i],' ');
                writeln;
                t := t - 1;
        end;
end.

Download