AcWing 2. 01背包问题

题面：
有 \(N\) 件物品和一个容量是 \(V\) 的背包。每件物品只能使用一次。
第 \(i\) 件物品的体积是 \(v_i\)，价值是 \(w_i\)。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

原链接：2. 01背包问题 - AcWing

• 有限集的最优问题：乘法原理，总方案数为 \(2^n\) ，在所有的方案中选择一个价值最大的方案。
• 对于 \(F(i,j)\)：
  • 集合：只考虑前 \(i\) 个物品，且总体积不超过 \(j\) ；
  • 属性：题目要求我们求最大价值，则其属性就是 \(max\)。
• 划分方案：所有不选第 \(i\) 个物品的方案 / 所有选第 \(i\) 个物品的方案（不重不漏）
  • 左集合（不选）：由于它在 \(F(i, j)\) 内，且不包含 \(i\)，即相当于 \(F(i-1, j)\)；
    • 即问题转化为：考虑前 \(i-1\) 个物品且总体积不超过 \(j\) 的情况下的最优解。
    • 将原始问题转化为一个更小的子问题进行求解，从而实现问题的分解和状态转移
  • 右集合（选）：再次细分，将 \(i\) 单独拿出来，得到 \(F(i-1, j-Vi)\)；
    • 表示考虑前 \(i-1\) 个物品且总体积不超过 \(j-Vi\) 的集合。
  • 也就是说求右边的最大值：\(max(F(i-1, j-Vi) + Wi)\)；
    • 即先前右集合的基础上加上第 \(i\) 个物品的价值 \(Wi\)。
  • 右集合不一定存在（\(j＜Vi\)），故特判：\(j ≥ Vi ≥ 0\)；
  • 状态转移方程：\(F(i, j) = max(F(i-1, j), F(i-1, j-Vi) + Wi)\) \(j≥Vi\)；
• 时间复杂度：物品数量 × 背包容量，因此本题的时间复杂度是 \(O(nv)\)。
• 循环顺序问题：板子为外层循环遍历物品，内层循环遍历容量；
  • 二维数组的两个for遍历的先后循序可以颠倒;
  • 一维数组的两个for循环先后循序一定是先遍历物品，再遍历背包容量。
• 滚动数组的容量倒序遍历问题^[1]：每次取的状态不会和之前取的状态重合；
  • 对于二维dp，dp[i][j]都是通过上一层即dp[i - 1][j]计算而来，本层的dp[i][j]并不会被覆盖。

#include<bits/stdc++.h>
using namespace std;

const int N = 1005;

int n, m;
int v[N], w[N];
int f[N][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 - 1][j - v[i]] + w[i]);
        }
    }
    cout << f[n][m];
    //优化-使用滚动数组：状态转移方程中的 F(i, j) 只与 F(i-1, x) 有关，且 x ≤ j
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v[i]; j--)
            f[j] = max(f[j], f[j - v[i]] + w[i]);
    //从大到小枚举背包容量 j：确保在计算 f[j] 时，f[j-v[i]] 已经被更新过：
    //后面的数据依赖于左上方的数据（f(i-1,j-x)），从小到大循环会导致状态依赖在计算前就被覆盖，即f(i-1,j-x)会在f(i,j)之前被更新为f(i,j-x)
    cout << f[m] << endl;
    return 0;
}