背包问题

背包问题是较为经典的动态规划问题，各种背包问题从简单到复杂，对于不同背包的状态转移方程，不仅记住，也要弄明白它们是怎么得出来的，最好能够自己想一种得到这些方程的方法。事实上，对每一道动态规划题目都思考其方程的意义以及如何得来，是加深对动态规划的理解、提高动态规划功力的好方法。

01背包

题目

有 $N$ 件物品和一个容量为 $V$ 的背包。第i件物品的费用是 $w [i]$ ，价值是 $v [i]$ ，求将哪些物品装入背包可使价值总和最大。

基本思路

这是最基础的背包问题，特点是：每种物品仅有一件，可以选择放或不放。
用子问题定义状态：即 $f [i] [j]$ 表示前 $i$ 件物品恰放入一个容量为 $j$ 的背包可以获得的最大价值。则其状态转移方程便是：

$f [i] [j] = m a x (f [i ? 1] [j], f [i ? 1] [j ? w [i]] + v [i])$

时间复杂度： $O (V N)$
空间复杂度： $O (V N)$

优化空间复杂度

优化后的状态转移方程如下：

$f [j] = m a x (f [j], f [j ? w [i]])$

时间复杂度： $O (V N)$
空间复杂度： $O (N)$

使用一维数组 $f [j]$ 定义状态 $f [i] [j]$ ，需要注意的是，为了保证第 $i$ 次循环后， $f [j]$ 为 $f [i] [j]$ 的状态， $V$ 的循环顺序要逆序，否则 $f [j]$ 的状态为 $f [i] [j ? w [i]]$ 推知，而不是由 $f [i ? 1] [j ? w [i]]$ 推知，与题意不符。

初始化的细节问题

恰好装满背包： $f [1 . . . V] = ? \infty ， f [0] = 0$
不需装满背包： $f [0 . . . V] = 0$

可以这样理解：初始化的 $f$ 数组事实上就是在没有任何物品可以放入背包时的合法状态。如果要求背包恰好装满，那么此时只有容量为 $0$ 的背包可能被价值为 $0$ 的 $n o t h i n g$ “恰好装满”，其它容量的背包均没有合法的解，属于未定义的状态，它们的值就都应该是 $? \infty$ 了。如果背包并非必须被装满，那么任何容量的背包都有一个合法解“什么都不装”，这个解的价值为 $0$ ，所以初始时状态的值也就全部为 $0$ 了。

常数优化

针对 $V$ 较大时，可对循环进行改进。
由于只需要最后 $f [j]$ 的值，倒推前一个物品，其实只要知道 $f [j ? w [n]]$ 即可。以此类推，对于第 $j$ 个背包，其实只需要知道到 $f [j ? s u m (w [j . . . n])]$ 即可，保证有空间能装下剩余所有背包，即代码可以改成：

for (int i = 1; i <= n; i++) {
    int bound = max(V - sum{w[i + 1]...w[n]}, w[i]);
    for (int j = V; j >= bound, j--)
        f[j] = max(f[j], f[j - w[i]] + v[i]);
}

对于求 $s u m$ 可以用前缀和。
具体代码：

for (int i = 1; i <= n; i++) cin >> w[i] >> v[i], s[i] = s[i - 1] + w[i];
for (int i = 1; i <= n; i++) {
	int bound = max(w[i], V - (s[n] - s[i]));
	for (int j = V; j >= bound; j--)
		f[j] = max(f[j], f[j - w[i]] + v[i]);
}

例题

HDU 2602 Bone Collector

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int C, n, v[N], w[N], dp[N][N];
int main() {
	int t;
	cin >> t;
	while(t--) {
		cin >> n >> C;
		memset(dp, 0, sizeof(dp));
		for(int i=1; i<=n; i++)
			cin >> v[i];
		for(int i=1; i<=n; i++)
			cin >> w[i];
		for(int i=1; i<=n+1; i++) {
			for(int j=0; j<=C; j++) {
				if(j >= w[i])
					dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
				else 
					dp[i][j] = dp[i-1][j];
			}
		}
		cout << dp[n][C] << endl;
	}
	return 0;
}

洛谷 P1616 疯狂的采药

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=1e4+5,M=1e7+5;
ll n, m, w[N], v[N], f[M];
int main(){
	cin >> m >> n;
	for(int i=1; i<=n; i++)
		cin >> w[i] >> v[i];
	for(int i=1; i<=n; i++)
		for(int j=w[i]; j<=m; j++)
			f[j] = max(f[j], f[j-w[i]]+v[i]);
	cout << f[m] << endl;
	return 0;
}