[AcWing 2] 01背包问题

1. 朴素做法（二维数组）

#include

using namespace std;
const int N = 1010;

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] << endl;
    return 0;
}

1. \(f[i][j]\)：前 \(i\) 个物品，背包容量为 \(j\) 的条件下的最大价值
2. \(f[i][j]\) 可以分成两种情况
   ① 不选第 \(i\) 个物品，只在前 \(i - 1\) 个物品中选择，对应了 \(f[i][j] = f[i-1][j]\)
   ② 选第 \(i\) 个物品，前提是能够装得下第 \(i\) 个物品，也就是 \(j >= v[i]\)，在这种情况下，还需要在前 \(i - 1\) 个物品中选择，背包容量为 \(j - v[i]\)，也就是 \(f[i - 1][j - v[i]]\)，最后的 $f[i][j] = f[i - 1][j - v[i]] + w[i] $
3. 状态转移：$ f[i][j] = max(f[i-1][j],f[i-1][j-v[i]] + w[i])$ ，
   \(f[i-1][j-v[i]] + w[i]\) 存在的前提是 $ j >= v[i] $

2. 一维数组优化

#include

using namespace std;
const int N = 1010;

int n, m;
int v[N], w[N];
int f[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 = m; j >= v[i]; j --)
                f[j] = max(f[j], f[j - v[i]] + w[i]);
    cout << f[m] << endl;
    return 0;
}

1. $ f[i][j] $ 的状态转移仅依赖于 $ f[i-1][0] $ ~ $ f[i-1][m] $ ，可以用一维数组来进行更新，每次枚举到 \(i\) 时，当前的 \(f[j]\) 都相当于是 \(f[i-1][j]\)
2. $ j $ 要从 $ m $ 枚举到 $ j >= v[i] $，原因如下：
   ① \(j\) 要从后往前枚举：$ f[j] $ 的更新依赖的是 \(i - 1\) 对应的 \(f[j]\)，需要保证在更新时，$ f[j] $ 的更新不会影响到后续的 $ f[j'] $ 的更新，$ f[i][j] = max(f[i-1][j],f[i-1][j-v[i]] + w[i])$，可以发现，对于 \(j\) 的更新依赖的是 \(j\) 和 $j - v[i] $，这两项都小于等于 \(j\)，那么从后往前枚举，\(f[j]\) 的更新必然不会影响到 \(f[j'] \ (j' 的更新
   ② \(j >= v[i]\) : 当 $ j < v[i] $ 时，$ f[i][j] = f[i - 1][j] $，而一维数组的 \(f[j]\) 正是 \(f[i-1][j]\)，故不需要更新，循环体的内部是 $ f[j] = max(f[j], f[j - v[i]] + w[i]) $，这个状态更新的前提是 \(j >= v[i]\)