定义子问题$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.$
算法：
参考文献
