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

2024-11-22 23:52:18

推荐回答（1个）

回答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)}