二维：var n,m,i,j:integer;
w,v:array[1..200] of integer;
h:array[0..200,0..30] of integer;function max(x,y:integer):integer;begin
if x>y then max:=x else max:=y;end;beginreadln(n,m);for i:=1 to n doread(w,v);for i:=1 to n do h[0,i]:=0;for i:=1 to m do h[i,0]:=0;for i:=1 to n do
for j:=1 to m do
if j>=w then h[i,j]:=max(h[i-1,j-w]+v,h[i-1,j])
else h[i,j]:=h[i-1,j];{其实最好直接比较而不是用函数-函数会慢很多。这里为了给你看时直观些，就用了一个函数}writeln(h[n,m]);end.优化空间（一维）后：var v,w,bag:array[0..1000]of longint;
n,total,i,j:longint;beginfillchar(bag,sizeof(bag),0);readln(n,total);for i:=1 to n do readln(w,v);for i:=1 to n do
for j:=total downto w do
if bag[j]0 thenbegin writeln(bag);break;end;end. 程序中的状态为什么是倒序而不是顺序呢？对于样例数据，请看分析过程： 首先，解释一下要倒序的原因：由于01背包每种物品只能选一件所以在迭代算法中顺序的话会更改了上一次前面的数据简单的说 就是一个物品会被选多次因此用倒序其次，楼下做的不是记忆化搜索而是dp（动归）记忆化搜索主要部分 不是程序别抄f(i,j)表示前i件物品还剩j容量function f(i,j:integer):longint;if i>n then exit(0);if f1[i,j]0 then exit(f1[i,j]); x2 then
f:=x1else
f:=x2f1[i,j]:=f nthenexit(0);iff1[i,j]0thenexit(f1[i,j]);x2thenf:=x1elsef:=x2f1[i,j]:=f<==记录 |
