p1059.pas

www.vijos.cn上一些习题的参考源码

program p1059;
var
    cas:array[1..100,1..100] of integer;
    n,i,k:integer;
    len:array[1..100] of integer;
    high:array[1..100] of longint;
    min,max,v:longint;
    ok:boolean;
    
function knap(k:integer; v:integer):boolean;
var
    f0,f1:array[0..10000] of boolean;
    i,j:integer;
begin
    fillchar(f0,sizeof(f0),0);
    f0[0]:=true;
    for i:=len[k] downto 1 do begin
        f1:=f0;
        for j:=cas[k,i] to v do
            if f0[j-cas[k,i]] then f1[j]:=true;
        f0:=f1;
    end;
    {f[0]:=true;
    for i:=0 to n do begin
        for j:=1 to len[k] do begin
            if f[i] then
                f[i+cas[k,j]]:=true;
        end;
    end;}
    if f1[v] then knap:=true
    else knap:=false;
end;


begin
    readln(n);
    fillchar(cas,sizeof(cas),0);
    min:=maxint;
    for i:=1 to n do begin
        read(k);
        len[i]:=0; high[i]:=0;
        while (k<>-1) do begin
            inc(len[i]);
            cas[i,len[i]]:=k;
            inc(high[i],k);
            read(k);
        end;
        if high[i]<min then min:=high[i];
        readln;
    end;

    max:=0;
    for v:=min downto 0 do begin
        ok:=true;
        for i:=1 to n do begin
            if not knap(i,v) then begin
                ok:=false;
                break;
            end;
        end;
        if ok then begin max:=v;break;end;
    end;
    
    writeln(max);

end.