引言

本节将结合完全背包问题，介绍动态规划中基础的的优化方法。

基本模型

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

模型分析

完全背包与多重背包不同之处在于每种物品有任意多个，而多重背包每种物品有数量限制。当然，我们可以完全按照多重背包的方法来做。每次做决策时，虽然没有了a[i]的数量限制，但因为背包大小有限，使用第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 } \}$

而完全背包的状态转移方程，只要把a[i]的限制换成+∞即可。因为要满足$j \ge w[i]*k$，所以k严格意义上的上界是$\left\lfloor {{j \over {w[i]}}} \right\rfloor$。

所有可以得到完全背包的状态转移方程：

$f(i,j) = \mathop {\max }\limits_{k = 0}^{\left\lfloor {{j \over {w[i]}}} \right\rfloor } \{ v[i]*k + f(i - 1,j - w[i]*k)\}$

这个算法的时间复杂度仍然是$O(n{m^2})$，因为决策不再受a[i]限制，所以该算法的计算次数一定不会比多重背包少。但是完全背包问题与多重背包相比少了很多的限制条件，问题更加一般化，直观上的感受性质也会更好一些。然而使用原先的方法，却只能算的更慢（虽然复杂度并没有变化），所以很可能存在着更快的算法等着我们来发现。

优化方法

动态规划的复杂度主要是两个方面，一个是状态的规模，一个是转移时枚举决策的复杂度。作为基础动态规划篇的前几节，这里就不深入介绍，如何确定该使用哪一种优化技巧，而是直接把这种优化方法当做一个典例介绍给大家。

在多重背包问题中，我们尝试对转移环节进行优化。原算法的复杂度$O(n{m^2})$中的最后一个m，就是源于决策最坏情况下会达到O(m)级别。我们原来的分析方法是，用前i种物品去填充大小为j的背包，枚举第i种物品使用了多少个。然而我们可以换一种想法，决策变为是否填一个第i种物品。

如果填一个第i种物品，那么获得价值v[i]，背包剩余空间j-w[i]。因为每种物品都有无限个，所以接下来仍然可以随便使用第i种物品。于是接下来的问题就变为用前i种物品，填充大小为j-w[i]的背包，最大价值是多少。仍然是用前i种物品，只不过背包大小有所减少。

$\matrix{ {f(i,j) = v[i] + f(i,j - w[i])} & {j \ge w[i]} \cr }$

如果第i种物品不用了，接下来就要用前i-1种物品填充大小为j的背包了。

$f(i,j) = f(i - 1,j)$

综合以上两种情况，就可以得到新的状态转移方程：

$f(i,j) = \max \left\{ {\matrix{ {v[i] + f(i,j - w[i])} & {j \ge w[i]} \cr {f(i - 1,j)} & {} \cr } } \right.$

状态的规模仍然为O(n*m)，不过现在的决策只有两种，转移的复杂度为O(1)，所以整体的时间复杂度为$O(nm)$。

为什么这一算法会比原算法快呢？关键就在于这个f(i,j-w[i])，原先此处还要继续比较用2,3,4...件第i种物品的最大价值，而现在只用一个f(i,j-w[i])就解决了所有问题。事实上是因为所有这些情况在f(i,j-w[i])中已经被计算过了。

在原先的算法中，计算f(i,j)、f(i,j-w[i])、f(i,j-2*w[i])...时，都只是利用f(i-1,...)来计算，但是其中包含了大量重复性的比较。而现在直接用f(i,j-w[i])来计算f(i,j)，就省去了这些重复性的工作，提高了算法的整体效率。

在理解了该算法的基础上，读者不妨思考一下，为什么不能对多重背包问题也使用这种优化方法？

具体实现

现在每一个状态f(i,j)不仅依赖于f(i-1,j)，还依赖于f(i,j-w[i])。所以我们不妨在两个维度都按照从小到大的顺序来求解。

核心代码

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];
              if(j>=w[i])
              {
                     tmp=v[i]+f[i][j-w[i]];
                     if(tmp>f[i][j]) f[i][j]=tmp;
              }
       }//f[n][m] is the answer

该算法实现和01背包的实现其实只有一处不同，你发现了么？

written by PCZ