[数据结构与算法]细说背包问题 - 完全背包

分类

背包模型的本质，就是从 n 种物品中选择若干，放入容量为 m 的背包。按照每种物品的数量，背包问题可以分成以下三种基本类型：

• 01背包：每种物品只有 1 件，可以选择 0 件，可以选择 1 件
• 完全背包：每种物品数量无限，可以选择 0 件，可以选择 1 件，可以选择 2 件…只要已选物品的总重量不超过背包容量
• 多重背包：每种物品数量有限，可以选择 0 件，可以选择 1 件，可以选择 2 件…只要不超过该种物品的数量，且已选物品的总重量不超过背包容量

完全背包

解题

• 约定用f[i][j]表示从前 i 种物品中选择若干，放入容量为 j 的背包所能够获得的最大总价值，分别用 w 和 v 表示第 i 种物品的重量和价值

1. 若选择 0 件第 i 种物品，等价于先从前 i - 1 种物品中选择若干，放入容量为 j 的背包，获得的最大总价值为f[i - 1][j]
2. 若选择 1 件第 i 种物品，等价于先从前 i - 1 种物品中选择若干，放入容量为 j - w 的背包，获得的最大总价值为f[i - 1][j - w] + v
3. 若选择 2 件第 i 种物品，等价于先从前 i - 1 种物品中选择若干，放入容量为 j - 2 * w 的背包，获得的最大总价值为f[i - 1][j - 2 * w] + 2 * v
4. 。。。。。。
5. 若选择 3 件第 i 种物品，等价于先从前 i - 1 种物品中选择若干，放入容量为 j - 3 * w 的背包，获得的最大总价值为f[i - 1][j - 3 * w] + 3 * v
6. 用变量来表示，若选择 k 件第 i 种物品，等价于先从前 i - 1 种物品中选择若干，放入容量为 j - k * w 的背包，获得的最大总价值为f[i - 1][j - k * w] + k * v，k的值满足0 <= k <= j / w

• 我们通过打擂台，找到从前 i 种物品中选择若干，放入容量为 j 的背包所能够获得的最大总价值
• 题目要求的，从前 n 种物品中选择若干，放入容量为 m 的背包，能够获得的最大总价值，即f[n][m]

代码如下：

#include <bits/stdc++.h>
using namespace std;

int m, n;
int f[39][209];

int main() {
	cin >> m >> n;
	
	for (int i = 1; i <= n; i ++) {
		int w, v;
		cin >> w >> v;
		for (int j = 1; j <= m; j ++) {
			for (int k = 0; k <= j / w; k ++) {
				f[i][j] = max(f[i][j], f[i - 1][j - k * w] + k * v);
			}
		}
	}	
	cout << "max=" << f[n][m];

	return 0;
}

优化时间复杂度

这个代码无论时间复杂度还是空间复杂度，都不是最优的。我们进一步观察状态转移方程。

• 如果背包容量j >= w，我们考虑以下两种情况：

1. 从前 i 种物品中选择若干，放入容量为 j 的背包，从下表左侧这一列中找出的最大值就是f[i][j]
2. 从前 i 种物品中选择若干，放入容量为 j - w 的背包，从下表右侧这一列中找出的最大值就是f[i][j - w]

• 对比这两列，我们得出 f[i][j] = max(f[i - 1][j], f[i][j - w] + v
• 这个新的状态转移方程中不再出现变量 k，也就是说，我们可以用嵌套循环取代三重循环！
• 如果背包容量j < w，则f[i][j] = f[i - 1][j]

代码如下：

#include <bits/stdc++.h>
using namespace std;

int m, n;
int f[39][209];

int main() {
	cin >> m >> n;
	
	for (int i = 1; i <= n; i ++) {
		int w, v;
		cin >> w >> v;
		for (int j = 1; j <= m; j ++) {
			if (j < w) f[i][j] = f[i - 1][j];
			else f[i][j] = max(f[i - 1][j], f[i][j - w] + v);
		}
	}	
	cout << "max=" << f[n][m];

	return 0;
}

优化空间复杂度

• 上面的代码使用二维数组，f[i][j]表示从前 i 种物品中选择若干，放入容量为 j 的背包能够获得的最大总价值。
• 和处理01背包的方法一样，我们可以将二维数组 f 压缩成一维数组
• f[i][j] = max(f[i - 1][j], f[i][j - w] + v)变成f[j] = max(f[j]，f[j - w] + v
• f[i][j] = f[i - 1][j]变成f[j] = f[j]，这条语句可以省略
• 这样一来，完全背包和01背包的状态转移方程变得一模一样。整个代码的区别在于，01背包的第二重循环，是从大到小枚举背包容量，而完全背包的第二重循环，是从小到大枚举背包容量。
• 我们从这个角度来理解，假设有一个容量为 j 的背包，它装载物品的最大价值是f[j]。如果增加一件重量为 w 的物品后不会超过容量 m，则容量为 j + w的背包的最大价值f[j + w] = f[j] + v；如果再增加一件重量为 w 的物品不会超过容量 m，则容量为 j + 2 * w 的背包的最大价值f[j + 2 * w] = f[j + w] + v，…。当我们从小到大枚举背包容量的时候，恰好对应多次选择同一种物品。
  f[j + w] = f[j] + v，选择 1 次
  f[j + 2 * w] = f[j + w] + v，选择 2 次
  f[j + 3 * w] = f[j + 2 * w] + v，选择 3 次
  f[j + 4 * w] = f[j + 3 * w] + v，选择 4 次
  。。。。。。

代码如下

#include <bits/stdc++.h>
using namespace std;

int m, n;
int f[209];

int main() {
	cin >> m >> n;
	
	for (int i = 1; i <= n; i ++) {
		int w, v;
		cin >> w >> v;
		for (int j = w; j <= m; j ++) {
			f[j] = max(f[j], f[j - w] + v);
		}
	}	
	cout << "max=" << f[m];

	return 0;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