定义子问题$P(i,W)$为：在前$i$个物品中挑选总重量不超过$w$的物品，每种物品至多只能挑选1个，使得总价值最大；这时的最优值记作$dp(i,W)$，其中$1<=i<=n$ , $1<=w<=c$

考虑第$i$件物品，无外乎两种可能：选，或者不选。

• 不选的话，背包的容量不变，改变为问题$P(i-1,W)$
• 选的话，背包的容量变小，改变为问题$P(i-1,W-w_i)$

最优方案就是比较这两种方案，哪个会更好些：

$dp(i,W)=max{dp(i-1,W),dp(i-1,W-w_i)+v_i}$

得到

$dp(i, W)=\left{\begin{array}{ll} 0 & \text { if } i=0 \ 0 & \text { if } W=0 \ dp(i-1, W) & \text { if } w_{i}>W \ \max \left{dp(i-1, W), v_{i}+dp\left(i-1, W-w_{i}\right)\right} & \text { otherwise } \end{array}\right.$

算法：

参考文献

0-1背包问题的动态规划算法 - Bat特白的文章 - 知乎

赏

谢谢你请我吃糖果

微信