f:array[0..10000,0..10000] of longint;

w,c:array[0..100000] of longint;

function max(x,y:longint):longint;

begin

if x>y then

exit(x)

else

exit(y);

end;

begin

readln(m,n);

for i:=1 to n do

readln(w[i],c[i]);

for i:=1 to n do

for j:=m downto 0 do

if j>=w[i] then

f[i,j]:=max(f[i-1,j-w[i]]+c[i],f[i-1,j])

else

f[i,j]:=f[i-1,j];

writeln(f[n,m]);

end.

与

var i,j,n,t:longint;

v,w,f:array[1..100]of longint;

function max(i,j:longint):longint;

begin if i>j then exit(i)

else exit(j); end;

begin

read(t,n);

for i:= 1 to n do

read(v[i],w[i]);

fillchar(f,sizeof(f),0);

for i:= 1 to n do

for j:= t downto v[i] do

f[j]:=max(f[j-v[i]]+w[i],f[j]);

writeln(f[t]);

end.

1、 阶段i：前i个物品中选取物品放入到背包中。

2、 状态c[I,j]：前i个物品中选取物品放入到容量为j的背包中所能获得的最大价值。

3、 动规方程：c[I,0]=0；c[0,i]=0

c[I,j]=max{c[i-1,j-w[i]]+p[i](j>=w[i])，c[i-1,j]}

(1<=i<=n, 1<=j<=m)

Answer:c[n,m]