完全背包、多重背包

对于背包问题的初步认识，可以参考我的另一篇文章
算法学习（三）——01背包

题目类型

有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 个物品的价值和体积分别是 $value[i]$ 和 $weight[i]$ 。每个物品能无限制的使用任意个。求解将哪些物品放进包里可以使价值最大。

题目类型

大体和01背包类似，唯一不同的地方是每种物品有无限个。此时每种物品的策略已经不再是要或者不要了，而变成了要0个，要1个，要2个……

状态表达式和状态转移方程

状态表达式方面和01背包是一样的，依旧用 $tab[i][j]$ 去表示前 $i$ 个物品恰好放入一个容量为 $j$ 的背包的最大价值。我们就可以很容易的按照原本的思路，写出状态转移方程：
tab[i][j] = max{ tab[i-1][j-k*weight[i]]+k*value[i] | 0<=k*c[i]<=v}

状态转移方程理解

看到上面的状态转移方程和往常一样，懵了，不过有了01背包的基础，我还是可以冷静下来分析分析这个状态转移方程的：

注意状态转移方程最后有一个 $0 <= k * weight[i]<= v$ ，即物品重量要在背包重量范围内，当然，这是肯定的。
其实这个状态转移方程就是在01背包的基础上增加了一个变量 $k$ ，在写代码的时候加上 $k$ 其实就好了。
查了很多很多的教程，都没有对于完全背包的状态转移方程的详解，都是自己一点一点琢磨出来的。不过查教程的时候发现这个状态转移方程虽然是核心，但是使用的时候好像都是它的变形。

复杂度分析

时间复杂度： $O(NV\sum_ {}\frac{V}{C _i}) $
空间复杂度： $O(NV)$

优化：转换成01背包问题

01背包是所有背包的基础，所以任何背包问题最后都可以转化为01背包，下面来看看具体是怎么转化的吧。

最通俗易懂的转化

首先想想01背包是怎么样的：有N个物品，每个物品都可以选择装或不装。
然后现在吧完全背包理解为：每个物品有 $\frac{V_{sum}}{V_i}$ 个（这里的 $V_{sum}$ 是背包总重量，$V_{i}$ 是这个物品的重量）。
通过上面的转化，其实就可以把完全背包的问题转化为有有限多个物品的01背包的问题了，然后使用01背包的解决办法就可以解决完全被背包的问题了。
不过，这种转化虽然通俗易懂，但是时间复杂度和上面的方法是一模一样的，因此，我们还需要寻找一种更加合适的转化方法。

二进制拆分

这里没有怎么看懂，不过还是照搬照抄的把大致思想写出来把。

首先，把第 $i$ 件物品拆分成价值为 $values[i]×2^k$ ，质量为 $weight[i]x2^k$ 的若干件物品，其中 $k$ 满足 $weight[i]x2^k<=V$ 。这是二进制的思想，因为不管最优策略选几件第 $i$ 种物品，总可以表示成若干个 $2^k$ 件物品的和。这样把每种物品拆成 $log(\frac{V}{C_i})$ 件物品，是一个很大的改进。

$O(VN)$ 的算法

算了，看懂了说不出来，还是直接摘抄吧：

这个算法使用一维数组，先看伪代码：

java

for (int i = 0; i <= V; i++) dp[i] = 0;
for (int i = 1; i <= n; i++) {
    for (int j = C[i]; j <= V; j++) {
        dp[j] = max(dp[j], dp[j-C[i]]+W[i]);
    }
}

可以看到，这段代码和01背包的空间优化版本是不是特别像？对的。首先要考虑在01背包中第二层循环是 $V→Ci$ 的原因，因为每件物品都只有一个，当前的选择不能被前面的选择所影响，如果是按照 $Ci→V$ 的顺序的话，当计算到一个值的时候，前面所用到的 $j−C[i]$ 的这个值可能是已经选择了当前物品的情况，所以用来先计算体积大的部分（因为无后效性）。
而在这个问题中，显然是应该被前面计算的值所影响的，因为每件物品有无限个。这个应该很容易理解到。

这个教程其实讲的已经很通俗易懂了，静下心来仔细阅读就可以，实在不行画个流程图就OK了。

多重背包

题目模型

有 $N$ 件物品和一个容量为 $V$ 的背包。第 $i$ 个物品的体积和价值分别是 $Ci$ 和 $Wi$ 。每个物品最多只有 $Mi$ 个物品可用。求解将哪些物品放进包里可以使价值最大。

题目特点

和完全背包很相似，唯一不同的地方就是每个物品的最大个数不再是 $\frac{V}{C_i}$ ，而变成了 $min(\frac{V}{C_i},M_i)$ 。其他的部分都和完全背包是一样的。

关于多重背包的问题，大家可以浏览这个网站第三讲多重背包问题

参考

基础动态规划
 第二讲完全背包问题