背包问题本质是"在限制条件下，从若干个物品中做选择，使得某个价值最大化（或方案数/可行性）"。 所有背包变种的区别集中在三个维度：物品选择方式、限制条件数量和所求目标。 一般地， - 背包具有的属性：最大容积v - 物品具有的属性：价值w、体积v、每个物品的数量 - [01背包详解](https://kernelcode.cn/article/152) - [完全背包详解](https://kernelcode.cn/article/153) ## 一、按物品选择方式区分（最核心） ```bash 每个物品能选几次？ │ ┌─────────┼─────────┐ │ │ │ 0或1次 不限次数 有限定次数 │ │ │ 0-1背包 完全背包 多重背包 1. 0-1 背包 - 特征：每个物品最多选 1 次（选或不选） - 关键词："每个物品"、"选或不选" - 模板： # w 背包最大可装重量 # weights[ i ] 每个物品的重量 # values[ i ] 每个物品的价值 def backpack_01( w, weights, values ): n = len( weights ) # dp[ i ] 表示容积为i的最大价值 dp = [ 0 for _ in range( w + 1 ) ] for i in range( n ): # !important:01背包限定( 倒序遍历重量 ) for j in range( w, weights[ i ] - 1, -1 ): # 可以选中或不选 两者价值取最大 dp[ j ] = max( dp[ j - weights[ i ] ] + values[ i ], dp[ j ] ) return dp[ -1 ] - 经典题：LeetCode 416（分割等和子集）、494（目标和） 2. 完全背包 - 特征：每个物品可以选无限次 - 关键词："无限个"、"可以重复选"、"零钱兑换" - 模板： # w 背包最大可装重量 # weights[ i ] 每个物品的重量 # values[ i ] 每个物品的价值 def complete_backpack( w, weights, values ): n = len( weights ) # dp[ i ] 表示容积为i的最大价值 dp = [ 0 for _ in range( w + 1 ) ] for i in range( n ): # !important:完全背包限定( 正序遍历重量 ) for j in range( weights[ i ], w + 1 ): # 可以选中或不选 两者价值取最大 dp[ j ] = max( dp[ j - weights[ i ] ] + values[ i ], dp[ j ] ) return dp[ -1 ] - 经典题：LeetCode 322（零钱兑换）、518（零钱兑换 II） 3. 多重背包 - 特征：每个物品最多选 k 次（k 可能各不相同） - 关键词："每个物品有限个"、"最多选 k 个" - 优化方法： a) 二进制拆分：将每个物品的 k 个拆成 log(k) 个新物品，转成 0-1 背包 b) 单调队列优化：O(VN) - 经典题：AcWing 4、AcWing 5 ``` ## 二、按限制条件数量区分 **1. 一维背包（只有重量限制）** - dp[重量] → 最大价值 - 最常见的背包形式 **2. 二维费用背包** - 有两个限制条件（如重量和体积都要满足） - dp[重量][体积] → 最大价值 - 经典题：LeetCode 474（一和零，看作二维容量）、LeetCode 879（盈利计划） **3. 多维背包** - 三个及以上限制条件（少见，通常是状态压缩或优化掉一个维度） ## 三、按所求目标区分 **1. 求最大价值** - 给定容量，求能装的最大价值 - dp 数组存最大值 **2. 求方案总数** - 恰好装满背包的方案数 - dp[0] = 1，dp[j] += dp[j-weight] （组合数） - 经典题：LeetCode 518（零钱兑换 II）、494（目标和） - 注意区分组合数（先物品后容量）和排列数（先容量后物品） **3. 求可行性（True/False）** - 是否能恰好装满背包 - dp[j] = dp[j] or dp[j-weight] - 经典题：LeetCode 416（分割等和子集） **4. 求最少物品数** - 恰好装满背包所需的最少物品数 - dp[j] = min(dp[j], dp[j-weight] + 1) - 初始化为 INF，dp[0] = 0 - 经典题：LeetCode 322（零钱兑换）、279（完全平方数） ## 四、其他常见变种 ``` 4. 分组背包 - 特征：物品被分成若干组，每组最多选一个 - 关键词："每组至多选一个" - 模板： for 每组: for j 从 容量 到 0: ← 先枚举容量（倒序） for 该组的每个物品: dp[j] = max(dp[j], dp[j-weight] + value) - 经典题：LeetCode 1981（最小化目标值与所选元素的差的绝对值） - LeetCode 1155（掷骰子的N种方法，也可看作分组背包） 5. 依赖背包 / 树形背包 - 特征：选某个物品的前提是选了它的"父物品"（依赖关系构成一棵树） - 关键词："必须先选 A 才能选 B"、"附件和主件" - 模板：树形 DP + 背包思想 def dfs(u): dp[u] = [0] * (容量+1) for v in 子节点: dfs(v) for j 从 容量 到 0: for k 从 0 到 j: dp[u][j] = max(dp[u][j], dp[u][j-k] + dp[v][k]) - 经典题：AcWing 10（有依赖的背包问题） - 金明的预算方案（有附件的背包） 6. 泛化物品背包 - 物品的价值不再是固定值，而是关于消耗的函数 - 把每个物品当作一个价值函数 f(weight) → value - 较为罕见，竞赛范畴 ``` ## 五、快速判断流程 Step 1：识别是否为背包问题 - 有"物品"概念，有"容量/限制"概念，有"价值/选择"概念 - 物品可以被选或不选，有数量限制 Step 2：看物品可以被选几次 - 每个物品 0/1 次 → 0-1 背包（倒序容量） - 每个物品无限次 → 完全背包（正序容量） - 每个物品有限 k 次 → 多重背包（二进制优化 + 0-1 背包） Step 3：看有几个限制条件 - 只有一个容量限制 → 一维 dp - 有两个限制（容量+另一维度）→ 二维费用背包 Step 4：看问题要求什么 - "最大价值" → dp 存最大值 - "方案总数" → dp 累加求和 - "是否存在" → dp 存布尔值 - "最少物品数" → dp 存最小值 Step 5：看是否有特殊结构 - 物品分组，每组限选一个 → 分组背包 - 物品有依赖关系（选 A 才能选 B）→ 树形背包 - 要求组合数还是排列数 → 先物品还是先容量 ## 六、背包模板速查 | 类型 | 遍历顺序 | 初始化 | 转移方程 | |:---|:---|:---|:---| | 0-1 背包 | 物品后，容量倒序 | dp[0]=0 | dp[j]=max(dp[j],dp[j-w]+v) | | 完全背包 | 物品后，容量正序 | dp[0]=0 | dp[j]=max(dp[j],dp[j-w]+v) | | 多重背包 | 二进制拆成0-1背包 | 同0-1背包 | 同0-1背包 | | 分组背包 | 组后容量倒序（组内物品最后） | dp[0]=0 | dp[j]=max(dp[j],dp[j-w]+v) | | 求方案数(组合) | 先物品后容量（倒/正取决于背包类型） | dp[0]=1 | dp[j] += dp[j-w] | | 求方案数(排列) | 先容量（正序），后物品 | dp[0]=1 | dp[j] += dp[j-w] | ## 七、总结 区分背包问题的核心三问： 1. 物品能选几次？ → 决定 0-1 / 完全 / 多重 2. 有几个限制？ → 决定一维 / 多维 3. 求什么？ → 决定 dp 含义和初始化 只要顺着这三个问题逐个排除，就能准确定位是哪种背包模型。