面试官：完全背包都不会，是你自己走还是我送你？

面试官：完全背包都不会，是你自己走还是我送你？

在如今的面试当中算法题已经成为面试不可或缺的内容，今天就跟大家分享一个还比较困难的笔试题——完全背包。

完全背包问题

有$N$种物品和一个容量是 $V$的背包，每种物品都有无限件可用。第$i$ 种物品的体积是 $v_i$，价值是$w_i$。求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

完全背包问题和01背包的唯一区别就在于物品的个数，在01背包当中所有的物品只有一件，也就只能使用一次。而在完全背包当中物品可以使用无限多次。

比如下面的4个物品，背包能够承受的最大重量为5，我们应该如何选择，使得我们获得的总价值最大：

这个问题还是比较简单，我们直接从图中看，我们可以选择五个A或者两个B一个A，可以产生最大的收益，最大收益为10。

完全背包问题分析

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]，因此我们的收益为dp[i - 1][j - v[i]] + w[i], dp[i - 1][j])。