概述前面两篇我们已经讲了动态规划的基础思路和线性 DP。如果说线性 DP 主要训练的是沿着一条线往前推那么背包问题训练的就是在有限容量里做选择背包问题非常经典也非常容易让初学者卡住。原因不在于代码多复杂而在于它同时考察三件事状态怎么定义物品能不能重复选一维优化时循环顺序怎么写本篇重点讲两个最基础、最重要的模型01 背包完全背包学完这篇你应该能分清 01 背包和完全背包并能独立写出二维 DP、一维优化和循环顺序。核心概念什么是背包问题背包问题通常有这样一个背景有一个容量为bagSize的背包有若干物品每个物品有重量和价值问在容量限制内能获得的最大价值。比如物品重量1, 3, 4 物品价值15, 20, 30 背包容量4你要决定哪些物品放进背包让总重量不超过4同时总价值最大。背包问题的三个关键变量物品下标i当前考虑到第几个物品背包容量j当前背包最多还能装多少重量状态值dp在当前条件下能得到的最大价值背包问题的本质背包问题的本质不是“装东西”而是“做选择”当前物品选不选当前物品能不能重复选选了之后容量怎么变化背包 DP 的本质是在容量限制下枚举物品选择并保存最优结果。01 背包每个物品最多只能选一次先看最经典的01 背包。它的限制是每个物品只有一个要么选要么不选所以叫01意思是每个物品只有两种状态0不选1选问题示例weights [1, 3, 4] values [15, 20, 30] bagSize 4可选方案包括选重量1的物品价值15选重量3的物品价值20选重量4的物品价值30选重量1 3的两个物品价值15 20 35所以最大价值是35。01 背包二维 DP先把状态定义清楚初学背包时建议先写二维 DP。二维 DP 更容易理解因为状态含义比较直观。状态定义定义dp[i][j] 表示从下标 0 到 i 的物品里任意选择放进容量为 j 的背包能得到的最大价值这里有两个维度i考虑到哪个物品j当前背包容量状态转移对于第i个物品有两种选择。1. 不选第 i 个物品如果不选第i个物品那么结果直接继承上一行dp[i][j] dp[i - 1][j]2. 选第 i 个物品如果选第i个物品前提是当前容量j放得下它。选了之后背包剩余容量是j - weights[i]所以价值是dp[i - 1][j - weights[i]] values[i]合并转移因此dp[i][j] max( dp[i - 1][j], dp[i - 1][j - weights[i]] values[i] )注意第二项只有在j weights[i]时才成立。当前物品只有选和不选两种情况选了就只能从上一层状态转移过来。01 背包二维代码实现classSolution{publicintzeroOneKnapsack(int[]weights,int[]values,intbagSize){intnweights.length;int[][]dpnewint[n][bagSize1];for(intjweights[0];jbagSize;j){dp[0][j]values[0];}for(inti1;in;i){for(intj0;jbagSize;j){dp[i][j]dp[i-1][j];if(jweights[i]){dp[i][j]Math.max(dp[i][j],dp[i-1][j-weights[i]]values[i]);}}}returndp[n-1][bagSize];}}初始化为什么这样写第一行dp[0][j]表示只考虑第0个物品。如果容量j能装下第0个物品那么最大价值就是values[0]。所以for(intjweights[0];jbagSize;j){dp[0][j]values[0];}为什么返回dp[n - 1][bagSize]因为我们最终要考虑所有物品并且背包容量是bagSize。所以答案就是dp[n - 1][bagSize]二维 01 背包最重要的是看懂dp[i][j]代表“前 i 个物品在容量 j 下的最优解”。01 背包一维优化为什么可以压缩空间观察二维转移dp[i][j] 只依赖 dp[i - 1][j] 和 dp[i - 1][j - weights[i]]也就是说第i行只依赖上一行。因此可以把二维数组压缩成一维数组。一维状态定义定义dp[j] 表示容量为 j 的背包当前能得到的最大价值转移写成dp[j] max(dp[j], dp[j - weights[i]] values[i])关键问题为什么容量要倒序遍历01 背包一维优化时容量必须倒序遍历for(intjbagSize;jweights[i];j--){dp[j]Math.max(dp[j],dp[j-weights[i]]values[i]);}原因是每个物品只能选一次如果正序遍历dp[j - weights[i]]可能已经在本轮被当前物品更新过。这样就会导致同一个物品被重复使用。01 背包倒序遍历是为了保证当前物品不会在同一轮被重复选择。01 背包一维代码实现classSolution{publicintzeroOneKnapsack(int[]weights,int[]values,intbagSize){int[]dpnewint[bagSize1];for(inti0;iweights.length;i){for(intjbagSize;jweights[i];j--){dp[j]Math.max(dp[j],dp[j-weights[i]]values[i]);}}returndp[bagSize];}}一维写法的理解方式外层枚举物品内层枚举容量。对于每个物品都尝试把它放进不同容量的背包里。如果放进去能让价值更大就更新dp[j]。一维 01 背包的模板很短但倒序遍历是不能改的核心规则。完全背包每个物品可以选无限次接着看完全背包。它和 01 背包最关键的区别是每个物品可以重复选择比如有一个重量为2、价值为5的物品只要容量允许就可以选多次。问题示例weights [1, 3, 4] values [15, 20, 30] bagSize 4如果每个物品可以无限选那么最优方案可能是选 4 个重量为 1 的物品总价值 60这和 01 背包完全不同。完全背包允许同一个物品重复使用所以转移来源和循环顺序都会变化。完全背包二维 DP和 01 背包的关键差异二维完全背包也可以这样定义dp[i][j] 表示从下标 0 到 i 的物品里任意选择放进容量为 j 的背包能得到的最大价值不选第i个物品时dp[i][j] dp[i - 1][j]选第i个物品时注意这里不是从dp[i - 1]转移而是从dp[i]转移dp[i][j] dp[i][j - weights[i]] values[i]因为第i个物品可以继续选。合并转移dp[i][j] max( dp[i - 1][j], dp[i][j - weights[i]] values[i] )这里和 01 背包最大的区别是第二项类型选当前物品时的来源原因01 背包dp[i - 1][j - weights[i]]当前物品只能选一次完全背包dp[i][j - weights[i]]当前物品可以重复选01 背包选当前物品后看上一行完全背包选当前物品后仍然可以看当前行。完全背包一维代码实现完全背包一维写法最常见也最重要。classSolution{publicintcompleteKnapsack(int[]weights,int[]values,intbagSize){int[]dpnewint[bagSize1];for(inti0;iweights.length;i){for(intjweights[i];jbagSize;j){dp[j]Math.max(dp[j],dp[j-weights[i]]values[i]);}}returndp[bagSize];}}为什么完全背包容量要正序遍历完全背包允许同一个物品重复选择。所以我们希望dp[j - weights[i]]可以使用本轮已经更新过的结果。这正好对应正序遍历。如果倒序遍历就会变成“当前物品只能用一次”那就退化成 01 背包了。完全背包正序遍历是为了允许当前物品在同一轮被重复选择。01 背包和完全背包的模板对比这两个模板长得非常像区别主要在内层循环方向。01 背包模板for(inti0;in;i){for(intjbagSize;jweights[i];j--){dp[j]Math.max(dp[j],dp[j-weights[i]]values[i]);}}完全背包模板for(inti0;in;i){for(intjweights[i];jbagSize;j){dp[j]Math.max(dp[j],dp[j-weights[i]]values[i]);}}对比表类型每个物品可选次数容量遍历方向核心原因01 背包最多一次倒序防止同一物品重复使用完全背包无限次正序允许同一物品重复使用判断背包类型时先看物品能选几次再决定容量循环方向。组合问题和排列问题循环顺序还有另一层含义很多背包题不一定问最大价值而是问方案数。这时循环顺序还会影响“组合”和“排列”。组合问题如果不关心顺序例如1 2 和 2 1 算同一种方案通常先遍历物品再遍历容量for(inti0;inums.length;i){for(intjnums[i];jtarget;j){dp[j]dp[j-nums[i]];}}排列问题如果关心顺序例如1 2 和 2 1 算两种方案通常先遍历容量再遍历物品for(intj1;jtarget;j){for(inti0;inums.length;i){if(jnums[i]){dp[j]dp[j-nums[i]];}}}为什么顺序会影响结果因为dp[j]的更新顺序决定了方案是按“物品集合”统计还是按“选择顺序”统计。求组合通常物品在外求排列通常容量在外。常见题型背包不一定长得像背包很多题表面上看不出背包但本质都是背包模型。01 背包常见变形每个数字只能用一次选一些元素凑成目标和把数组分成两个和相等的子集每个物品只能选或不选典型状态dp[j] 表示容量为 j 时的最优值或可行性完全背包常见变形硬币可以无限使用数字可以重复选择求凑成目标值的最少数量求凑成目标值的方案数典型状态dp[j] 表示凑成 j 的最优值、最少数量或方案数只要题目出现“容量、目标值、选或不选、能否重复选”就应该联想到背包。背包问题的状态类型背包不只可以求最大价值还可以求很多不同目标。问法dp[j]含义初始化思路最大价值容量为j的最大价值通常初始化为0是否可达是否能凑出容量jdp[0] true方案数量凑出j的方案数dp[0] 1最少物品数凑出j的最少数量dp[0] 0其他设为较大值是否可达示例boolean[]dpnewboolean[target1];dp[0]true;for(intnum:nums){for(intjtarget;jnum;j--){dp[j]dp[j]||dp[j-num];}}这里倒序遍历说明每个num只能用一次。最少数量示例int[]dpnewint[amount1];Arrays.fill(dp,amount1);dp[0]0;for(intcoin:coins){for(intjcoin;jamount;j){dp[j]Math.min(dp[j],dp[j-coin]1);}}这里正序遍历说明每个coin可以重复使用。背包题先判断求什么再决定dp[j]存最大值、布尔值、方案数还是最少数量。常见问题点1. 分不清 01 背包和完全背包最核心的问题是当前物品能不能重复选如果不能重复选就是 01 背包。如果可以重复选就是完全背包。2. 一维优化时循环方向写反这是最常见错误。01 背包容量倒序完全背包容量正序3. 初始化不符合题意不同问题初始化不同最大价值通常初始化为0可行性问题通常dp[0] true方案数问题通常dp[0] 1最小值问题通常先填充一个较大值4. 忘记判断容量是否够二维写法里选当前物品时一定要判断j weights[i]一维写法可以通过循环起点规避这个问题。5. 把组合数和排列数混在一起求方案数时一定要看题目是否关心顺序。如果题目说[1, 2]和[2, 1]算不同方案那就是排列。如果只关心选了哪些数那就是组合。背包题大多数错误都来自类型判断、循环方向和初始化。复杂度分析背包 DP 的成本怎么看设物品数量为n背包容量为bagSize二维写法时间复杂度O(n * bagSize)空间复杂度O(n * bagSize)一维优化时间复杂度仍然是O(n * bagSize)空间复杂度优化为O(bagSize)为什么时间没有变因为物品和容量仍然都要枚举一遍。一维优化只是减少了保存状态的空间。背包 DP 通常是物品数乘容量一维优化主要优化空间不改变时间复杂度。标准思考流程遇到背包题应该怎么想建议按下面顺序分析。第一步判断是不是背包看题目里有没有这些关键词目标和容量限制选一些元素每个元素能不能重复用最大值、最小值、方案数、可行性第二步判断物品能选几次只能选一次 - 01 背包 可以无限选 - 完全背包第三步定义dp[j]想清楚dp[j] 表示什么它可能表示最大价值是否能凑出凑出方案数最少使用数量第四步确定初始化初始化一定要服务于dp[j]的含义。第五步确定循环顺序01 背包物品在外容量倒序 完全背包物品在外容量正序 排列问题容量在外物品在内背包题不要先背代码先判断类型、状态、初始化和循环顺序。模板总结01 背包最大价值模板int[]dpnewint[bagSize1];for(inti0;in;i){for(intjbagSize;jweights[i];j--){dp[j]Math.max(dp[j],dp[j-weights[i]]values[i]);}}returndp[bagSize];完全背包最大价值模板int[]dpnewint[bagSize1];for(inti0;in;i){for(intjweights[i];jbagSize;j){dp[j]Math.max(dp[j],dp[j-weights[i]]values[i]);}}returndp[bagSize];01 背包可行性模板boolean[]dpnewboolean[target1];dp[0]true;for(intnum:nums){for(intjtarget;jnum;j--){dp[j]dp[j]||dp[j-num];}}returndp[target];完全背包最少数量模板int[]dpnewint[amount1];Arrays.fill(dp,amount1);dp[0]0;for(intcoin:coins){for(intjcoin;jamount;j){dp[j]Math.min(dp[j],dp[j-coin]1);}}returndp[amount]amount?-1:dp[amount];背包模板看起来像几行代码但每一行都对应着物品次数、状态含义和循环顺序。总结背包问题是动态规划里非常重要的一类题。它的难点不是公式多而是模型判断和循环顺序。你可以重点记住下面几句话01 背包每个物品最多选一次完全背包每个物品可以重复选01 背包一维优化时容量倒序遍历完全背包一维优化时容量正序遍历最大价值、可行性、方案数、最少数量对应不同dp[j]含义求组合通常物品在外求排列通常容量在外初始化必须和状态定义严格对应背包问题刚开始学会觉得绕但一旦把“能不能重复选”和“循环顺序”这两个点打通很多题都会变成同一套模板的变形。