求所有背包问题源程序pascal+题目解析 0/1背包问题怎么做，关键是要写出解题思路和过程还有程序，能...

\u6c42\u5b8c\u5168\u80cc\u5305\u95ee\u9898\u5168\u90e8pascal\u7a0b\u5e8f\u53ca\u8fd0\u884c\u7ed3\u679c

var
i,j,v,n:longint;
f,c,w:array[0..100]of longint;
function max(a,b:longint):longint;
begin
if a>b then exit(a) else exit(b);
end;
begin
read(n,v);
fillchar(f,sizeof(f),0);
for i:=1 to n do
read(c[i],w[i]);
for i:=1 to n do
for j:=c[i] to v do
f[j]:=max(f[j],f[j-c[i]]+w[i]);
writeln(f[v]);
end.

\u770b\u770b\u8fd9\u4e2a~~
http://zhidao.baidu.com/question/107090954.html
\u80cc\u5305\u95ee\u9898\u4e00\u822c\u7528\u52a8\u6001\u89c4\u5212\u505a\uff0c\u641c\u7d22\u4e5f\u53ef\u4ee5~~~~~

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.

扩展阅读：扫一扫出答案免费网站 ... 答题神器一扫就出答案 ... 扫一扫题目出答案 ... 安全试题扫一扫出答案 ... 免费答题扫一扫 ... 0-1背包问题 ... 扫一扫一秒出答案 ... 24年保密观所有答案 ... 查答案扫一扫 ...