01 背包学习笔记升级版
AFO_Lzx
·
·
算法·理论
众所周知，一篇专栏也需要一个头图。
于是，本文出现了。这里有一个建议搭配使用的比赛。邀请码为 zli5。
\texttt{Part 1 01} 背包模板
[题目传送门在这里。](https://www.luogu.com.cn/problem/U523050)
- 确定**状态**：$dp_{i,j}$ 表示前面 $i$ 件物品，任意挑选装入背包**容量**为 $j$ 的背包之中可以获取的**最大价值**。$j$ 就是**背包的容量**，整个背包**可以不装满**。所以这就是**部分背包问题**。
- 确定**答案**：易得其为 $dp_{n,m}$。
- 确定**状态转移方程**：对于第 $i$ 件物品，一共**两种情况**。
- **第一种**：准备装入：
- 当**装得下**时：$dp_{i,j}=dp_{i-1,j-w_i}+val_i$。
- 当**装不下**时：$dp_{i,j}=dp_{i-1,j}$。
- **第二种**：不准备装入：
- $dp_{i,j}=dp_{i-1,j}$。
- **合并**之后可以发现：
- $$dp_{i,j}=\max(dp_{i-1,j},dp_{i-1,j-w_i}+val_i)$$。
- **初始化**和**边界**：**全部**为 $0$。
代码实现如下：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e3 + 5;
int n, m, w[maxn], val[maxn];
int dp[maxn][maxn];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> m >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> val[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= w[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - w[i]] + val[i]);
}
}
cout << dp[n][m] << endl;
return 0;
}
```
但是，有些毒瘤的出题人会卡我们的空间，这个时候，我们就需要进行**滚动数组优化空间**。
我们注意到，每一次的状态转移中，只用到了 `dp[i - 1][j]` 和 `dp[i - 1][j - w[i]]` 两个前面的量，而且关于 $i$ 的下标都是 $i-1$。所以，我们可以另外开一个数组 $pre$，维护所有的 $dp_{i-1,j}\ (0 \le j \le m)$ 的值，这样转移方程就可以为：
$$dp_j = \begin{cases} pre_j & j < w_i \\ \max(pre_j,pre_{j-w_i}+val_i) & j \ge w_i \end{cases}$$
但是，这样我们就需要在每一次的转移方程之后：
```cpp
for (int j = 0; j <= m; j++) pre[j] = dp[j];
```
这样是为了存储当前的 $dp_j$ 的值，以便下一次转移的时候使用。这就是**滚动数组**的使用方式。所以，本题优化后的完整代码如下：
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1e3 + 5;
int n, m, w[maxn], val[maxn];
int dp[maxn];
int pre[maxn];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> m >> n;
for (int i = 1; i <= n; i++) {
cin >> w[i] >> val[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
dp[j] = pre[j];
if (j >= w[i]) dp[j] = max(dp[j], pre[j - w[i]] + val[i]);
}
for (int j = 0; j <= m; j++) pre[j] = dp[j];
}
cout << dp[m] << endl;
return 0;
}
```
板子到此就讲完了。当你掌握了上面的内容之后，你就可以迅速地切掉这场比赛的前两题了。稍加思考之后，你也可以切掉第三题。
### $\texttt{Part 2}$ 二维费用背包
实际上，二维费用背包就是有双重的费用，要满足两种费用都能够付出才能够购买这种物品。我们只需要将每一次的循环多开一维即可。但是还有一个重点，就是**初始化问题**。一般情况下，我们需要将其整体设为一个**极大值**或**极小值**，然后让 $dp_{0,0,0}=0$。但有的题目可能有些特殊，需要自行调整。
注意，**二维费用背包**也是可以使用**滚动数组优化**的。这样就可以将数组变为二维。当然，这也增加了**时间复杂度**。之前我们讲到，$\texttt{DP}$ 是用**空间换时间**，但是如果出题人要**卡空间**的话，那么我们就需要用**滚动数组优化**的方式用**时间换空间**。
来一道例题试试手。[洛谷 P1507](https://www.luogu.com.cn/problem/P1507)
有了前面的基础，我们很快就能打出如下的代码，注意滚动数组只能滚掉关于 $i$ 的一维，是不能滚掉关于**费用**维度的。所以，当我们做 $n$ 维费用背包的时候，原本需要开 $(n+1)$ 维的数组，但是经过**滚动数组**的优化之后，就只有 $2$ 个 $n$ 维的数组了。
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 4e2 + 5;
const int INF = 2e9;
int n, m, k, h[maxn], t[maxn], kl[maxn];
int dp[maxn][maxn];
int pre[maxn][maxn];
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= k; i++) {
cin >> h[i] >> t[i] >> kl[i];
}
memset(pre, INF, sizeof(pre));
pre[0][0] = 0;
for (int i = 1; i <= k; i++) {
for (int j = 0; j <= n; j++) {
for (int l = 0; l <= m; l++) {
dp[j][l] = pre[j][l];
if (j >= h[i] && l >= t[i]) dp[j][l] = max(dp[j][l], pre[j - h[i]][l - t[i]] + kl[i]);
}
}
for (int j = 0; j <= n; j++) {
for (int l = 0; l <= m; l++) {
pre[j][l] = dp[j][l];
}
}
}
cout << dp[n][m] << endl;
return 0;
}
```
掌握了二维费用背包之后，你可以切掉这场比赛的第五题和第六题。实际上 T7 是一个较难的一维费用，多加思考之后也可以切掉。
### $\texttt{Part 3}$ 存在性问题
实际上存在性问题比较简单，就是要满足一些 $\texttt{DP}$ 的基本条件，满足就标为 $1$，不满足就为 $0$。实在不会就去 [OI-wiki](https://oi.wiki/dp/knapsack/) 里面找吧。
这里找一道较难的例题来分析。[P1284 三角形牧场](https://www.luogu.com.cn/problem/P1284)
```#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 1605;
int dp[maxn][maxn];
int pre[maxn][maxn];
int l[45];
/*
1.确定状态
dp[j][k] 表示前面 i 块木板，是否可以组装出来
2.确定答案
dp[j][k] 中找最大的三角形面积，具体看代码
3.状态转移方程
两个都装得下：
dp[j][k] |= pre[j - l][k] | pre[j][k - l]
一个装得下：
dp[j][k] |= pre[j - l][k]
另一个装得下：
dp[j][k] |= pre[j][k - l]
装不下:
dp[j][k] |= 0
4.初始值和边界
pre[0][0] = 1，其余为 0
*/
int mj(int x, int y, int z) {
double p = (x + y + z) / 2.0;
double s = sqrt(p * (p - x) * (p - y) * (p - z));
return 100 * s;
}
bool pd(int a, int b, int c) {
return a + b > c && a + c > b && a < b + c;
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
int n;
cin >> n;
int sum = 0;
for (int i = 1; i <= n; i++) {
cin >> l[i];
sum += l[i];
}
pre[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= sum; j++) {
for (int k = 0; k <= sum; k++) {
dp[j][k] = pre[j][k];
if (j >= l[i] && k >= l[i]) dp[j][k] |= pre[j - l[i]][k] | pre[j][k - l[i]];
else if (j >= l[i]) dp[j][k] |= pre[j - l[i]][k];
else if (k >= l[i]) dp[j][k] |= pre[j][k - l[i]];
else dp[j][k] |= 0;
}
}
for (int j = 0; j <= sum; j++) {
for (int k = 0; k <= sum; k++) {
pre[j][k] = dp[j][k];
}
}
}
int ans = -1;
for (int j = 0; j <= sum; j++) {
for (int k = 0; k <= sum; k++) {
if (dp[j][k]) {
int tmp = sum - j - k;
if (pd(j, k, tmp)) ans = max(ans, mj(j, k, tmp));
}
}
}
cout << ans << endl;
return 0;
}
```
边打代码边写的注释，于是就不用 $\text{Markdown}$ 和 $\LaTeX$ 了。
弄懂了存在性问题，就可以把 T4 切掉，于是你 AK 了本场模拟赛，恭喜。
