编程实现0－1背包问题的求解
- 提问者网友：沉默的哀伤
- 2021-04-23 01:46
- 五星知识达人网友：第四晚心情
- 2021-04-23 02:03
可惜我是学PASCAL的pascal的代码是：
var m,n,j,i:integer;
c,w:array[1..200] of integer;
f:array[0..200,0..30] of integer;
function q(x,y:integer):integer;
begin
if x>y then q:=x else q:=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]:=q(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.
不会C++
你加油吧
思路是：设f(i,x)表示前i件物品，总重量不超过x的最优价值，则f(i,x)=max(f(i-1,x-w[i])+c[i],f(i-1,x)){第i件物品放进去与不放进去的更优方案}，f(n,m)即为最优解。
- 1楼网友：春色三分
- 2021-04-23 02:23
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.
我也只会pascal
背包问题 背包问题有三种
1.部分背包问题
一个旅行者有一个最多能用m公斤的背包，现在有n种物品，它们的总重量分别是W1，W2，...,Wn,它们的总价值分别为C1,C2,...,Cn.求旅行者能获得最大总价值。
解决问题的方法是贪心算法:将C1/W1,C2/W2,...Cn/Wn,从大到小排序,不停地选择价值与重量比最大的放人背包直到放满为止.
2.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.
使用二维数组存储各子问题时方便，但当maxm较大时如maxn=2000时不能定义二维数组f,怎么办,其实可以用一维数组,但是上述中j:=1 to m 要改为j:=m downto 1,为什么?请大家自己解决。
3.完全背包问题
一个旅行者有一个最多能用m公斤的背包，现在有n种物品，每件的重量分别是W1，W2，...,Wn,
每件的价值分别为C1,C2,...,Cn.若的每种物品的件数足够多.
求旅行者能获得的最大总价值。
本问题的数学模型如下：
设 f(x)表示重量不超过x公斤的最大价值，
则 f(x）=max{f(x-w[i])+c[i]} 当x>=w[i] 1<=i<=n
程序如下:（顺推法）
program knapsack04; const maxm=2000;maxn=30; type ar=array[0..maxn] of integer; var m,n,j,i,t:integer; c,w:ar; f:array[0..maxm] of integer; begin readln(m,n); for i:= 1 to n do readln(w[i],c[i]); f(0):=0; for i:=1 to m do for j:=1 to n do begin if i>=w[j] then t:=f[i-w[j]]+c[j]; if t>f[i] then f[i]:=t end; writeln(f[m]); end.