Question

01背包输出物品种类

01背包要求输出物品种类,怎么实现啊?~~~~
注意要求输出物品种类~~~

Answer 1

先看完全背包问题

一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,

每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.

求旅行者能获得的最大总价值。

本问题的数学模型如下：

设 f(x)表示重量不超过x公斤的最大价值，

则 f(x）=max{f(x-i)+c[i]} 当x>=w[i] 1<=i<=n

可使用递归法解决问题程序如下:

program knapsack04;
const maxm=200;maxn=30;
type ar=array[0..maxn] of integer;
var m,n,j,i,t:integer;
c,w:ar;
function f(x:integer):integer;

var i,t,m:integer;

begin

if x=0 then f:=0 else

begin

t:=-1;

for i:=1 to n do

begin

if x>=w[i] then m:=f(x-i)+c[i];

if m>t then t:=m;

end;

f:=t;

end;

end;

begin
readln(m,n);
for i:= 1 to n do
readln(w[i],c[i]);
writeln(f(m));
end.

说明:当m不大时,编程很简单,但当m较大时,容易超时.

4.2 改进的递归法

改进的的递归法的思想还是以空间换时间,这只要将递归函数计算过程中的各个子函数的值保存起来,开辟一个

一维数组即可

程序如下:

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[i] then m:=f(i-w[i])+c[i];

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[i],c[i]);
fillchar(p,sizeof(p),-1);

writeln(f(m));
end.