（待更）背包九讲复习

背包九讲

1. 01背包问题
2. 完全背包问题
3. 多重背包问题
4. 混合背包问题
5. 二维费用的背包问题
6. 分组背包问题
7. 背包问题求方案数
8. 求背包问题的方案
9. 有依赖的背包问题

---

01背包问题

f[i][j]表示只看前i个物品，总体积是j的情况下，总价值最大是多少。

result = max{f[n][0~V]}

f[i][j]:
1. 不选第i个物品，f[i][j] = f[i - 1][j];
2. 选第i个物品，f[i][j] = f[i - 1] [j - v[i]] + w[i];

f[i][j] = max{1. 2.}

f[0][0] = 0;

未优化版

#include <iostream>
using namespace std;
const int N = 1010;

int n, m;
int f[N]; // f[i][j], j体积下前i个物品的最大价值 
int v[N]; // 体积
int w[N]; // 价值

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
	
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			f[i][j] = f[i - 1][j];
			if (j >= v[i]) // 如果装得下的话
			   f[i][j] = max(f[i][j], f[i - 1][j - v[i]] + w[i];
		}
		
	cout << f[n][m] << '\n';
	return 0;
}

因为每一层都是跟上一层有关的，所以用一维数组f[]即可，节省空间。

B站y总视频BV1qt411Z7nE下方的热心网友“呼啁哼”评论说明：

01背包问题空间优化的原理是：
我们其实还是进行双重循环
1. 外层for还是用来遍历原来二维数组的每一行（虽然现在已经没有二维数组了，但是表示的还是这个意义，只不过是用一维数组一直通过外层循环将每一行的值更新）
2. 内层循环就是在更新二维数组（同上一个括号内的说法）的每一行中的每一列的值。
3. 因此我们还想用上一行的值得时候，就不能从前往后了，要从后往前，更新某行最后一个值的时候，其实前面的值存储的还是上一行的所有值，所以不受影响。

优化版：1. 一维状态f[] 2. 边输入边处理

// 注意逆序更新状态f[j]
#include <iostream>
using namespace std;
const int N = 1010;

int n, m;
int f[N]; // 状态f[j]定义：N件物品，背包容量j下的最优解。

int main() {
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		int v, w;
		cin >> v >> w;
		for (int j = m; j >= v; j--) // 另一个优化：直接在循环条件里限制“当大于v[i]才取max”
			f[j] = max(f[j], f[j - v] + w);
	}
	
	cout << f[m] << '\n';
	return 0;
}

关于状态f[j]的补充说明：
二维下的状态定义f[i][j]是前i件物品，背包容量j下的最大价值。一维下，少了前i件物品这个维度，我们的代码中决策到第i件物品（循环到第i轮），f[j]就是前i轮已经决策的物品且背包容量j下的最大价值。

因此当执行完循环结构后，由于已经决策了所有物品，f[j]就是所有物品背包容量j下的最大价值。即一维f[j]等价于二维f[n][j]。

参考博客：ttps://www.acwing.com/solution/content/1374/

完全背包

#include <iostream>
using namespace std;

const int N = 1010;

int n, m;
int f[N];

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

多重背包

是01背包的扩展，所以也要注意倒序枚举体积。

未优化版

#include <iostream>
using namespace std;

const int N = 110;

int n, m;
int f[N];

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

二进制优化版

#include <iostream>
using namespace std;

const int N = 2010;

int n, m;
int f[N];

struct Good {
	int v, w;
};

int main() {
	vector<Good> goods;
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		int v, w, s;
		cin >> v >> w >> s;
		for (int k = 1; k <= s; k *= 2) {
			s -= k;
			goods.push_back({v * k, w * k});
		}
		if (s > 0) goods.push_back({v * s, w * s});
	}
	
	for (auto good : goods)
		for (int j = m; j >= good.v; j--)
			f[j] = max(f[j], f[j - good.v] + good.w);
	
	cout << f[m] << '\n';
	return 0;
}