ATM机的吞钱和吐钱表面上是硬件问题背后其实是一道算法题。你在ATM上输入取款金额比如8300元后台要在毫秒级内决定从当前钞箱库存里选哪些券别、各出几张才能凑出正好8300元。少了不行多了更不行。这个恰好凑出指定金额的问题落到数据结构里就是经典的多重背包问题用C实现时还要考虑库存约束、吐钞张数上限、无解兜底这些业务细节。这篇文章我会从头梳理ATM配钞与多重背包的关系给出完整可跑的C实现并分享我在实际项目中踩过的坑。如果你正在做银行渠道系统、ATM终端应用或者单纯想搞懂背包问题的工程化写法这篇文章应该能直接帮你省掉不少试错时间。1. ATM配钞为什么天然就是多重背包问题1.1 从一次取款请求看约束条件ATM配钞的场景可以这样描述系统里有若干种面额每种面额对应一个钞箱钞箱里有固定张数的库存。客户申请取款金额S我们需要从每个钞箱中取出一定张数使得取出的纸币总面额恰好等于S并且单种面额的出钞数量不能超过该钞箱当前库存。这个描述里的每一个字都对应多重背包的一个要素面额是物品价值库存张数是物品数量上限恰好等于S是背包容量约束。更确切地说这是一个多重背包的可行性/最优性问题——不是要最大化价值而是要判断能否把背包容量恰好填满。实际项目中约束条件还会更多。例如某设备单笔吐钞不能超过30张否则出钞口会卡纸某券别钞箱故障时该面额库存虽在但不能使用后台风控可能要求单笔取款券别数不超过3种。这些约束都可以在DP建模阶段通过调整状态定义来实现我会在后面详细展开。1.2 多重背包和完全背包、01背包的本质区别同样是把东西往背包里放三种模型的区别只在每个物品能用几次。01背包中每个物品最多取1次对应的是某张特定编号的纸币是否使用。完全背包中每种物品可取无限次对应的是纸币无限量供应——这在ATM场景里不成立因为钞箱库存是有限且变动的。多重背包正好卡在中间每种物品有明确的可用次数上限。为什么这个区别重要因为很多人在刚接到配钞需求时会下意识写一个两层循环外层遍历金额j从0到S内层遍历第i种面额可以取多少张k然后对每种面额把满足jkv[i]S的状态全部更新一遍。这个朴素写法的复杂度是O(NS*C)其中N是面额种类数C是单种面额的最大库存张数。面额种类少时问题不大但一旦库存张数到几千、目标金额到几十万三层循环就会慢到无法接受。所以工程化实现必须做优化而最经典的优化就是二进制拆分它能把每种物品取0到cnt张的需求等价转换成O(log cnt)个01背包物品。1.3 配钞算法里业务规则的优先级抛开纯算法视角真实业务里的配钞规则往往存在优先级。第一个优先级是能不能配出即可行性第二个优先级是配出的方案是否合规比如不能超出单笔张数上限第三个优先级才是方案是否最优而最优的定义依据业务场景而变化。有的银行希望优先使用大面额让出钞张数尽可能少这样可以降低清点成本和设备卡纸概率。有的业务场景恰好相反希望尽量使用小面额给后续找零留出大额库存。还有的场景要求各券别出钞数量尽量均衡避免某个钞箱消耗过快。这些规则会直接影响DP的目标函数。如果要求张数最少状态dp[j]可以定义为凑出金额j所需的最小张数如果要求券别均衡就得引入加权系数把不同券别的消耗代价定义成不同数值。先想清楚业务你到底要什么再写代码这是我做这个项目最大的体会。2. 状态设计与二进制优化从三层循环到数百倍提速2.1 一维DP数组到底存什么朴素想法是定义dp[j]true/false表示金额j能否被凑出。这个bool数组实现最简单初始化dp[0]true然后对于每种面额v、每种可取张数k执行dp[jk*v]|dp[j]。可用但有两个问题。第一bool数组无法回溯方案。就算最后dp[S]true你也不知道该从哪个钞箱取几张。业务上光知道能配没有任何意义ATM还要真正吐钞必须输出各券别的张数明细。第二bool数组做不了最优判断。多组可行方案并存时无法按张数、券别偏好筛选。所以我在实际项目中用了另一种定义dp[j]表示凑出金额j所需的最小纸币张数初始为无穷大dp[0]0。每加入一组可用的纸币组合就尝试用dp[j-w]k去更新dp[j]。转移方程直观回溯路径也方便。如果你不追求最小张数只想找到任意一组可行方案也可以把dp[j]定义成布尔值并额外维护path[j]数组记录转移来源两种套路各有适用场景。2.2 二进制拆分是如何把张数降成组数的二进制拆分的原理很简单对于任意正整数cnt我们可以把它拆成若干个二进制块每个块的大小是1、2、4、8……最后一个块取剩余值。这样拆分出来的块数大约是log2(cnt)1个并且这些块可以组合表示0到cnt之间的任意整数张数。举个具体例子。假设某券别面额是50元库存13张。朴素做法等价于枚举0,1,2,...,13共14种取法。二进制拆分后把13拆成1、2、4、6四个块含义分别是取50元x1张取50元x2张取50元x4张取50元x6张。你可能觉得奇怪6不是2的幂没错最后一个块是余数直接把剩余部分打包。为什么这4个块能表示0到13之间所有的取法1、2、4三个块能组合出0到7的所有整数加上最后一个6能组合出6到13的所有整数两段拼起来正好覆盖0到13。这样原来需要做14次枚举的券别现在只需要当4个新物品来处理耗时降了一个数量级。2.3 一维滚动数组为什么要倒序遍历拆分完成后每个块变成独立的01背包物品。01背包用一维数组优化时内层循环必须倒序。这个细节很多人知道但没想明白。正序更新的问题在于dp[j]可能在同一次外层循环中被提前更新然后又被当作旧状态去更新更大的j导致同一个二进制块被使用多次。倒序时j从大到小遍历dp[j-w]还没有被本轮更新影响它永远来自上一轮的结果等价于每个物品最多用一次。这个最多用一次是01背包的语义也正是我们对每个二进制块的要求。如果你在这块写成正序程序不会报错但结果会变成该块可用无限次相当于把多重背包错当成了完全背包配钞结果会虚增库存这在真实业务里是严重事故。3. C实现从数据结构到完整配钞流程3.1 数据结构与输入约定我先定义券别与库存的结构以及二进制拆分后的分组结构。#include bits/stdc.h using namespace std; struct BillType { int value; // 面额单位元 int count; // 当前钞箱库存张数 }; struct SplitGroup { int value; // 该组等价总面额 原始面额 * 组内张数 int k; // 该组包含的原始面额张数 };这里有一个很容易混淆的点SplitGroup.value不是原始面额而是原始面额x组内张数的乘积。比如拆分出k4张50元的块这个块的value就是200。在做背包转移时我们把它当成一个总面额为200的虚拟物品选中它等价于从50元钞箱里取4张。3.2 二进制拆分函数的实现拆分函数接收原始面额和库存张数返回一组虚拟物品。vectorSplitGroup splitBills(int value, int count) { vectorSplitGroup groups; int k 1; while (count 0) { int take min(k, count); groups.push_back({value * take, take}); count - take; k 1; } return groups; }循环过程要仔细看第一次k1取1张第二次k2取2张第三次k4取4张直到剩余数量不足当前k时直接把剩余值全部打包。以库存13张50元为例group输出为组序号take值虚拟总面额包含原始张数11501221002342004463006确认一下这组块能表示的张数范围前3块能组合0到7第4块固定6整体覆盖0到13没问题。3.3 核心DP转移目标是最小张数把所有券别拆分后的虚拟物品收集到一个大列表里然后跑01背包。dp[j]表示凑出j元需要的最少纸币张数这里张数要理解成原始纸币张数不是虚拟组数所以更新时需要加上SplitGroup.k。vectorSplitGroup allGroups; for (const auto bill : bills) { if (bill.count 0) continue; // 零库存直接跳过 auto g splitBills(bill.value, bill.count); allGroups.insert(allGroups.end(), g.begin(), g.end()); } int target 8300; const int INF 1e9; vectorint dp(target 1, INF); vectorint lastGroup(target 1, -1); // 记录转移到该金额的虚拟组下标 dp[0] 0; for (int gi 0; gi (int)allGroups.size(); gi) { int w allGroups[gi].value; int k allGroups[gi].k; for (int j target; j w; --j) { if (dp[j - w] k dp[j]) { dp[j] dp[j - w] k; lastGroup[j] gi; } } }注意这里的更新代价是k而不是1。因为选中的这个虚拟组实际是从钞箱里拿出来的k张真钞。dp最终值代表凑出目标金额所需的总张数回溯时也要按k来累加。3.4 路径回溯从金额反推每个券别出几张很多人写完转移就停在这一步结果测试时发现dp有值但根本不知道钞箱该怎么出钞。回溯函数其实非常简单从target开始不断根据lastGroup信息回退到上一个金额同时记录该虚拟组对应的原始券别张数。vectorint restoreSolution(int target, const vectorBillType bills, const vectorSplitGroup groups, const vectorint lastGroup) { vectorint out(bills.size(), 0); int cur target; while (cur 0) { int gi lastGroup[cur]; if (gi -1) return {}; // 无解 // 根据虚拟组包含的张数累加到对应券别 out[0] 0; // 示意占位实际需通过映射关系定位 cur - groups[gi].value; } return out; }实际编码时拆分产生的虚拟组必须记录它来自哪个原始券别。可以把SplitGroup里增加一个billIndex字段回溯时直接out[billIndex] groups[gi].k。上面代码里我特意省略了这个字段以突出重点完整实现时千万别漏。回溯完成后一定要再做一次校验把out里每个券别的张数乘以对应面额求和结果必须严格等于target。任何一步的错误都会在最终金额上暴露这个校验在联调阶段价值极大。4. 实测与边界无解兜底、张数上限、大金额性能4.1 无解时怎么办兜底策略不是一句提示失败DP跑完后如果dp[target]仍然是INF说明在当前库存组合下无法精确配出目标金额。真实ATM系统里直接返回无法取款是体验极差的方案一般会有层层兜底逻辑。我在项目里见过并被要求实现的常见兜底顺序是检测目标金额与当前可用面额最大公约数的关系如果不可整除无论如何都无解直接提示客户修改金额如果可整除但库存仍不足系统会尝试把取款金额向上取整到某个允许的档位比如客户取8300元配不出但8300元通常是100的倍数拆分档可能被调整成8400元并提示客户确认最后再考虑移交柜面处理或走人工加钞。这些逻辑属于业务规则不必全部塞进DP但至少要在DP无解时有一套明确出口。4.2 张数上限和券别数量约束如何把硬件限制塞进状态ATM设备通常对单笔出钞总张数有限制。以某常见设备为例上限约30张超过这个数吐钞口会卡顿甚至故障。如果dp目标是最小纸币张数天然会优先选择大面额通常不容易超限但这不是必然的。比如客户取6700元可用面额只有50元和20元且50元库存不足时最小张数方案也可能超过30张。要处理这个约束可以在DP数组里额外记录张数并在转移时检查dp[j-w]k必须小于等于设备上限否则不更新。这样超出硬件能力的状态直接不进入候选集。券别数量约束同理。有些业务规则要求一次取款最多使用3种券别那状态就要从一维升到二维dp[j][c]表示凑出金额j且使用的券别种类数为c是否可行。代价是时间和空间上升但只要面额种类本身不多完全可接受。纯工程角度还可以在回溯后检查券别种类再做判定但这就失去了DP对可行性的预筛选能力。4.3 大金额与int64别让金额溢出毁掉一次配钞ATM单笔取款金额通常有限额几万元已经是上限但算法测试时我习惯把目标金额放大到几十万甚至百万来压性能。这时有两个隐患。第一个是int溢出。在计算虚拟组总面额value*take时take可能比较大value也可能上百乘积很容易超过int范围。稳妥做法是用long long保存所有金额相关变量尤其在一开始就把target和value转成long long。第二个是DP数组内存。target到50万时vector dp(500001)大约是2MB内存完全可接受但如果target过千万内存增长到40MB仍可运行但真实场景一般不会出现。复杂度层面所有券别拆分后的虚拟组总数m约为各券别log2(count)之和。面额种类通常不超过10种单钞箱库存最多几千张m大致在几十到一百之间DP核心循环为O(m*target)。目标金额几万元时这个量级大约是几十万次迭代C跑起来是微秒到毫秒级别完全满足实时配钞要求。4.4 贪心算法为什么在这里不靠谱很多人第一反应是优先出大面额不够再用小面额补这是贪心思路。对绝大多数正常流通的面额体系比如100、50、20、10贪心往往能凑出来因为50能整除10020整除不了50这就是问题所在。举一个思想实验假设可用面额是6元、4元、3元库存不限目标金额13元。贪心先拿两张6元剩下1元无法处理判定失败。但最优解是643正好13。虽然ATM实际券别不是这种奇葩组合但当某个钞箱故障、可用券别被禁用时剩余面额之间可能失去整除关系贪心失败的概率就不再为零。多重背包DP不依赖任何面额之间的整除性质它纯粹基于状态转移穷举所有可行组合。这也是我坚持用DP而不是贪心的根本原因。5. 生产环境落地时容易被忽略的几个坑5.1 二进制拆分组的先后顺序会影响最小张数吗我在开发过程中一度怀疑同样库存13张50元拆成1、2、4、6的先后顺序不同DP转移结果是否不同结论是不影响最终能否凑出因为二进制拆分表示的数字集合是确定的0..cnt。但会影响回溯输出方案。由于虚拟组被当作不同物品不同的遍历顺序会导致决策路径不同好在dp数组记录的是最小张数最终不管走哪条路径张数最优值是全局确定的。不过如果你在回溯时依赖最后一次更新的状态那么同金额多种最优方案之间路径选择会受虚拟组顺序影响。项目里如果对券别组合有偏好可以调整拆分组的顺序或者干脆在定义dp时加入券别偏好权重。我在代码实现里选择把大面额的拆分结果放在前面这样回溯天然优先大面额组客户拿到手的方案更符合直觉。5.2 库存为0的面额拆分函数的隐藏陷阱拆分函数如果收到count0我的实现里会直接返回空组所以调用方最好先判断库存大于0。但还有一种隐蔽情况钞箱里明明有库存但该钞箱故障被标记为禁用。此时库存数量不能参与配钞。我踩过的坑是在联调阶段遗漏了禁用状态DP跑出来的方案用到了故障钞箱导致测试设备吐钞失败。解决方式是进入DP前把所有不可用券别的count强制置0而不是单独维护一套是否可用的bool数组。这样能保证DP逻辑只有一条数据来源避免两套数据不一致。5.3 目标金额与最小面额的关系提前判定的价值如果所有可用面额的最大公约数是g而目标金额S不能被g整除那么无论怎么组合都无解。这个判断可以用几行代码完成在DP之前执行能避免无意义的全量搜索。我做个实际测试面额包括100、50、20库存足够目标金额是8310元。三者最大公约数是108310能被10整除不能所以直接判定无解。这时如果客户请求取8310元系统可以立刻提示无法支持该金额而不是白跑一遍DP后失败。另外需要注意只有当所有可用面额都参与求gcd。某个面额库存为零时不能参与计算否则会被0干扰结果这也是我在实现里坚持先清理库存再求gcd的原因。5.4 回归测试用四组边界数据验证代码正确性配钞功能上线前我建议至少准备四组测试数据。第一组目标金额恰好等于某券别单张面额比如100元面额库存充足时取100元期望结果是一张100元。这一组验证基础路径。第二组目标金额等于所有库存总和期望结果是把所有纸纱全部取出且不多不少这一组验证库存上限约束。第三组目标金额为1元但可用面额最小为5元期望结果是无解。第四组目标金额很大比如把所有券别库存都翻10倍后验证程序能在几百毫秒内给出结果而不是超时。每组测试都打印回溯后的明细并自动重新求和校验。我在项目里把这套校验写成了单元测试之后每次改动算法都能快速回归省了很多事。6. 一个小优化用bitset做纯可行性预判如果业务上先不关心最优方案只想快速判断目标金额S是否有解可以用bitset进一步加速。C标准库里的std::bitset支持移位和按位或一次能处理很多位的转移。bitset1000000 bs; bs[0] 1; for (auto g : allGroups) { bs | (bs g.value); } bool can bs[target];这个写法直接把用这个虚拟组更新所有可行金额变成一次位运算大量场景下比vector循环快很多。但它只能回答可行性不能回溯出具体出钞方案。我通常把它作为预筛手段先用bitset判断有解再跑完整DP回溯。两套逻辑共用同一个allGroups数据不会产生方案不一致的问题。从工程角度来看这个优化在目标金额五万以下时收益不大vector 版本已经足够快但如果目标金额达到几十万、面额种类又多bitset的提速效果就很明显值得保留。7. 从ATM到通用场景这个方案还能用在哪些地方多重背包的建模方式并不局限于ATM。我在另一个项目里处理过促销礼品的自动组合凑单需求客户的账户积分换礼每种礼品有不同积分值和库存需要凑出指定积分场景和ATM配钞几乎一模一样直接复用这套DP和回溯逻辑只改了字段名。还可以用在多规格商品的包装组合上仓库里同种商品有多种规格包装每种规格库存有限需要凑出某个总件数的订单。甚至游戏里的道具合成、资源调配只要满足种类有限、每类数量有限、目标总量精确这三个特征都能套用。这也从侧面说明搞懂多重背包不是单纯应付面试题它是很多真实业务系统里非常务实的基础能力。你把这个模型想透了以后遇到给一堆有限资源精确凑总量的需求根本不需要找外援自己就能设计出可靠方案。回到ATM配钞本身我想强调的还是那句话算法只是第一步把边界条件、业务规则、回溯校验想清楚才算真正把问题解决。代码可以抄思路和对坑的敏感度只能靠一次一次踩坑踩出来。