01背包问题，程序求解

一、01背包问题，程序求解

把这一句：int f[maxn],t[maxn],v[maxn];

放到main()的前面去，或者定义后就立即赋值为0。

因为局部变量初始化的值是不确定的，但保证全局变量都被初始化为0。

还有你最后：cout<

二、pascal背包问题

01背包：

fillchar(f,sizeof(f),0);{f数组初始化为0}

read(数量，总钱数);

for i:=1 to 数量 do begin

read(价钱，价值);

for j:=总钱数 DOWNTO 价钱 do

if f[j]end; 无限背包： 把01背包里面的“总钱数 DOWNTO 价钱”改成“价钱 TO 总钱数”.我也在找这个玩艺。分享一下

三、C语言，算法，动态规划。对于0-1背包问题，我有个小疑问。

dp(i,j)表示前i件物品选择任意件后放进最大容量为j的背包的最大价值。

显然，dp(0,j)=0，dp(i,0)=0。

对于第i件物品，有两种情况：

一、不放进背包，则最大价值为前i-1件物品可以放进容量为j的背包的最大价值，即dp(i,j)=dp(i-1,j)

二、放进背包，则最大价值为第i件物品价值加上前i-1件物品卡伊放进容量为j-w[i]的背包的最大价值，即dp(i,j)=v[i]+dp(i-1,j-w[i)

综合两种情况 dp(i,j)=max{dp(i-1,j), v[i]+dp(i-1,j-w[i)}