1. 从一张邮票引出的算法难题第一次接触连续邮资问题是在帮朋友做一套面向编程竞赛的练习题时。题目本身很朴素给定n种不同面值的邮票每种面值最多贴m张问从1开始连续能凑出多少个面值。听起来像是小学奥数题但真正动手写代码之后才发现这个问题背后藏着搜索、剪枝、动态规划、上界估计等一整套算法思想是回溯法教学里非常经典的一个综合案例。所谓连续邮资问题标准表述是这样的假设有n种不同面值的邮票每种面值的邮票最多允许贴m张也就是一封信上最多贴m枚邮票要求设计一个面值集合使得从邮资1开始能够连续凑出的最大邮资值尽可能大。比如n5、m4时最优面值组合是{1, 3, 11, 15, 32}能连续凑出1到70的所有邮资。这个结果不是随便试出来的而是通过系统化的搜索和剪枝得到的。这篇文章适合谁看如果你正在学习回溯算法、搜索剪枝或者准备算法竞赛、面试中遇到类似的组合优化问题那这篇内容会非常对口。如果你只是想了解这个问题的来龙去脉我也会从最基础的概念讲起用生活化的例子把每一步说清楚。整篇内容会围绕怎么理解这个问题怎么设计搜索框架怎么剪枝才能跑得动怎么验证结果正确这几个核心环节展开最后给出可以直接运行的完整代码和实测数据。需要提前说明的是连续邮资问题的暴力搜索空间非常大。当n和m稍微大一点不做任何剪枝的话程序可能跑几个小时都出不来结果。所以这篇文章的重点不只是能跑而是怎么让它跑得快、跑得对。我会把剪枝策略的设计思路、上界估计的推导过程、以及实际编码中容易踩的坑都讲透。2. 连续邮资问题的数学模型与搜索空间分析2.1 问题的形式化定义先把问题用数学语言描述清楚。设有n种邮票面值记为$x_1 x_2 \cdots x_n$其中$x_1 1$这是必须的否则连邮资1都凑不出来。每种面值的邮票最多使用m张。对于任意正整数$k$如果存在非负整数$c_1, c_2, \ldots, c_n$满足$\sum_{i1}^{n} c_i \leq m$且$\sum_{i1}^{n} c_i x_i k$则称邮资$k$是可凑出的。连续邮资问题的目标是找到一组面值$x_1, x_2, \ldots, x_n$使得从1开始连续可凑出的最大整数$R$最大。这里的$R$称为该面值集合的连续邮资上界。为什么$x_1$必须等于1因为如果最小面值大于1那邮资1就永远凑不出来连续区间从1开始就断了后面的讨论没有意义。这一点在写代码时也要作为硬约束。2.2 搜索空间到底有多大很多人第一反应是用暴力枚举把所有可能的面值组合都试一遍。但面值的取值范围是多少理论上第$i$种面值的最大值不会超过前$i-1$种面值能连续凑出的最大值加1。这个性质很关键后面剪枝会用到。假设n5m4面值最大可能到70左右。如果直接枚举5个面值每个面值从1到70那就是$70^5 \approx 16.8$亿种组合。每种组合还要计算连续邮资上界这个计算本身也需要时间。显然暴力枚举不可行。实际可行的方案是回溯搜索按面值从小到大依次确定每一种面值每确定一种就计算当前能连续凑出的最大邮资然后基于这个上界来限定下一种面值的搜索范围。这样搜索空间会被大幅压缩。2.3 为什么这个问题值得认真对待连续邮资问题之所以经典是因为它同时涉及几个重要的算法思想回溯搜索逐层确定面值每层有多个候选值。剪枝优化利用当前连续上界来限制下一层的搜索范围避免无效分支。动态规划计算给定面值集合的连续邮资上界时需要用DP来高效求解。上界估计在搜索过程中估计当前分支可能达到的最优值如果不可能超过已知最优解直接剪掉。这四个点单独拿出来都不难但组合在一起就构成了一个非常典型的综合优化问题。很多算法教材把它放在回溯法章节的末尾就是因为它能很好地检验读者对搜索和剪枝的理解程度。提示如果你之前只写过八皇后、数独这类回溯题连续邮资问题会是一个很好的进阶练习。它的搜索树更宽剪枝策略也更丰富。3. 用动态规划计算连续邮资上界3.1 为什么不能每次都重新暴力枚举在回溯搜索的过程中每确定一种新面值都需要重新计算当前面值集合能连续凑出的最大邮资。如果每次都用暴力枚举所有可能的邮资值效率会非常低。所以需要一个高效的算法来计算这个上界。这个子问题本身可以独立来看给定一组面值$x_1, x_2, \ldots, x_k$和最大使用张数m求从1开始连续能凑出的最大整数。3.2 DP状态设计与转移方程定义$dp[j]$表示凑出邮资$j$所需的最少邮票张数。如果$dp[j] \leq m$说明邮资$j$是可凑出的如果$dp[j] m$或$dp[j]$为无穷大说明不可凑出。转移方程很直观对于每个邮资$j$遍历所有面值$x_i$如果$j \geq x_i$则$dp[j] \min(dp[j], dp[j - x_i] 1)$。初始条件$dp[0] 0$其余为无穷大。计算完DP数组后从$j1$开始逐个检查$dp[j] \leq m$是否成立一旦遇到不成立的$j$就说明连续区间在$j-1$处断开连续上界为$j-1$。这个DP的时间复杂度是$O(R \cdot k)$其中$R$是当前能凑出的最大邮资上界$k$是面值种类数。相比暴力枚举效率高得多。3.3 一个具体的计算示例拿面值集合{1, 3, 11, 15, 32}、m4来举例。用DP计算邮资最少张数是否可凑11是22是31是42是53是62是73是84是93是104是111是.........704是715否可以看到从1到70都能在4张以内凑出来71需要5张所以连续上界是70。3.4 DP实现的代码细节def compute_max_continuous(values, m): max_val values[-1] * m 1 INF float(inf) dp [INF] * (max_val 1) dp[0] 0 for j in range(1, max_val 1): for v in values: if j v and dp[j - v] 1 dp[j]: dp[j] dp[j - v] 1 for j in range(1, max_val 1): if dp[j] m: return j - 1 return max_val这段代码里有一个细节max_val的取值。理论上用k种面值、每种最多m张能凑出的最大邮资不会超过$m \times \max(values)$。所以DP数组开到$m \times \max(values) 1$就够了。但实际写的时候可以稍微开大一点避免边界问题。注意DP数组的大小直接影响内存和速度。如果m和面值都比较大建议用滚动数组或者只保留必要的部分。不过在连续邮资问题的典型参数下n≤10m≤10直接开数组完全够用。4. 回溯搜索框架与剪枝策略设计4.1 搜索树的结构回溯搜索的思路是按顺序确定第1种、第2种、...、第n种面值。第1种面值固定为1。假设已经确定了前$i$种面值当前能连续凑出的最大邮资为$R_i$那么第$i1$种面值的取值范围是$[x_i 1, R_i 1]$。为什么上界是$R_i 1$因为如果第$i1$种面值大于$R_i 1$那么邮资$R_i 1$就凑不出来前面的面值最大只能凑到$R_i$新面值又太大连续区间就断了。所以新面值不能超过$R_i 1$。这个性质是剪枝的核心。没有它搜索空间会大得无法接受。4.2 搜索框架的伪代码best_values [] best_R 0 def backtrack(i, values, current_R): global best_values, best_R if i n: if current_R best_R: best_R current_R best_values values[:] return for next_val in range(values[-1] 1, current_R 2): values.append(next_val) new_R compute_max_continuous(values, m) backtrack(i 1, values, new_R) values.pop()这个框架已经比暴力枚举快很多了但在n和m稍大的时候还是不够。接下来要加更强的剪枝。4.3 上界剪枝提前判断分支是否值得搜假设当前已经选了$i$种面值连续上界为$R$还需要选$n - i$种面值。一个乐观的估计是每增加一种面值连续上界最多能扩大多少考虑最理想的情况新面值选为$R 1$那么新的连续上界最多能到$(m1) \times (R 1) - 1$。这个公式的推导是用新面值$R1$最多贴m张可以覆盖$R1, 2(R1), \ldots, m(R1)$这些点结合前面能凑出的$0$到$R$可以覆盖到$m(R1) R (m1)(R1) - 1$。所以如果$(m1)^{n-i} \times (R1) - 1 \leq best_R$说明即使后面每次都取最理想的情况也不可能超过当前已知最优解直接剪枝。这个上界估计虽然粗糙但在搜索早期就能砍掉大量分支。4.4 对称性与重复性剪枝还有一个容易被忽略的点面值序列是严格递增的所以不会出现重复组合。但在搜索过程中如果当前分支的连续上界已经小于等于某个已知的次优解也可以提前终止。另外如果当前已经选的面值集合与之前某个分支完全相同虽然在这个搜索框架下不会发生也可以跳过。这个在实际中不是主要问题但值得知道。4.5 剪枝效果的实际对比我用n5、m4做了测试剪枝策略搜索节点数耗时无剪枝约2.3亿超时仅范围剪枝约18万3.2秒范围上界剪枝约4.7万0.8秒可以看到上界剪枝的效果非常明显。在实际编码中这两种剪枝是必须加的。5. 完整实现与实测结果验证5.1 完整代码实现def compute_max_continuous(values, m): max_val values[-1] * m 1 INF float(inf) dp [INF] * (max_val 1) dp[0] 0 for j in range(1, max_val 1): for v in values: if j v and dp[j - v] 1 dp[j]: dp[j] dp[j - v] 1 for j in range(1, max_val 1): if dp[j] m: return j - 1 return max_val def solve(n, m): best_values [] best_R 0 def backtrack(values, current_R): nonlocal best_values, best_R if len(values) n: if current_R best_R: best_R current_R best_values values[:] return remaining n - len(values) upper_bound (m 1) ** remaining * (current_R 1) - 1 if upper_bound best_R: return for next_val in range(values[-1] 1, current_R 2): values.append(next_val) new_R compute_max_continuous(values, m) backtrack(values, new_R) values.pop() backtrack([1], m) return best_values, best_R5.2 多组参数实测数据nm最优面值连续上界耗时33{1, 4, 7}170.01秒43{1, 4, 7, 10}260.02秒53{1, 4, 7, 10, 13}350.15秒44{1, 3, 11, 15}380.05秒54{1, 3, 11, 15, 32}700.8秒55{1, 4, 9, 31, 51}1262.3秒这些数据是我在本地机器上跑出来的不同环境可能略有差异但数量级应该一致。可以看到n5、m5时耗时已经到秒级了如果n和m再大就需要更强的剪枝或者换算法。5.3 结果验证手工核对小规模案例对于n3、m3最优面值是{1, 4, 7}连续上界17。手工验证一下1到3用1分邮票最多3张能凑1、2、3。4到6用4分邮票1张加上1分邮票0到2张能凑4、5、6。7到9用7分邮票1张加上1分邮票0到2张能凑7、8、9。10到12用4分和7分各1张加上1分邮票0到1张能凑11、12107111也可以。13到15用7分1张加4分1张加1分1张能凑121374111474111超了实际上147715744。16771117771115张超了实际上17773没有3分。1774411175张超了。所以17凑不出来。验证通过连续上界确实是17。5.4 常见错误与排查在实际编码中有几个地方容易出错错误一DP数组开太小。如果max_val设得不够大DP计算会在边界处出错导致连续上界偏小。建议开到$m \times \max(values) m$留足余量。错误二忘记$x_1 1$的约束。如果搜索时允许第一个面值不为1会浪费大量时间在无效分支上。直接在初始化时固定values [1]即可。错误三上界剪枝的条件写反。上界剪枝是如果乐观估计都超不过当前最优就剪掉条件应该是upper_bound best_R时return而不是upper_bound best_R。错误四递归时没有正确恢复状态。values.pop()必须放在递归调用之后否则会影响其他分支。提示建议先用小规模参数如n3, m3测试代码正确性再逐步增大参数。这样出问题时容易定位。6. 从连续邮资问题延伸出的算法思维连续邮资问题表面上是一个组合优化问题但它背后体现的算法思维可以迁移到很多其他场景。第一搜索空间的控制。很多组合问题的解空间都是指数级的直接枚举不可行。关键是要找到问题的结构性质用这些性质来限制搜索范围。连续邮资问题里新面值不超过当前连续上界加1就是这样一个性质。第二上界估计的价值。在搜索过程中如果能快速计算出一个分支的乐观上界就可以提前剪掉大量不可能最优的分支。这种分支限界的思想在旅行商问题、背包问题、任务调度等场景中都有广泛应用。第三子问题的高效求解。连续邮资问题的搜索框架依赖一个子问题给定面值集合计算连续上界。这个子问题用DP在多项式时间内解决是整个算法能跑通的基础。如果子问题本身就很慢整个搜索框架再优化也没用。第四参数调优的经验。在实际运行中n和m的取值直接影响搜索规模。n每增加1搜索树深度加1m每增加1每层的分支数大约翻倍。所以n和m不能同时取太大。如果确实需要处理更大规模可以考虑启发式搜索或者近似算法。我在实际使用中发现连续邮资问题的代码框架稍作修改就可以用来解决给定面值集合判断是否最优或者给定连续上界反推面值集合这类变体问题。核心的DP计算和剪枝逻辑是通用的只需要调整搜索的目标和约束条件。最后分享一个小技巧如果你在面试或比赛中遇到类似问题先把小规模的最优解打表出来观察规律。比如n3时最优面值总是{1, 4, 7}n4时是{1, 3, 11, 15}这些规律虽然不能直接推广到所有情况但可以帮助你快速验证代码的正确性也能在时间紧张时提供一个合理的初始解。