题目链接：洛谷 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; } ```
评论 (0)