背包九讲2——完全背包
题目
有 $N$ 件物品和一个容量是 $V$ 的背包。每件物品有无限件可用。
第 $i$ 件物品的体积是 $v_i$，价值是 $w_i$。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，$N$，$V$，用空格隔开，分别表示物品数量和背包容积。
接下来有 $N$ 行，每行两个整数 $v_i$, $w_i$，用空格隔开，分别表示第 $i$ 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
$0<N,V≤1000$
$0<v_i,w_i≤1000$
朴素方法：01背包转换
我们先回顾一下01背包的朴素解法：
我们使用二维数组 $f[i][j]$ ，表示前 $i$ 个物品放入空间为 $j$ 的背包中所能得到的最大价值。
因为每个物品只能选一次，所以对于物品 $i$ 且背包容量为 $j$ 的情况，我们有以下两种选择：
不选，此时最大价值等于前 $i-1$ 件物品的最大价值。
$f[i][j]=f[i-1][j]$
选，此时最大价值等于前 $i-1$ 件物品且背包容量为 $j-v[i]$ 时的最大价值。
$f[i][j] = f[i-1][j-v[i]]+w[i]$
两者取最大即可。
最终结果取 $f[n][m]$ 即可。
初始化： $f[0][j]$ 和 $f[i][0]$ 初始化为 $0$。
复杂度： 时间复杂度 $O(NV)$ ，空间复杂度 $O(NV)$
我们在01背包的基础上进行修改。当选择第 $i$ 件物品时枚举选择的个数。此时其空间复杂度肯定是要大于 $O(NV)$ 的，当数据量比较大的时候一般会超时的。
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int f[N][N];
int v[N], 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];
for (int k = 1; v[i] * k <= j; ++k) {
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
cout << f[n][m] << endl;
return 0;
}时间优化：二维数组
我们使用二维数组 $f[i][j]$ ，表示前 $i$ 个物品放入空间为 $j$ 的背包中所能得到的最大价值。
因为每个物品能选无限次，所以对于物品 $i$ 且背包容量为 $j$ 的情况，我们有以下两种选择：
不选，此时最大价值等于前 $i-1$ 件物品的最大价值。
$f[i][j]=f[i-1][j]$
选，此时最大价值等于前 $i$ 件物品且背包容量为 $j-v[i]$ 时的最大价值。
$f[i][j] = f[i][j-v[i]]+w[i]$
这样做的道理就是，我们可以由上式得出：$f[i][j-v[i]] = f[i][j-2\times v[i]]+2\times w[i]$，以此类推，状态 $f[i][j-v[i]]$ 可能已经包含了若干个物品 $i$。更准确的证明可以使用科学归纳法。
两者取最大即可。
最终结果取 $f[n][m]$ 即可。
初始化： $f[0][j]$ 和 $f[i][0]$ 初始化为 $0$。
复杂度： 时间复杂度 $O(NV)$ ，空间复杂度 $O(NV)$
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int f[N][N];
int v[N], 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][j - v[i]] + w[i]);
}
}
}
cout << f[n][m] << endl;
return 0;
}空间优化：一维数组
由于每一层的状态只与上一层有关，所以我们可以采用滚动数组来优化空间：
$f[j]$ 表示背包容量为 $j$ 时最大的价值。
$f[j] = max(f[j],f[j-v[i]])$
具体做法是：从 $1…N$ 顺序遍历物体，第二层循环我们仍要正向遍历，如上式，等号左边是要求的前 $i$ 件物品的价值，而等号右边是前 $i-1$ 件物品的价值，正序遍历保证了等号右边的数值是更新过的。
初始化： $f[0…V]=0$ ，若题目要求恰好装满背包，则 $f[0]=0, f[1..V] = -\infty$ ，这样保证了所有合法结果都是从 $f[0]$ 转移过来的，最后判断一下 $f[V]$ 是否合法即可。
复杂度： 时间复杂度 $O(NV)$ ，空间复杂度 $O(V)$
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, m;
int f[N];
int v[N], 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 = v[i]; j <= m; ++j) {
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m] << endl;
return 0;
}
