01背包问题

0/1背包

一个旅行者有一个最多能用m公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn,它们的价值分别为C1,C2,...,Cn.若每种物品只有一件求旅行者能获得最大总价值。

<1>分析说明:

显然这个题可用深度优先方法对每件物品进行枚举(选或不选用0,1控制).

程序简单,但是当n的值很大的时候不能满足时间要求，时间复杂度为O（2n）。按递归的思想我们可以把问题分解为子问题,使用递归函数

设 f(i，x)表示前i件物品，总重量不超过x的最优价值

则 f（i，x）=max(f(i－1，x-W[i])+C[i]，f（i－1，x））

f（n，m）即为最优解，边界条件为f（0，x）＝0 ，f(i,0)=0;

动态规划方法(顺推法)程序如下:

程序如下：

program knapsack02;

const maxm=200;maxn=30;

type ar=array[1..maxn] of integer;

var m,n,j,i:integer;

c,w:ar;

f:array[0..maxn,0..maxm] of integer;

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

begin

if x>y then max:=x else max:=y;

end;

begin

readln(m,n);

for i:= 1 to n do

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

for i:=1 to m do f(0,i):=0;

for i:=1 to n do f(i,0):=0;

for i:=1 to n do

for j:=1 to m do

begin

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];

end;

writeln(f[n,m]);

end.