[背包问题] 01背包
-
前言
背包问题是一类
动态规划
问题,满足动态规划
的主要特征:- 具有最有子结构的性质。问题的最优解所包含的子问题的解也是最优的
- 无后效性。子问题的解一旦确定,就不再改变,不受之后的决策影响
- 子问题重叠性。同一个子问题可能被计算多次,我们的做法通常是将子问题的解保存下来,以免重复计算
而背包问题也分不同的类别,称为
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
扩展:在上题的基础上进一步输出具体方案