今天大年初一，这是背包问题的最后一个知识点更新，窗外鞭炮震天，而我却...

引言

本节将通过多维背包问题，巩固一下前几节的内容。

基本模型

现要把N个物品装进一个大小为M、最多承重S的背包，第i个物品大小为w[i]，重量为g[i]，价值为v[i]。那么这个背包可以装载物品的最大价值是多少？

模型分析

多维背包问题的特点在于，除了大小上的限制，又多出了一个重量上的限制。当然这种限制叫什么名字都是无所谓的，再多出几种限制也同样是多维背包问题。这里仅以两种限制为例，介绍多维背包。

我们仍然可以从初始状态来考虑。现在要用n个物品，填充大小为m，承重为s的背包，欲获得最大的价值。首先还是考察第n个物品用不用。

如果用第n个物品，获得价值v[n]。接下来要用前n-1个物品填充大小为m-w[i]，可承重s-g[i]的背包，同样是获得最大的价值。

如果不使用，那么就要用前n-1个物品来填充大小为m，可承重s的背包，获得最大的价值。

所以我们不妨设定状态f(i,j,k)，来表示用前i种物品，填充大小为j、可承重k的背包，所能获得的最大价值。f(n,m,s)就是最终的答案。

这次我们就不再整理f(n,m,s)的公式，而是直接推广到任意的f(i,j,k)，写出状态转移方程：

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

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

下面来分析一下时空复杂度。时间上，状态的规模为O(n*m*s)，决策只有两种，转移的复杂度为O(1)，所以整体时间复杂度为$O(nms)$。空间上，开了一个三维数组来存储所有的状态，复杂度为$O(nms)$。

虽然多维背包中，限制条件不止一个，但整体的方法和普通的背包问题基本是一样的。那么，我们能否通过前几节中的方法，来进行空间优化呢？答案是肯定的。

具体的优化方法留给读者思考，这里就不再赘述了。最终可以将空间复杂度优化至$O(ms)$。

核心代码

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

for(i=1;i<=n;i++)
       for(j=0;j<=m;j++)
              for(k=0;k<=s;k++)
              {
                     f[i][j][k]=f[i-1][j][k];
                     if(j>=w[i] && k>=g[i])
                     {
                            tmp=v[i]+f[i-1][j-w[i]][k-g[i]];
                            if(tmp>f[i][j][k]) f[i][j][k]=tmp;
                     }
              }//f[n][m][s] is the answer

written by PCZ