【算法设计与分析】第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],jw[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]},​jw[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行就再也不会被用到。这意味着我们不需要保留整个二维表。只需一个长度为W1的一维数组并在每一轮物品迭代中“就地”更新它。但这里有一个容易被忽视的细节——内层循环的方向。如果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背包我们看到的动态规划都是在一个有限的表格中按规则递推。下一篇我们将面对更具挑战性的字符串场景——最长公共子序列与编辑距离在那里状态将横跨两个序列二维表格上的转移方向也会更为丰富。