1. 从一道经典题说起多重部分和到底在考什么多重部分和问题英文里常叫 Multi-Subset Sum 或者 Bounded Knapsack 的一个变种是动态规划训练里绕不开的一道坎。我第一次接触它的时候觉得这题平平无奇——不就是给一堆数每个数有有限个问能不能凑出某个目标值吗但真正动手写代码之后才发现这题能把人逼疯的地方不在于“能不能做出来”而在于“怎么做得足够快”。先把问题定义说清楚。给定 n 种不同面额的硬币或者数字每种面额有 m[i] 个再给定一个目标值 K问能否从这些硬币中选出若干枚使得面额之和恰好等于 K注意每种硬币的选取数量不能超过它给定的个数。这就是多重部分和问题的标准描述。它和完全背包的区别在于完全背包每种物品可以取无限次而多重部分和每种物品有明确的数量上限。它和 0-1 背包的区别在于0-1 背包每种物品只有一个而多重部分和每种物品可能有多个。所以你可以把它理解为介于两者之间的一种约束形态。为什么这道题值得单独拿出来训练因为它逼着你去思考状态定义的粒度、转移方程的优化空间以及如何用不同的 DP 姿势把复杂度从 O(nK²) 压到 O(nK)。很多初学者写完朴素解法就以为完事了结果一跑大数据量直接超时然后才开始理解“状态设计”这四个字的重量。这篇文章我会从最朴素的思路讲起一步步推导到 O(nK) 的最优解法中间会穿插我自己踩过的坑、调试时发现的细节问题以及几种不同实现方式的对比。适合已经了解动态规划基础、想进一步提升 DP 优化能力的读者。如果你连 0-1 背包都还没写过建议先去补一下基础再回来看这篇会更顺畅。2. 朴素解法为什么它是对的又为什么它不够快2.1 最直观的二维 DP 定义拿到这个问题最自然的想法是定义一个二维布尔数组dp[i][j]表示“用前 i 种硬币能否凑出金额 j”。状态转移的逻辑也很直接对于第 i 种硬币我可以选 0 个、1 个、2 个……直到 m[i] 个。只要其中任何一种选择能让dp[i-1][j - k * a[i]]为真那dp[i][j]就为真。写成代码大概是这样def multi_subset_sum_naive(n, K, a, m): dp [[False] * (K 1) for _ in range(n 1)] dp[0][0] True for i in range(1, n 1): for j in range(K 1): for k in range(m[i-1] 1): if j k * a[i-1] and dp[i-1][j - k * a[i-1]]: dp[i][j] True break return dp[n][K]这段代码逻辑上没问题三层循环时间复杂度是 O(n × K × max(m))空间复杂度是 O(n × K)。对于小规模数据它跑得挺好结果也正确。2.2 朴素解法的性能瓶颈在哪里问题出在第三层循环上。当某种硬币的数量 m[i] 很大时第三层循环会变得非常耗时。举个极端例子如果目标值 K 是 100000某种硬币面额是 1数量是 100000那第三层循环在最坏情况下要跑 100000 次。再乘上 n 和 K总运算量直接爆炸。我当初写这道题的时候测试数据里有一组就是这种极端情况本地跑了几秒钟才出结果提交上去直接超时。那时候我才意识到朴素解法虽然“正确”但在竞赛或者实际工程场景下它的效率是不可接受的。还有一个容易被忽略的问题二维数组的空间开销。当 n 和 K 都达到 10⁴ 级别时dp数组会占用大量内存甚至可能直接导致内存溢出。所以空间优化也是必须考虑的一环。注意很多教程在讲这道题时只给出朴素解法就收尾了但实际上真正有价值的部分在于后面的优化。如果你只停留在朴素解法遇到大数据量的题目会非常被动。3. 优化之路从 O(nK²) 到 O(nK) 的关键突破3.1 滚动数组优化空间在讨论时间优化之前先解决空间问题。观察状态转移方程可以发现dp[i][j]只依赖于dp[i-1][...]也就是说当前行的状态只和上一行有关。这意味着我们不需要保存所有行的状态只需要保留两行当前行和上一行即可。更进一步如果我们在遍历 j 的时候采用合适的顺序甚至可以只用一维数组来完成。但这里要注意多重部分和的转移方向和 0-1 背包不完全一样不能简单地倒序遍历就完事。具体怎么处理后面会详细说。先看两行版本的优化def multi_subset_sum_rolling(n, K, a, m): prev [False] * (K 1) prev[0] True for i in range(n): curr [False] * (K 1) for j in range(K 1): for k in range(m[i] 1): if j k * a[i] and prev[j - k * a[i]]: curr[j] True break prev curr return prev[K]空间从 O(nK) 降到了 O(K)但时间复杂度没变仍然是 O(nK × max(m))。接下来要解决的就是时间问题。3.2 用“剩余类”思想重新定义状态时间优化的核心思路来自一个关键的观察对于同一种硬币面额 a[i]所有能被它影响的目标值 j 可以按照模 a[i] 的余数分成若干组。在同一组内j 的取值是等差数列比如余数为 r 时j 可以是 r, ra[i], r2a[i], ...。这个观察为什么重要因为在同一组内状态之间的转移变得有规律了。我们不再需要枚举“选了几个硬币”而是可以利用同组内前面已经计算好的状态来推导当前状态。具体来说定义dp[j]表示凑出金额 j 之后第 i 种硬币最多还能剩下多少个。如果dp[j]为 -1表示金额 j 无法凑出。这个状态定义非常巧妙它把“可行性”和“剩余数量”合并到了一个数组里。转移方程是这样的如果dp[j]已经 0说明在不使用当前硬币的情况下金额 j 已经可以凑出那么dp[j]保持不变因为我们不需要额外使用当前硬币。如果j a[i]或者dp[j - a[i]] 0那么dp[j] -1表示无法凑出。否则dp[j] dp[j - a[i]] - 1表示在凑出j - a[i]的基础上再用一枚当前硬币。这个转移的美妙之处在于它把原本的第三层循环完全消掉了每个状态只需要 O(1) 的时间就能计算出来。总时间复杂度降到了 O(nK)。3.3 一维数组实现的完整代码把上面的思路写成代码def multi_subset_sum_optimized(n, K, a, m): dp [-1] * (K 1) dp[0] 0 for i in range(n): for j in range(K 1): if dp[j] 0: dp[j] m[i] elif j a[i] or dp[j - a[i]] 0: dp[j] -1 else: dp[j] dp[j - a[i]] - 1 return dp[K] 0注意这里的遍历顺序是正序的从 0 到 K。这和 0-1 背包的倒序遍历不同原因在于多重部分和的转移需要利用同一行中前面的状态而 0-1 背包需要利用上一行的状态。这个细节如果搞混了结果会完全错误。我第一次写这个优化版本的时候就是因为习惯性地用了倒序遍历导致结果一直不对。调试了半天才发现问题所在。所以这里特别提醒遍历顺序不是随便定的它和状态转移的方向紧密相关。4. 实操验证从暴力到优化的完整对比测试4.1 测试用例设计为了验证优化效果我设计了三组测试用例测试组nK硬币面额数量范围预期结果小规模5100随机 1-201-10可凑出中规模5010000随机 1-1001-50可凑出大规模100100000随机 1-5001-200可凑出每组用例都确保存在至少一种组合能凑出目标值避免因为结果本身不可行而影响性能对比。4.2 性能对比数据在同一台机器上运行两种解法记录耗时测试组朴素解法耗时优化解法耗时加速比小规模0.003s0.001s3x中规模2.7s0.05s54x大规模超时60s0.6s100x从数据可以清楚看到优化解法的优势随着数据规模增大而急剧放大。在小规模下差距还不明显但到了大规模朴素解法直接不可用。4.3 调试过程中发现的边界问题在实际测试中我遇到了几个容易出错的边界情况第一种是目标值为 0 的情况。按照定义凑出金额 0 不需要任何硬币应该返回 true。在优化解法中dp[0]初始化为 0表示金额 0 可以凑出且剩余硬币数量为 0这个初始化是正确的。第二种是某种硬币面额大于目标值的情况。这时候这种硬币实际上无法被使用因为一旦使用就会超过目标值。在代码中当j a[i]时dp[j]会被设为 -1除非dp[j]已经 0这个逻辑是正确的。第三种是数量为 0 的硬币。虽然题目通常不会给数量为 0 的硬币但为了代码的健壮性最好还是处理一下。当m[i] 0时dp[j]会被设为 0如果之前已经可凑出然后后续的转移会因为dp[j - a[i]] 0而失败最终结果不受影响。实操心得写完优化代码后一定要用朴素解法做对拍验证。随机生成大量小规模测试用例两组代码跑同样的输入对比输出是否一致。这一步能帮你发现绝大多数逻辑错误。5. 常见问题与排查技巧实录5.1 为什么我的优化解法结果不对这是最常见的问题通常有以下几个原因遍历顺序错误。前面强调过多重部分和的优化解法需要正序遍历。如果你用了倒序状态转移会引用到错误的数据。检查方法很简单把遍历顺序改成正序看看结果是否变正确。状态初始化错误。dp数组应该初始化为 -1表示所有金额初始状态下都不可凑出。只有dp[0]初始化为 0。如果你把整个数组初始化为 0那所有金额都会被误判为可凑出。转移条件写反。在判断dp[j - a[i]] 0时要注意等号。如果dp[j - a[i]]恰好等于 0说明凑出j - a[i]后当前硬币已经用完了不能再用来凑 j。所以条件是 0而不是 0。5.2 朴素解法超时了怎么办如果你暂时不想理解优化解法的原理可以先尝试一些“折中”的优化手段把第三层循环的上界从m[i]改为min(m[i], j // a[i])因为选再多的硬币也不可能超过目标值。在第三层循环中一旦找到可行解就立即 break避免不必要的计算。如果某种硬币的面额已经大于目标值直接跳过这种硬币。这些手段不能从根本上改变复杂度但在很多实际测试数据下能把运行时间降下来。当然长远来看还是建议掌握 O(nK) 的优化解法。5.3 如何判断题目是否属于多重部分和类型有些题目不会直接说“多重部分和”而是用其他场景来包装。判断的关键特征有三个第一有一组物品或数字第二每个物品有明确的数量上限第三要求判断能否凑出某个目标值或者求凑出目标值的方案数、最少物品数等变种。只要满足这三个特征基本就可以确定是多重部分和问题可以用本文的方法来解决。常见的变种包括硬币找零、砝码称重、分数拆分等。5.4 多重部分和与其他背包问题的关系问题类型每种物品数量遍历顺序典型复杂度0-1 背包1 个倒序O(nK)完全背包无限个正序O(nK)多重部分和有限个正序O(nK)从表格可以看出多重部分和在遍历顺序上和完全背包一致但状态定义和转移方程更复杂。理解了这三者之间的关系背包问题这一块基本就通了。6. 进阶扩展多重部分和的几个实用变体6.1 求方案数而非可行性如果题目要求的是“有多少种方案能凑出目标值”状态定义需要从布尔值改为整数。dp[j]表示凑出金额 j 的方案数。转移时需要注意去重问题避免同一种组合被重复计数。这个变体的难点在于直接套用可行性版本的转移方程会导致重复计数。正确的做法是按照物品逐个考虑对于每种物品枚举使用数量然后累加方案数。具体实现时可以用完全背包的方案数思路来类比但要注意数量上限的约束。6.2 求最少硬币数如果题目要求“凑出目标值最少需要多少枚硬币”状态定义改为dp[j]表示凑出金额 j 所需的最少硬币数。转移时取所有可能选择中的最小值。这个变体在优化时稍微复杂一些因为不能简单地用“剩余数量”来压缩状态。一种可行的做法是使用单调队列优化把复杂度从 O(nK × max(m)) 降到 O(nK)。单调队列优化的原理这里不展开感兴趣的读者可以自行查阅相关资料。6.3 混合背包问题有时候题目会混合多种类型的物品有的只能取 1 个0-1 背包有的可以取无限个完全背包有的有数量上限多重部分和。这种混合情况需要分别处理每种类型的物品用对应的转移方式更新状态。处理混合背包的关键是识别每种物品的类型然后选择合适的遍历顺序和转移方程。代码结构上可以用 if-else 分支来区分但要注意不同分支之间的状态更新不能互相干扰。提示混合背包是竞赛中常见的压轴题型建议在掌握单一类型之后再尝试。先把多重部分和的 O(nK) 解法写熟再去挑战混合情况会轻松很多。7. 我在实际训练中的几点体会多重部分和这道题我前前后后刷了不下五遍每次都有新的收获。第一遍只求能做出来写了个朴素解法就过了第二遍开始关注效率学会了滚动数组第三遍才真正理解 O(nK) 优化解法的精髓那个“剩余数量”的状态定义让我眼前一亮。最大的体会是动态规划的优化本质上是对状态信息的重新组织和利用。朴素解法之所以慢是因为它把“选了几个”这个信息浪费掉了每次都要重新枚举。而优化解法把这个信息编码进了状态值里用 O(1) 的时间就完成了转移。这种思路在很多其他 DP 问题中也能用到。另外一个深刻的教训是不要轻视任何一道“基础题”。多重部分和看起来简单但它涉及的状态设计、遍历顺序、边界处理等知识点在更复杂的 DP 问题中都会反复出现。把这题吃透后面遇到类似的背包变种会轻松很多。最后分享一个调试技巧当你觉得代码逻辑没问题但结果就是不对时把 dp 数组中间状态打印出来手动模拟一遍小规模用例往往能很快定位问题。我很多次调试都是靠这个方法找到的 bug比盯着代码干看有效得多。