/ Vijos / 讨论 / 问答 /

完全背包问题

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

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

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

2 条评论

  • @ 2009-03-24 16:33:53

    给你答案啦

    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.

  • @ 2009-03-24 16:32:55

    给你答案啦

    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.

  • 1