引言

本节通过多重背包问题，巩固上节内容的同时，进一步介绍动态规划中算法复杂度的分析，以及一些空间优化的技巧。

基本模型

现要把N种物品装进一个大小为M的背包，第i种物品有a[i]个可以使用，每一个大小为w[i]，价值为v[i]。那么这个背包能装下物品的最大价值是多少？

模型分析

01背包可以看做是多重背包的一个特例，当多重背包中每种物品都仅有一个时，就退化为了01背包。自然，我们也可以用类似的方法来考虑这个问题。

我们还是先考虑第n种物品，与之前01背包不同的是，现在我们有a[n]+1种决策：即不用第n种物品、用一个、用两个……一直到用a[n]个。如果我们选择使用k个，那么将获得v[n]*k的价值，背包剩余空间为m-k*w[n]。接下来我们要用前n-1种物品，填大小为m-k*w[n]的背包，尽量获得最大的价值。

所以我们依然用f(i,j)来表示用前i种物品，填大小为j的背包，所能获得的最大价值。

由上面的分析可以整理得下面的公式：

\(f(n,m) = \mathop {\max }\limits_{k = 0}^{a[n]} \{ \matrix{ {v[n]*k + f(n - 1,m - w[n]*k)} & {m \ge w[n]*k} \cr } \} \)

同理可以推广到任意的f(i,j)，此时的决策为第i件物品要使用多少个，读者可以尝试自己写出一般的状态转移方程。

\(f(i,j) = \mathop {\max }\limits_{k = 0}^{a[i]} \{ \matrix{ {v[i]*k + f(i - 1,j - w[i]*k)} & {j \ge w[i]*k} \cr } \} \)

边界条件依然是f(0,...)=0。

具体实现

for(j=0;j<=m;j++) f[0][j]=0;

for(i=1;i<=n;i++)

       for(j=0;j<=m;j++)

       {

              f[i][j]=f[i-1][j];      //不使用第i种物品

              for(k=1;k<=a[i];k++)           //用k枚举第i种物品使用的数量

              {

                     if(w[i]*k>j) break; //如果使用k个已经装不下了，也就不需要继续放更多的第i种物品了

                     tmp=v[i]*k+f[i-1][j-w[i]*k];

                     if(tmp>f[i][j]) f[i][j]=tmp;

              }

       }//f[n][m] is the answer

算法复杂度分析

关于时空复杂度的详细定义，由于篇幅有限，这里便不展开介绍了。如果感兴趣的话，可以翻阅《算法导论》或者在网上查找相关资料，想必可以得到满意的答案。这里仅仅简要的介绍如何分析动态规划的时空复杂度。

首先来分析时间复杂度，简而言之就是每一条语句总执行次数的规模。在本例中，我们用外层i、j两层循环，计算所有的状态，复杂度为O(n*m)。在算每一个状态时，都需要用内层k的循环，枚举每一种决策，选取一个最优值。每种物品大小最小是1，也就是说最多选取m个，所以这里的复杂度为O(m)。

状态的规模为O(n*m)，计算每一个状态的复杂度为O(m)，所以总的时间复杂度为两者的乘积\(O(n{m^2})\)。

接下来考虑空间复杂度，也就是占用的内存空间大小的规模，通俗的讲就是开了多大的数组。本例中用二维数组存储每一个状态，空间复杂度自然就是O(n*m)。

时间优化

在这里简单地为读者介绍一种时间优化的方法——转化为01背包。

直观地来看，第i种物品最多可以用a[i]个，那就把它们当做是a[i]个不同的物品做01背包就可以了。但这样直接拆分成a[i]个同样的物品，并不会带来时间上的优化。

稍做分析便可以知道，拆成a[i]的同样的物品，虽然答案同样是正确的，但却带来了大量的冗余。x件物品每一件取或不取，总共有2^x种可能性，但因为每件物品都一样，最终其实只表示了x+1种不同的情形，即不用、用1个…用x个。很自然地便可以想到，我们是否可以使用2进制的方式来进行拆分呢？

