[算法模板随笔] 背包Part 1 01背包

最近在oi wiki上学感觉蛮快乐的, 比啃大部头书感觉效率来得快很多

今天来聊一下最经典的01背包问题吧.
01背包大概就是这样一个问题:

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

经典地, 我们可以用f[i][j]来表示, 用前i个物品, 在少于体积j的条件下, 能装的最大值. (局面的描述)

然后考虑下面这样一种转移
f[i][j] = max{f[i – 1][j], f[i – 1][j – v[i]] + w[i]}

我们很容易能写出下面这样的代码:

/*
Author: SJ

general 
1.shuzu buyao kai xiaole
2.0 1 zhe liangge tepan
3.dfs jide biaoji qidian
4.changdaima jide fenbu tiaoshi
5.yao xihuanshang heihezi

str
1.yongle s.substr(), jide kanyixiashibushikeyi yigeyige shuchu

THINK TWICE, CODE ONCE.
Duo xiang ti, Shao jiao lv.
*/
#include<bits/stdc++.h>
const int N = 1e3 + 10;
using ll = long long;

int n, m, v[N], w[N], f[N][N];
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> n >> m;
	for (int i = 1; i <= n; i++) std::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] = std::max(f[i][j], f[i - 1][j - v[i]] + w[i]);
		}
	}
	std::cout << f[n][m];
	return 0;
}

很好理解, 从集合的角度考虑, 只有两种情况, 拿第i个或者不拿第i个.(第一维是0的话, 意味着根本就不选, 最值肯定也是0, 所以不用管他)

那我们现在考虑怎么来优化这个算法, 第一种情况, 我们可能会写出这样的错误代码:

/*
Author: SJ

general 
1.shuzu buyao kai xiaole
2.0 1 zhe liangge tepan
3.dfs jide biaoji qidian
4.changdaima jide fenbu tiaoshi
5.yao xihuanshang heihezi

str
1.yongle s.substr(), jide kanyixiashibushikeyi yigeyige shuchu

THINK TWICE, CODE ONCE.
Duo xiang ti, Shao jiao lv.
*/
#include<bits/stdc++.h>
const int N = 1e3 + 10;
using ll = long long;

int n, m, v[N], w[N], f[N][N];
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> n >> m;
	for (int i = 1; i <= n; i++) std::cin >> v[i] >> w[i];

	for (int i = 1; i <= n; i++) {
		for (int j = v[i]; j <= m; j++) {
			if (j >= v[i]) f[i][j] = std::max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
		}
	}
	std::cout << f[n][m];
	return 0;
}

这种情况下, f[i – 1][j]可能会仍旧是0, 也就是根本没有更新到(比如v[i]比背包总体积m还大时, 第二层循环就会直接被跳过去了, 那f[i – 1]维就全部都是0了(或者是第i维要的状态第i – 1维没有, 反例很好想). 所以从第二维做优化的思路不太可行.

换一个思路, 我们从第一维做优化, 观察发现, 第i维的状态只会从第i – 1维转移而来, 那我们可以用类似0-1滚动的方式来优化了.

/*
Author: SJ

general 
1.shuzu buyao kai xiaole
2.0 1 zhe liangge tepan
3.dfs jide biaoji qidian
4.changdaima jide fenbu tiaoshi
5.yao xihuanshang heihezi

str
1.yongle s.substr(), jide kanyixiashibushikeyi yigeyige shuchu

THINK TWICE, CODE ONCE.
Duo xiang ti, Shao jiao lv.
*/
#include<bits/stdc++.h>
const int N = 1e3 + 10;
using ll = long long;

int n, m, v[N], w[N], f[N];
int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	std::cin >> n >> m;
	for (int i = 1; i <= n; i++) std::cin >> v[i] >> w[i];

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

这里有两个非常重要的思考

1. 为什么第二层循环一定要逆序呢, 实际上啊, 循环开始时, 这个一维数组, 存储的就是原来二维数组f[i – 1]维的所有状态, 假如从大到小循环的话, f[j – v[i]]就会在f[j]前面被更新到, 也就是f[j – v[i]]此时是f[i][j – v[i]]了, 但是我们要的是f[i – 1][j – v[i]], 所以就不对了, 那我们让它逆序循环就好了.
2. 为什么之前我们说过直接优化第二维不太可行, 但是这里又貌似可以了呢. 这是因为之前用二维数组存储状态时, 直接优化第二维会让有些时候第i维需要的i – 1维的状态为0. 但是在这里就不存在这种问题了, 第i – 1维没更新过的状态自然也就等于第i – 2维的状态, 刚好是符合条件的.

原文地址：http://www.cnblogs.com/IhopeIdieyoung/p/16905379.html