背包问题小结

发表于 | 分类于 | |

今天在刷到LeetCode 039. Combination Sum这道题时，一看就是完全背包的问题，所以就趁机参考《挑战程序设计竞赛》把背包问题进行一个小结。

01背包

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

之所以称这类问题为01背包问题，就在于每件物体只有两种状态，

  • 放
  • 不放

所以理论上只要枚举所有可能性就能得出最后答案，但是复杂度高达：2^n次方，这样显然是不行的。

所以，只能寻求复杂更低的做法。仔细观察，这类问题其实包含主重叠的子问题

你判断第N个物体的抉择时的和你前面N-1个物体是怎么选的有很大的关系。所以就可以用动态规划的思想来解决。

而用动态规划，最主要就是想清楚两件事情：

  • 状态的定义
  • 状态的转移

转移的转移不难想，肯定是根据第i个物体选或不选来规定转移方程的。

但是在状态的定义上，有时会因人而异。

我个人比较喜欢如下定义。

1
dp[i][j] = 从前i个物品中选出不超过j的价值之和

这样定义后状态转移方程便成了

1
dp[i][j] = max{dp[i-1][j]/*不选*/, dp[i-1][j-c[i]]+w[i] /*选*/}

代码实现：

1
2
3
4
5
6
void solve()
{
  for(int i = 0 ; i < N; i++)
    for(int j = 0 ; j < V; j++)
      dp[i][j] = max(dp[i-1][j],dp[i-1][j-c[i]]+w[i])
}

其实就是一个填表的过程：每一行的某个数都是由上一行根据一定的规则推算出来的。

在崔天翼的《背包九讲》中，还进一步压缩了空间复杂度。因为dp(i)(j)中的j要么由上一行的j推出，要么由上一行的j-c[i]推出。所以只需要保证，j遍历的时候小的部分保留着上次计算的结果就行，那么就只需把j倒序便ok了。

1
2
3
for(int i = 0 ; i < N ; i++)
  for(int j = V, j > 0 ; j--)
    dp[j] = max(dp[j],dp[j-c[i]]+w[i])

完全背包

完全背包与01背包相比，区别就是每件物体选的个数不设上限，可以取无限次。刚开始以为还以为有多难，其实空间压缩到一维后，与01背包的代码异常类似：

1
2
3
for(int i = 0 ; i < N ; i++)
  for(int j = 0, j < V ; j++)
    dp[j] = max(dp[j],dp[j-c[i]]+w[i])

是这么理解的：

你会发现，这个伪代码与P01的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢？首先想想为什么P01中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[i][v]是由状态f[i-1][v-c[i]]递推而来。换句话说，这正是为了保证每件物品只选一次，保证在考虑“选入第i件物品”这件策略时，依据的是一个绝无已经选入第i件物品的子结果f[i-1][v-c[i]]。而现在完全背包的特点恰是每种物品可选无限件，所以在考虑“加选一件第i种物品”这种策略时，却正需要一个可能已选入第i种物品的子结果f[i][v-c[i]]，所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。

崔真的是天才，从二维压缩到了一维，而且能够使到01背包和完全背包在解题形式上如此高度统一。

Reference：

  1. http://love-oriented.com/pack/ （背包问题九讲）
  2. 《挑战程序设计竞赛》（第二版）