【问题求解II-HW5.C】背包问题

本题虽然是经典的 01 背包问题 (它被称为 01 背包是因为每个物品要么选要么不选，只有两种状态)，但仍然有一些值得注意的细节。和 2-5-B 类似地，本题也需要仔细斟酌状态的选取。01 背包的一种常见状态设计是：令 $dp(i, j)$ 表示考虑到第 $i$ 个物品，使用容积为 $j$ 的背包，最多可以获得多少价值。转移考虑第 $i$ 个物品是否放进背包。方程是容易写出的：

$$ dp(i, j) = \max\{dp(i-1, j), dp(i-1, j-v_i) + w_i\} $$

时间总复杂度为 $O(nv)$。但本题中 $v$ 的取值范围很大，这样做无法通过。

考虑将值域更小的价值作为状态，将值域大的容积作为动态规划的值，重新设计：令 $dp(i, j)$ 表示考虑到第 $i$ 个物品，想要选取出总价值为 $j$ 的物品，至少需要多少容积。最终所有容积不超过 $v$ 的状态的 $j$ 的最大值即为题目所求。转移仍然考虑第 $i$ 个物品是否选择：

$$ dp(i, j) = \min\{dp(i-1, j), dp(i-1, j-w_i) + v_i\} $$

看上去和之前的方程式长得差不多，但现在时间复杂度变为了 $O(n\cdot \sum w_i)$。而且在做第 $i$ 轮时，第二维实际只需要枚举到 $\sum_{k=1}^iw_k$，因此实际实现时会有一个十分可观的小于 1 的常数因子，足够通过。

另外一个需要考虑的问题是: $O(n\cdot \sum w_i)$ 的空间复杂度似乎过高，使用了太多的内存。这里我们为大家介绍“滚动数组”的技术：观察状态转移方程，我们容易发现 $dp(i, *)$ 只使用了 $dp(i-1, *)$ 来更新自己的结果，因此在做 $dp(i+, *)$ 时仍然存留这 $dp(i-2, *)$ 以及更之前的数据就是对空间的浪费。因此我们的 dp 数组可以只开两行：$dp(previous, *)$ 和 $dp(current, *)$。current 层依赖 previous 层获取结果，然后 previous 和 current 互换，依次类推。采用滚动数组的代码通常会写成如下形式：

int dp[2][MAXN];

int previous = 0, current = 1;
for (int i = 1; i <= n; i++)
{
    // DP logic: dp[current][...] = compute(dp[previous][...])
    swap(previous, current);
}

滚动数组是压缩空间的通用技术，不过就本题而言，我们还可以做得更激进一些，只需要开一维数组即可，这样代码书写起来也更加方便。你可以参考 2-3-C 关于空间优化的部分进行思考。