背包问题

发表于 更新于 分类于 Valine： 本文字数： 2.5k 阅读时长 ≈ 2 分钟

常见的背包问题根据背包的重数和最终求的值可以分为下面6类：

1重 多重 无穷重
最大价值 0-1背包 多重背包 完全背包
方案数 0-1背包计数 多重背包计数 完全背包计数

0-1背包

以最普通的0-1背包来说，

问题描述：

有n种物品，每种1个，一个容量为C的背包，第i种物品的体积是w[i]，价值是v[i]，问背包能装下物品的最大价值。（也就是总体积不超过C的最大物品价值）

思路：

用dp[i][c]表示前i个物品在容量为c的背包时能装下的最大价值，每个物品都可以取或者不取，在面对第i个物品时，如果取那么

1
dp[i][c] = dp[i-1][c-w[i]]+v[i] if c>=w[i]

如果不取那么

1
dp[i][c] = dp[i-1][c]

并且dp[i][c]对于c应该是单调不减的，因为容量变大总价值不可能减少。

所以有

1
dp[i][c] >= dp[i][c-1]

综上，我们有

1
2
3
4
dp[i][c] = max(dp[i-1][c], dp[i][c-1]);
if(c>=w[i]) {
	dp[i][c] = max(dp[i][c], dp[i-1][c-w[i]]+v[i]);
}

有时候要求背包必须是满的，则没有上述单调性，或者我们总是不考虑单调性，而在给出最终答案前去遍历dp[n-1]得到最大值，鉴于此我们把上式简化，并加上循环

1
2
3
4
5
6
7
8
for(int i=0;i<n;i++) {
    for(int c=0;c<=C;c++) {
        dp[i][c] = dp[i-1][c];
        if(c>=w[i]) {
            dp[i][c] = max(dp[i][c], dp[i-1][c-w[i]]+v[i]);
        }
    }
}

注意到dp[i][c] = dp[i-1][c]相当于对于每个新的物品我们总是在前一物品算好的dp数组上做修改，那么能不能把第一维去掉直接修改呢，问题就在于dp[i-1][c-w[i]]我们会用到c-w[i]位置，而它可能在第i趟循环时修改了，如果我们再利用这个状态相当于物品i被用了两次，所以我们需要第i-1趟循环时的值，考虑到只会引用到c更小是位置，我们可以把内层循环反向，这样就不会在第i趟循环时修改到c-w[i]位置的值了。

1
2
3
4
5
for(int i=0;i<n;i++) {
    for(int c=C;c>=w[i];c--) {
        dp[c] = max(dp[c], dp[c-w[i]]+v[i]);
    }
}

循环完成后 max(dp)就是背包能取得的最大价值。

0-1背包算法时间复杂度O(n*C)，空间复杂度O(C)。

多重背包

问题描述：

有n种物品，每种m[i]个，一个容量为C的背包，第i种物品的体积是w[i]，价值是v[i]，问背包能装下物品的最大价值。

思路：

如果把m[i]个相同的物品视作m[i]种物品则问题可以规约为0-1背包，时间复杂度O(∑m[i]*C)，那么能不能利用m[i]个物品是相同的特性来优化时间复杂度呢？是可以的，对于第i种物品，我们不把它视作m[i]个相同的物品，而是把他们按二进制的方式组合，分成1个物品组合，2个物品组合，4个物品组合，……，这样m[i]个物品就被组合成了log(m[i])个物品，再规约为0-1背包，显然不影响最终解。算法时间复杂度O(∑log(m[i])*C)，组合成的新物品可以边循环边生成因此没有空间开销，空间复杂度还是O(C)。

完全背包

问题描述：

有n种物品，每种无穷个，一个容量为C的背包，第i种物品的体积是w[i]，价值是v[i]，问背包能装下物品的最大价值。

思路：

虽然每种物品个数是无穷的，但背包实际的容量的有限的，对于第i种物品最多装下C/v[i]个，我们可以令m[i]=C/v[i]即可把问题规约为多重背包问题。而实际上还有更简单的解法，我们在思考0-1背包空间降维时遇到的问题，“问题就在于dp[i-1][c-w[i]]我们会用到c-w[i]位置，而它可能在第i趟循环时修改了，如果我们再利用这个状态相当于物品i被用了两次”，而这对于完全背包问题来说正是我们需要的，因此只有把0-1背包内层循环的顺序改成正向的就实现了完全背包。

1
2
3
4
5
for(int i=0;i<n;i++) {
    for(int c=w[i];c<=C;c++) {
        dp[c] = max(dp[c], dp[c-w[i]]+v[i]);
    }
}

循环完成后 max(dp)就是背包能取得的最大价值。

完全背包的复杂度和0-1背包相同，算法时间复杂度O(n*C)，空间复杂度O(C)。

0-1背包计数

问题描述：

有n种物品，每种1个，一个容量为C的背包，第i种物品的体积是w[i]，问恰好装满背包的方案数。

思路：

对于计数问题通常会忽略价值，或者认为价值等于体积，用dp[i][c]表示前i个物品在容量为c的背包时恰好装满的方案数，则有

1
dp[i][c] = dp[i-1][c] + (dp[i-1][c-w[i]] if c>=w[i] else 0)

即要么不用第i个物品，要么用第i个物品。

同样我们可以用0-1背包类似的思想把空间降成1维，内层循环用倒序。

1
2
3
4
5
6
dp[0] = 1;
for(int i=0;i<n;i++) {
    for(int c=C;c>=w[i];c--) {
        dp[c] += dp[c-w[i]];
    }
}

多重背包计数

对于多重背包，要明确一点，相同种类的背包视为相同背包（例如5个第i种背包，取3个只会形成1种方案，而不是5C3种方案），那么还是可以按二进制的方式组合。

完全背包计数

问题描述：

有n种物品，每种无穷个，一个容量为C的背包，第i种物品的体积是w[i]，问恰好装满背包的方案数。

思路：

和完全背包类似思路，直接上代码：

1
2
3
4
5
6
dp[0] = 1;
for(int i=0;i<n;i++) {
	for(int c=w[i];c<=C;c++) {
		dp[c] += dp[c-w[i]];
	}
}