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, r+a[i], r+2a[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 测试用例设计

为了验证优化效果，我设计了三组测试用例：

每组用例都确保存在至少一种组合能凑出目标值，避免因为结果本身不可行而影响性能对比。

4.2 性能对比数据

在同一台机器上运行两种解法，记录耗时：

从数据可以清楚看到，优化解法的优势随着数据规模增大而急剧放大。在小规模下差距还不明显，但到了大规模，朴素解法直接不可用。

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 多重部分和与其他背包问题的关系

从表格可以看出，多重部分和在遍历顺序上和完全背包一致，但状态定义和转移方程更复杂。理解了这三者之间的关系，背包问题这一块基本就通了。

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，比盯着代码干看有效得多。