01背包算法.. [复制链接]

    谁能教我一下01背包算法   
  2005和2006NOIP的普及都有01背包的题..
    希望大家教我一下01背包.....
  尽量详细点..........................................感激不尽..
  本人QQ416675069...

主要用动态规划.

var
  time,m:integer;t:array [1..1000] of integer;v:array [1..100] of integer;
  a:array [0..100,0..1000] of integer;
  i,j:integer;
begin
  readln(time,m);
  for i:=1 to m do
    begin
    read(t);readln(v);
    end;
  for i:=1 to m do
    for j:=1 to time do
      if j>=t then if a[i-1,j]>a[i-1,j-t]+v then a[i,j]:=a[i-1,j]
                                                    else a[i,j]:=a[i-1,j-t]+v
                else a[i,j]:=a[i-1,j];
  write(a[m,time]);
end.
这是采药问题，完全的01背包，你可以把t当作重量，v当作价值

递推也行

用递归
程序如下:
program knapsack04;
const maxm=2000;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
p:array[0..maxm] of integer;
function f(x:integer):integer;
var i,t,m:integer;
begin
if p[x]<>-1 then f:=p[x]
else
begin
if x=0 then p[x]:=0 else
begin
t:=-1;
for i:=1 to n do
begin
if x>=w then m:=f(i-w)+c;
if m>t then t:=m;
end;
p[x]:=t;
end;
f:=p[x];
end;
end;
begin
readln(m,n);
for i:= 1 to n do
readln(w,c);
fillchar(p,sizeof(p),-1);
writeln(f(m));
end.

状态设置为穷举到第几个物品，还剩多少空间。

然后穷举到一个物品的时候就有2种情况：拿和不拿。

比如说穷举到第4个物品，还剩32，这个物品为12空间，14价值。

那么取了，就转化为5个物品，还剩20。同时价值加上14
不取，就转化为5个物品，还剩32

其实动态规划很简单，就和穷举差不多，就是要把每一个状态的当前的值记下来。避免重复计算。