ztrztr 的博客 - DP
type: channel
link: https://typecho.ztrztr.top/tag/dp/
items: 01 背包

01 背包
type: item
date: 2024-05-05T00:51:38+08:00
description: 题目链接：洛谷 P1048题目大意给定一个最大重量为 $V$ 的背包，和 $n$ 个物品。每个物品有一个重量和价值。现在问在背包可以装下的范围内，最大的价值是多少。朴素 DP我们定义 dp[i][j] 为到第 $i$ 个物品，背包的重量为 $j$ 的最大价值。我们可以得出状态转移方程： $$\text{dpi = max(dpi - 1, dpi - 1] + v[i])}$$ 其中 $\text{w[i]}$ 是重量，$\text{v[i]}$ 是价值。 我们会发现，这样的代码的空间复杂度是 $O(nV)$，时间复杂度是 $O(nV)$，在有一些题目中会 MLE。 于是，我们有了以下优化。 ## 状态压缩 DP 我们发现 `dp[i][j]` 肯定是从 `dp[i - 1]` 转移过来的，于是我们可以尝试把 $i$ 的这一维度压缩掉，只剩**背包重量**这个的维度。 我们可以得出状态转移方程： $$ \text{dp[i] = max(dp[j], dp[j - w[i]] + v[i])} $$但是，状态压缩方程有一点需要注意的。在递推的时候，我们需要注意第二层虚幻需要从大到小遍历。因为如果是正着推的话，我们会发现方程就变成： $$\text{dpi = max(dpi - 1, dpi] + v[i])}$$ 因为 $dp[j - w[i]]$ 已经被更新了。 ### 代码 ```cpp #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); int dp[10005] = {0}, n, V, v, w; cin >> V >> n; for (int i = 1; i <= n; i++) { cin >> w >> v; for (int j = V; j >= w; j--) { dp[j] = max(dp[j], dp[j - w] + v); } } cout << dp[V]; return 0; } ```