假如说某种物品有7个可用，我们便可以把其中的4个、2个、1个分别绑做一捆作为三个不同的物品，这样只用3个物品就可以表示出原来的8种情况。

当a[i]等于2^x-1的时候，按如上方式拆成1、2、...、2^(x-1)即可。但如果2^x-1

如果不用第x+1个物品，可以表示出0到2^x-1的所有情况；

如果使用最后一个物品，则可以表示y到2^x-1+y即y到a[i]的所有情况。

两者合在一起便能表示0到a[i]的所有可能。

简而言之，用1、2、4、...、2^(x-1)和y，就可以组合出0到a[i]之间的所有数字。

于是乎问题便转化为了一个更为简洁的01背包，此时背包中的物品个数为\(\sum\limits_{i = 1}^n {(\left\lfloor {{{\log }_2}a[i]} \right\rfloor + 1)} \)，背包大小仍然为M。

空间优化

在现在的ACM竞赛中，往往很少会用到空间优化的技巧，题目的空间限制往往非常宽容。但这并不意味着空间优化的手段就不重要。接下来将结合本例，介绍下空间优化的一般方法。

一个动态规划算法的核心就是状态转移方程，大多数的优化都是利用状态转移方程的特殊性质。我们先来观察一下本例中的方程：

\(f(i,j) = \mathop {\max }\limits_{k = 0}^{a[i]} \{ \matrix{ {v[i]*k + f(i - 1,j - w[i]*k)} & {j \ge w[i]*k} \cr } \} \)

不难发现，所有的f(i,...)只与f(i-1,...)有关。

我们动态规划求解所有状态的过程就像填表格一样，第i行就是f(i,...)。那么我们首先利用边界条件在第0行填满0，接下来用第0行的值算出第1行的值，以此类推，直到把前n行都填满。

因为第i行的值只与第i-1行的值有关，也就是说只有在填第i行时，第i-1行才是有用的。一旦第i行填好，开始算第i+1行，那么第i-1行再无任何用处（至少对于本例的问题是没有用了）。既然这样，我们何必还把它们存储在内存中浪费空间内。

首先介绍一种滚动数组的技术。

既然每一次计算，都只与两行状态有关，那么我们就只使用两个O(m)的数组即可，不妨记作第0行和第1行。首先把f(0,...)，填入第0行；然后将算出的f(1,...)放入第1行；接下来用第1行的f(1,...)计算f(2,...)，把结果再次存入第0行；之后再把f(3,...)存入第1行……

这样，只是用两个O(m)的数组，就完成了所有状态的计算，成功的将空间复杂度降至O(m)。

在本例中，如果你对使用两个O(m)的数组还感到不满意，只使用一个数组也是可以的。我们继续观察状态转移方程，之前我们利用行间的依赖关系做出了滚动数组的优化，那么我们再考虑一下行内有没有什么可以利用的性质。不难发现，f(i,j)实际上只依赖于f(i-1,k) (k=0,1...j)。从反向来考虑，也就是说f(i-1,k)只用来求f(i,j) (j=k,k+1...m)。f(i,m)算出后，f(i-1,m)就没有用了；f(i,m)和f(i,m-1)算完后，f(i-1,m-1)也没有用了……

所以我们不妨从大到小的求解每一行的状态。现在我们只有一个O(m)的数组，f(i-1,...)已经填在了里面，现在我们要计算f(i,...)。首先计算f(i,m)，我们先用一个临时变量beta存储f(i,m)的值，当beta算好后，f(i-1,m)就没有用了，于是我们就可以直接把beta填入数组的第m位，也就是原来f(i-1,m)的位置。同理依次在f(i,j)算好后，直接填入数组的第j位，替换掉原先的f(i-1,j)即可。

简而言之，空间优化的原理就是尽量少地存储无用的状态。一个状态一旦失去作用（不再被其他状态依赖），就可以用新的状态将其覆盖，以此来节省空间。至于一个状态什么时候会失去作用，就需要反复观察状态转移方程，思考其中的依赖关系了。

written by PCZ