UC知道pascal01背包问题
来源：百度知道 编辑：UC知道 时间：2024/06/04 07:20:04
用一维数组解
program _01backpack_2;
var m,n,i,x:longint;
f,w,c:array[0..99999]of longint;
begin
readln(m,n);
for i:=1 to n do
readln(w[i],c[i]);
for i:=1 to n do
for x:=m downto w[i] do
if f[x-w[i]]+c[i]>f[x] then f[x]:=f[x-w[i]]+c[i];
writeln(f[m]);
end.
为什么要用downto ?
program _01backpack_2;
var m,n,i,x:longint;
f,w,c:array[0..99999]of longint;
begin
readln(m,n);
for i:=1 to n do
readln(w[i],c[i]);
for i:=1 to n do
for x:=m downto w[i] do
if f[x-w[i]]+c[i]>f[x] then f[x]:=f[x-w[i]]+c[i];
writeln(f[m]);
end.
为什么要用downto ?
如果用to，可能前面的一个状态f[x-w[i]]已经用过第i个包了，而当f[x-w[i]]转移到f[x]时仍然用第i个包，这样就会导致重复使用。
而用downto可以避免这个问题。
如果不理解，可以把downto的语句换成to的语句，自己单步执行一下程序，跟踪一下变量，就知道了。