关于《背包九讲》

本文参考的《背包九讲》文章链接为：V2.pdf。

0-1 背包问题

题目：有 N 件物品和一个容量为 V 的背包，第 i 件物品的费用（占用背包空间）为 c_i，价值为 w_i。求解可获得的最大价值。

思路：对于每一个物品，可以选择选或不选。如果不选的话，f_{i,v} 的状态直接从 f_{i-1,v} 继承（相当于不变）；如果选的话，f_{i,v} 的状态就从 f_{i-1,v-c_i} 继承，加上选择获得的价值 w_i。所以，我们可以得到如下状态转移方程：

这是背包问题最基础的一个公式。如果第 i 件物品不选，其实就相当于在前 i-1 件物品中进行选择；如果第 i 件物品选，那么，就是在前 i-1 件物品的基础上，花费多了 c_i，价值多了 w_i。由于背包容量不能是负的，所以在遍历 v 的这一维时，要从 c_i 开始遍历到 V。C++ 代码如下：

for (int i=1; i<=n; i++) {
    for (int j=c[i]; j<=V; j++) {
        f[i][j] = max(f[i-1][j], f[i-1][j-c[i]] + w[i]);
    }
}

空间优化：容易发现，第 i 件物品的数据都是从第 i-1 件物品的数据继承的，与更前面的数据无关。由此，我们可以在每次遍历中摒弃掉前面过期的数据，也就是使用滚动数组优化。则状态转移方程为：

注意，由于我们更新要使用前面旧的数据，为了避免前面的数据被提前覆盖，需要倒序遍历。C++ 代码如下：

for (int i=1; i<=n; i++) {
    for (int j=V; j>=c[i]; j--) {
        f[j] = max(f[j], f[j-c[i]] + w[i]);
    }
}

初始化的细节问题：背包问题分为两种问法：一种问法是物品恰好装满背包，一种问法不要求物品恰好装满背包。对于第一种问法，需要将 f_0 初始化为 0，其余全部初始化为 -\infty。对于第二种问法，全部初始化为 0 即可。

这是因为，f 数组中保存的实际上是所有合法状态中的最大值。如果要求恰好装满背包，那么只有背包容量为 0 时什么都不装是合法的，其他容量在什么都不装时没有合法状态，需要初始化为负无穷。如果不要求恰好装满背包，那么对于每个容量，什么都不装都是一种花费和收益都为 0 的合法状态。