深入剖析多重背包问题（上篇）
前言
在前面的两篇文章当中，我们已经仔细的讨论了01背包问题和完全背包问题，在本篇文章当中将给大家介绍另外一种背包问题——多重背包问题，多重背包问题的物品数量介于01背包问题和完全背包问题之间，他的物品的数量是有限个！
多重背包问题介绍
有 $N$ 种物品和一个容量是 $V$ 的背包。第 $i$ 种物品最多有 $s_i$ 件，每件体积是 $v_i$，价值是 $w_i$。求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
注意：上面使用到的字符含义在本篇文章当中都一样。
多重背包问题跟01背包和完全背包的区别都是在物品的可用次数上，01背包只能使用一次，多重背包可用使用无数次，而多重背包可用使用多次。
背包问题复习——01背包的动态转移方程
01背包的动态转移方程
01背包问题当中，我们是使用一个二维数组dp[i][j]进行计算，dp[i][j]表示在只使用前i个物品且背包容量为j的情况下，我们能够获得的最大的收益。在这个情况下，我们根据当前背包容量j判断是否能装入第i个物品可以得到下面两个方程：
$$ dp[i][j] = \begin{cases} max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j]), j \ge v[i]\\ dp[i - 1][j] , j \lt v[i] \end{cases} $$
上面01背包的公式的第二条比较简单，如果背包容量不足以容纳第i件物品，那么只能从前i - 1物品当中选择了。我们来仔细分析一下第一条公式。
如果当前背包容量可以容纳第i个物品，那么我们就可以选择第i件物品或者不选择，我们应该选择两种选择当中收益更大的那个。
- 如果我们不选择第
i个物品，那么我们就能够使用容量为j的背包去选择前i - 1个物品，这种情况下我们的最大收益为dp[i - 1][j]。 - 如果选择第
i个物品，那么我们背包容量还剩下j - v[i]，还可以选择剩下的i - 1个物品，而且我们的收益需要加上w[i]，因此我们的收益为max(dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])。