【算法设计与分析】第7篇：01背包问题的动态规划建模与空间优化

给定一个容量有限的背包和若干件物品，每件物品有各自的重量和价值，每件物品只能选择装入或不装入，问在总重量不超过背包容量的前提下，能获得的最大价值。这就是经典的01背包问题，其名称来源于每件物品的“要么0要么1”的二元选择。

这个问题的暴力枚举需要O(2ⁿ)时间，而动态规划将它压缩到O(nW)，其中n为物品数量，W为背包容量。这个跨度，足以说明动态规划在处理组合优化时的威力。

一、二维动态规划建模

状态定义。令dp[i][j]表示从前i件物品中选取若干件，放入容量为j的背包中能获得的最大价值。这里i是物品索引的“考虑范围”，j是背包的“剩余容量”，两者共同构成状态空间的坐标。

最优子结构。考察第i件物品。它只有两种选择：不装入，则问题退化为前i-1件物品在容量j下的最优解dp[i-1][j]；装入，则需要在前i-1件物品、容量j-w[i]的基础上增加价值v[i]。只要j≥w[i]，我们就在两者之间取较大值。这给出了状态转移方程：

dp[i][j]={dp[i−1][j],j<w[i]max⁡{ dp[i−1][j],dp[i−1][j−w[i]]+v[i] },j≥w[i]dp[i][j]=⎩⎨⎧​dp[i−1][j],max{dp[i−1][j],dp[i−1][j−w[i]]+v[i]},​j<w[i]j≥w[i]​

初始化。dp[0][j]全为0——没有物品可选时，无论背包多大，价值都是零。dp[i][0]全为0——容量为零，装不下任何东西。

填表顺序。外层循环枚举i从1到n，内层循环枚举j从0到W，按行逐格填充。最终答案位于dp[n][W]。时间复杂度Θ(nW)，空间复杂度Θ(nW)。

二、滚动数组：从二维到一维的空间优化

观察上面的递推式可以发现一个关键性质：dp[i][j]的值只依赖于上一行dp[i-1]中的两个位置——正上方的dp[i-1][j]和左前方的dp[i-1][j-w[i]]。一旦第i行计算完成，第i-1行就再也不会被用到。

这意味着我们不需要保留整个二维表。只需一个长度为W+1的一维数组，并在每一轮物品迭代中“就地”更新它。但这里有一个容易被忽视的细节——内层循环的方向。

如果j从小到大遍历，那么dp[j-w[i]]在当前这一轮中可能已经被更新过了，代表的是dp[i][j-w[i]]而非我们需要的dp[i-1][j-w[i]]，这相当于允许同一件物品被重复使用（变成完全背包）。要避免这一点，j必须从W向w[i]递减遍历，确保dp[j-w[i]]读取到的是上一轮残留的值。

优化后的代码结构异常简洁：一维数组f初始全零，外层遍历物品，内层j从W递减到w[i]，执行f[j]=max(f[j], f[j-w[i]]+v[i])。空间复杂度从Θ(nW)降至Θ(W)。

三、背包问题的变形族

01背包是背包家族的基准模型，许多变体只需在转移方程上稍作调整。

完全背包：每件物品可以选无限次。只需将内层j的遍历方向改为从小到大，使同一物品可被反复选取。dp[j] = max(dp[j], dp[j-w[i]]+v[i])，j递增。

多重背包：每件物品有固定的数量上限s[i]。朴素方法是将s[i]个相同物品拆开当成01背包处理，但这样效率低下。更优的做法是二进制拆分：将s[i]分解为1,2,4,...,2ᵏ,剩余数这些“打包”后的新物品，每种最多选一次，转化为01背包求解。更高阶的优化是使用单调队列进行线性处理，但那已经属于进阶专题的范畴。

分组背包：物品被划分为若干组，每组内至多选一件。这需要在01背包的外层增加一个组枚举层，内层对组内物品做决策，循环顺序与01背包类似但需注意j循环在组内物品循环的外面，以保证每组只选一件。

四、为什么“容量”是多项式却不算多项式时间算法

一个值得思考的理论细节：背包问题的动态规划复杂度是O(nW)，n是物品数量，W是背包容量。看起来是多项式，但若W以输入中的二进制位数计，W的数值本身就是输入规模的指数。因此背包问题的DP解法实际是伪多项式时间算法，这一问题在NP完全性的讨论中将被再次提及。

从矩阵链乘法到01背包，我们看到的动态规划都是在一个有限的表格中按规则递推。下一篇，我们将面对更具挑战性的字符串场景——最长公共子序列与编辑距离，在那里状态将横跨两个序列，二维表格上的转移方向也会更为丰富。