01背包输出物品种类

先看完全背包问题

一个旅行者有一个最多能用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 改进的递归法