UC知道采药 Pascal
来源：百度知道 编辑：UC知道 时间：2024/06/23 15:41:31
maxn=1000;
var
f:array[0..maxn,0..maxn] of longint;
c,w:array[1..maxn] of longint;
n,m:longint;
procedure dlx;
var
i,j,k:longint;
begin
for i:=1 to n do
for j:=1 to m do
if w[i]<=m
then begin
if w[i]>j then begin f[i,j]:=f[i-1,j]; continue; end;
f[i,j]:=f[i,j-w[i]]+c[i];
if f[i,j]<(f[i-1,j]) then f[i,j]:=f[i-1,j];
end;
end;
procedure main;
var
i,j,k:longint;
begin
read(m,n);
for i:=1 to n do
read(w[i],c[i]);
readln;
fillchar(f,sizeof(f),0);
dlx;
write(f[n,m]);
end;
begin
main;
end.
我是用动态做的，哪里错了？
我没仔细看你的程序,你的编程习惯是好的,但一个简单的程序没必要编这么多过程.教你一个简单的降维的01背包,10行写完
Begin
Readln(M,N);
Fillchar(F,Sizeof(F),0);
For I:=1 to N do
Begin
Readln(W,C);
For J:=M downto W do
If(F[J-W]+C>F[J])Then
F[J]:=F[J-W]+C;
End;
End.
解析如下:
01背包问题
题目
有N件物品和一个容量为V的背包。第i件物品的费用是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。
f[i][v]表示前i件物品恰放入一个容量为v的背包可以获得的最大价值。则其状态转移方程便是：
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
详细解释一下：“将前i件物品放入容量为v的背包中”这个子问题，若只考虑第i件物品的策略（放或不放），那么就可以转化为一个只牵扯前i-1件物品的问题。如果不放第i件物品，那么问题就转化为“前i-1件物品放入容量为v的背包中”，价值为f[i-1][v]；如果放第i件物品，那么问题就转化为“前i-1件物品放入剩下的容量为v-c[i]的背包中”，此时能获得的最大价值就是f[i-1][v-c[i]]再加上通过放入第i件物品获得的价值w[i]。
优化空间复杂度
以上方法的时间和空间复杂度均为O(N*V)，其中时间复杂度基本已经不能再优化了，但空间复杂度却可以优化到O(V)。
先考虑上面讲的基本思路如何实现，肯定是有一个主循环i=1..N，每次算出来二维数组f[i][0..V]的所有值。那么，如果只用一个数组f[0..V]，能不能保证第i次循环结束后f[v]中表示的就是我们定义的状态f[i][v]呢？f[i][v]是由f[i-1][v]和f[i-1][v-c[i]]两个子问题递推而来，能否保证在推f[i][v]时（也即在第i次主