Question

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

看来网上许多关于背包问题的状态转移方程。但我是初学者不是太理解。但总感觉自己的又有那些地方有问题。我的状态转移方程是max｛dp(i+1,j),dp(i,j-w[i])+v[i]｝,描述：对于第i个物品，有两种选择，选和不选。不选就i+1，总的容量不变。选就i，总的减去当前第i物品的容量并且加上他的价值。请问大s，我这个状态转移方程有问题么？对了，这个我是用递归方式。

Answer 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)}