滚动数组优化

在背包问题中，往往状态表示方程是二维的，但在一些情况下，即每一阶段 $i$ 的状态只与上一阶段 $i - 1$ 的状态有关，转移方程中可以使用一维数组来代替原二维数组，降低空间开销，这种方式叫做滚动数组

01背包问题

先来看 01背包问题 ：

状态表示: $F(i,j)$ 表示用容量为 $j$ 的背包从前 $i$ 种物品中选出的最大价值总和

转移方程:
$$F(i, j)= max \begin{cases} F(i-1, j) \qquad \textbf{不选第}i \textbf{个物品}\\\ \\\ F(i-1, j - v_i)+w_i \quad(j \geq v_i) \qquad \textbf{选第}i \textbf{个物品}\\\ \end{cases}$$

代码为：

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];

注：（以下省略 $w[i]$ ，只讨论带 $f[\;][\;]$ 的情况）

我们可以看到，因为 $j$ 是从小到大变化的，所以在 $j < v[i]$ 时，所有的 $f[i][j]$ 都是和上一阶段一样的，即
$f[i][j] = f[i - 1][j]$；而当 $j$ 逐渐增大到满足 $j \geq v[i]$ 时，参与比较的是 $f[i][j]$ 和 $f[i - 1][j - v[i]]$。因为 $j$ 是从小到大变化的，所以当 $j$ 第一次满足 $j \geq v[i]$ 时，此时一定为 $v[i] \leq j \leq 2v[i]$，那么这时的 $f[i][j]$ 还是初始时被赋值的 $f[i - 1][j]$ ,即此时参与比较的其实是 $f[i-1][j]$ 和 $f[i - 1][j - v[i]]$。而当 $j$ 继续增大到满足 $2v[i] \leq j \leq 3v[i]$ 时，参与比较的 $f[i][j]$ 其实是上一次 $f[i-1][j]$ 和 $f[i - 1][j - v[i]]$ 的结果。可以发现不管怎么进行比较，当前 $i$ 状态下总是和上一阶段也就是 $i-1$ 有关，所以可以用滚动数组进行优化：即没必要刻意使用二维数组，因为 $f[i][\;]$ 总是用 $f[i-1][\;]$ 来更新的，所以不如去掉一维。

原理就是：每当 $i$ 进入新一层的循环时，此时的 $f[j]$ 的初始值为经过上一层循环的最终结果，即 $f[i-1][j]$，也就是利用 $for$ 循环的特性保证每次进入新阶段的初始值都是上一阶段的最终结果

那么01背包使用滚动数组优化之后为什么要倒序循环？
假设当前不用倒序循环，继续使用正序循环，代码如下：

for(int i = 1; i <= n; i ++)
        for(int j = v[i]; j <= m; j ++)
            f[j] = max(f[j], f[j - v[i]] + w[i]);

cout << f[m];

此时表示当外层循环到第 $i$ 个物品时，$F(j)$ 表示用容量为 $j$ 的背包从前 $i$ 个物品中选出的最大价值总和

但是这段代码最大的问题在于：如果存在一个 $f[j]$ 被 $f[j-v_i] + W_i$ 更新了，即此时的方案 $f[j]$ 中包含了第 $i$ 件物品，在同样的 $i$ 下， $j$ 增加到 $j + v_i$ 时，即此时 $j^\prime=j+v_i$ ,那么就变成了 $max(f[j^\prime], f[j^\prime-v_i]+w_i)$ ，即 $max(f[j^\prime], f[j]+w_i)$ 。如果更新成了 $f[j^\prime] = f[j] + w[i]$ ，那么就发生了冲突： 方案 $f[j]$ 中已经包含了第 $i$ 件物品，却又加了一次 $w[i]$

为了解决这种问题，我们将 $j$ 采取倒序循环的方式，即for(int j = m; j >= v[i]; j --)，这样当产生上述情况的 $max(f[j^\prime], f[j^\prime-v_i]+w_i)$ 时， $f[j]$ 还没有被更新，也就不会出现重复选择的情况

完全背包问题

