题目链接：洛谷 P1048

题目大意

给定一个最大重量为 $V$ 的背包，和 $n$ 个物品。每个物品有一个重量和价值。现在问在背包可以装下的范围内，最大的价值是多少。

朴素 DP

我们定义 dp[i][j] 为到第 $i$ 个物品，背包的重量为 $j$ 的最大价值。

我们可以得出状态转移方程：
$$
\text{dp[i][j] = max(dp[i – 1][j], dp[i – 1][j – w[i]] + 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{dp[i][j] = max(dp[i – 1][j], dp[i][j – w[i]] + v[i])}
$$

因为 $dp[j – w[i]]$ 已经被更新了。

代码

#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;
}