Cod sursa(job #742931)
Utilizator | Pojoga Vasile vasile_pojoga | Data | 2 mai 2012 09:03:02 |
---|---|---|---|
Problema | Problema rucsacului | Scor | 50 |
Compilator | fpc | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
program geanta;
var w,p:array[1..5000] of integer;
d:array[0..5000,0..10000] of longint;
n,i,j,g:integer;
begin
assign(input,'rucsac.in'); reset(input);
assign(output,'rucsac.out'); rewrite(output);
readln(n,g);
for i:=1 to n do readln(w[i],p[i]);
close(input);
for i:=1 to n do
for j:=0 to g do
begin
d[i,j]:=d[i-1,j];
if (j>=w[i])and(d[i-1,j-w[i]]+p[i]>d[i,j]) then d[i,j]:=d[i-1,j-w[i]]+p[i];
end;
write(d[n,g]);
close(output);
end.