再来看完全背包问题 ：

状态表示: $F(i,j)$ 表示用容量为 $j$ 的背包从前 $i$ 种物品中选出的最大价值总和

转移方程：
$$F(i, j)= max \begin{cases} F(i-1, j) \qquad \textbf{不选第}i \textbf{种物品}\\\ \\\ F(i, j - v_i)+w_i \quad(j \geq v_i) \ \textbf{选了}1\textbf{件第}i \textbf{种物品，后续仍可以选}\\\ \end{cases}$$

代码如下：

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][j - v[i]] + w[i]);
        }

cout << f[n][m];

因为 $j$ 是从小到大变化的，所以在 $j < v[i]$ 时，所有的 $f[i][j]$ 都是和上一阶段一样的，即
$f[i][j] = f[i - 1][j]$。而当 $j$ 逐渐增大到满足 $j \geq v[i]$ 时，因为 $j$ 是从小到大变化的，所以当 $j$ 第一次满足 $j \geq v[i]$ 时，此时一定为 $v[i] \leq j \leq 2v[i]$ ，那么此时 $j-v[i]$ 一定是一个 $0$~$j$ 的数，那么此时的 $f[i][j-v[i]]$ 其实是 $f[i-1][\;]$ 的某个数。

举例如下：（此时讨论的是当 $j$ 第一次满足 $j \geq v[i]$ 的情况）

如果 $j=v[i] + 1$ ，那么 $max(f[i][j], f[i][j - v[i]] + w[i])$ 实际为 $max(f[i-1][j], f[i][1] + w[i])$，而此时 $f[i][1]$ 实际为 $f[i-1][1]$，因此最终为 $max(f[i-1][j], f[i-1][1] + w[i])$

如果 $j=v[i] + 2$ ，那么 $max(f[i][j], f[i][j - v[i]] + w[i])$ 实际为 $max(f[i-1][j], f[i][2] + w[i])$，而此时 $f[i][2]$ 实际为 $f[i-1][2]$，因此最终为 $max(f[i-1][j], f[i-1][2] + w[i])$

依此类推，发现当 $j$ 第一次满足 $j \geq v[i]$ 时进行比较的还是 $i-1$ 阶段的值

而当 $j$ 继续增大到满足 $2v[i] \leq j \leq 3v[i]$ 时：

如果 $j=2v[i] + 1$ ，那么 $max(f[i][j], f[i][j - v[i]] + w[i])$ 实际为 $max(f[i-1][j], f[i][v[i]+1] + w[i])$，$f[i][v[i]+1]$ 是在上面所举例的第一轮比较中得到的数，所以不管怎么比较本质都是使用 $i-1$ 阶段的值，因此也可以使用滚动数组来优化

因为完全背包问题可选物品数量没有限制，所以不需要像01背包问题一样考虑一件物品选重复的情况，即优化后不需要刻意用倒序循环

多重背包问题

最后看多重背包问题 ：

状态表示:$F(i,j)$ 表示用容量为 $j$ 的背包从前 $i$ 种物品中选出的最大价值总和

转移方程：假设第 $i$ 种物品上限为 $s_i$ 件，设该物品当前拿了 $k$ 件，则有:
$$F(i, j) = max(F(i, j), F(i - 1, j - (v_i) * k) + w_i * k)\quad (k <= s_i 且 k * v_i <= j)$$

代码如下:

for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= m; j ++)
            for(int k = 0; k <= s[i] && k * v[i] <= j; k ++)
                f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);

cout << f[n][m];

可以看到，每次循环都是用 本阶段更新后的值 与 上阶段的值 进行比较，所以无法使用滚动数组来做优化

而如果我们把第 $i$ 种物品看作是独立的 $s_i$ 个物品，也就是变成了01背包问题，就可以使用滚动数组进行优化了

for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= s[i]; j ++)
            for(int k = m; k >= v[i]; k --)
                f[k] = max(f[k], f[k - v[i]] + w[i]);

int ans = 0;
for(int i = 0; i <= m; i ++)
    ans = max(ans, f[i]);

cout << ans;