[背包问题] 01背包

tangbin

前言

背包问题是一类 动态规划 问题，满足 动态规划 的主要特征：

具有最有子结构的性质。问题的最优解所包含的子问题的解也是最优的
无后效性。子问题的解一旦确定，就不再改变，不受之后的决策影响
子问题重叠性。同一个子问题可能被计算多次，我们的做法通常是将子问题的解保存下来，以免重复计算

而背包问题也分不同的类别，称为 01背包、完全背包、多重背包、混合背包 以及变种问题。我将介绍前4中问题的解法，并给出示例供大家参考。

01背包经典问题

有N件物品和一个容量为V的背包。第 i 件物品的体积是 c[i]，价值是 v[i]。求解将哪些物品装入背包可使价值总和最大。

思路

每种物品只有1件，所以只有装或不装2种状态，故称01背包。

定义状态 dp[ i ][ j ] 表示在前 i 件物品中选择，装体积为 j 的背包得到的最大价值。

考虑第 i 件物品，

装。得到的最大价值为 dp[ i - 1 ][ j - c[i] ] + v[ i ] , 即空出 c[ i ] 的体积装第 i 件物品，增加价值 v[ i ]，剩下的体积装入前 i - 1 件物品
不装。得到的最大价值为 dp[ i - 1 ][ j ] , 即用前 i - 1 件物品装体积为 j 的背包

由此得到状态转移方程: dp[ i ][ j ] = max { dp[ i - 1 ][ j - c[i] ] + v[ i ] , dp[ i - 1 ][ j ] }

伪代码

使用二维数组，可以轻松地写出以下逻辑

for i = 1 ... N
    for j = 0 ... V
        if j < c[i]:    // 装不下第 i 件物品
            dp[i][j] = dp[i-1][j]
        else:           // 装得下第 i 件物品
            dp[i][j] = max(dp[i-1][j], dp[i-1][j-c[i]] + v[i])

这种情况下，空间复杂度和时间复杂度都是 o( N * V ) ，不过我们可以通过降维来减少空间复杂度。

空间优化

考虑数组的第一维，我们只用到了 i 和 i - 1，所以一个简单的降维方法就是声明数组时，第一维的大小声明为2，即dp[ 2 ][ V ], 然后交替使用 dp[ 0 ][ j ] 和 dp[ 1 ][ j ]，将这种数组称为滚动数组。这样空间复杂度就降到了o( V )
还有一个更巧妙的方法，使用一位数组 f[ j ] 代替 dp[ i ][ j ]，先看代码
```
for i = 1 ... N
    for j = V ... c[i]
        f[j] = max(f[j], f[j-c[i]] + v[i])
```
观察这份代码与上面的代码，除开 dp 数组去掉第一维变成了 f 数组，有2个主要的区别
- j 倒序枚举
  
  因为 f 数组中最优解 f [ j ] 的得到会依赖于 f [ j - c[i] ] ，倒序保证了上一次的状态（即 i - 1 时得到的最优解）还未被覆盖，这样才能在节省空间的情况下得到正确的解
- 少了判断语句
  
  由于 j < c[ i ] 时状态转移方程为dp[ i ][ j ] = dp[ i - 1 ][ j ] ，等效到 f 数组就是 f [ j ] = f [ j ]，于是可以省略判断，将 j 的下限改为 c[ i ]

例题

模板题：POJ 3624

扩展：在上题的基础上进一步输出具体方案