企业官网建设流程全解析

ATM机、多重背包、C++，这三个词摆在一起，老玩家一看就知道是经典题单里那道“取钱”的题目。它把生活中很常见的场景抽象成了一个算法模型：你输入一个想取的金额，ATM里准备了若干种面额的纸币，每种面额都有剩余张数，机器需要在不超过你输入金额的前提下，凑出一笔尽可能接近目标金额的现金。于是问题就变成了“给定货币面额、每种货币数量、金额上限，求能凑出的最大金额”——这不就是教科书式的多重背包吗。

这篇想把这类题目一次讲透。刚接触动态规划的人，第一反应通常是“有多少张就拆成多少张，然后做01背包”，这个方法确实对，但数据一大就容易超时。文章会解释为什么不能用贪心、暴力拆分的问题在哪、二进制优化是怎么把复杂度压下来的，最后给一份可以直接复用的C++代码。不管你是刚开始学背包问题的新手，还是想快速拾起来应付笔试的开发，这套思路都够用。

1. 拆题：ATM取款场景是一个伪装成现实问题的多重背包

1.1 为什么“面额有限量”的组合不能用贪心解决

很多人的第一反应是“ATM取钱不都是先给大面额吗”。现实生活中，ATM确实倾向于先用大钞，因为人民币、美元这类币种的面额体系本身设计得比较规整，大面额基本都能被小面额整除。但在算法题里，题目给的面额组合完全可以是任意正整数，比如面额是7元、5元、2元，这时候贪心就会翻车。

举个具体例子：上限是10元，机器里有7元、5元、2元各若干张。贪心策略是“先拿最大的7元”，剩下3元再拿一张2元，最后拿到9元。但最优解明明是5+5=10元，刚好拿满。为什么贪心错了？因为7、5、2这三者之间没有整除关系，大面额钞票塞进去之后，反而把背包空间挤掉了，凑不出最优值。只要面额之间不是“彼此整除”的货币体系，贪心就不安全。

换句话说，这个问题天然适合动态规划而不是贪心。我们需要把所有可能的组合放进一个状态空间里，最后取最大值。这也正是背包问题擅长处理的事情。

1.2 从01背包、完全背包到多重背包，ATM为什么是多重背包

背包家族里有三个近亲：01背包要求每种物品最多选一次，完全背包允许每种物品无限使用，多重背包则给每种物品加了一个“库存上限”。ATM场景里，每种面额有固定张数，比如面额50的纸币有200张，面额20的有150张。你既要考虑张数限制，又要考虑目标金额上限，这不就是多重背包的典型特征。

很多人会问，直接把它当完全背包行不行？不行。完全背包假设每种纸币无限供应，ATM里显示“余额不足”或者“该面额纸币已取完”的情况就不存在了，模型直接失真。把它当成01背包呢？也可以，前提是你先把每张纸币都拆成独立物品——200张50元就拆出200个体积和价值都是50的物品。这种做法小数据没问题，可一旦面额多、张数大，物品数量会爆炸，后面会专门讲这个问题。

其实只要理解了“张数”就是“物品数量”，“金额上限”就是“背包容量”，这题已经解决一半了。剩下的就是选对优化策略。

2. 三种优化思路：暴力拆分、二进制分组、单调队列

2.1 暴力拆分：最直觉的做法，为什么代价很高

先看最直白的版本：把每种面额按照张数展开，每种面额的一张纸币就当成一个01背包物品。举个例子，面额50元有200张，就生成200个完全相同的物品，每个物品的体积和价值都是50；面额20元有150张，再生成150个物品，以此类推。

这种“拆成01背包”的代码写起来很顺手，三段循环一嵌套就完事，小数据下样例基本一遍过。代价是什么呢？总物品数等于所有面额张数的总和，再乘以背包容量，复杂度是 O(容量 × Σ张数)。一旦遇到某种面额有好几万张，组合数量立刻爆炸。比如容量10万、总张数10万，循环次数就是10的10次方级别，在现代OJ上基本等于全程超时。

所以暴力拆分的定位只有一个：写对拍脚本或者验证边界小数据时用。它不适合当正解，但适合当“基准答案”，用来检查优化版本有没有写错。

2.2 二进制优化：把12张钞票拆成1、2、4、5

二进制优化是多重背包的经典解法，思路非常巧妙。核心思想是：与其把200张50元拆成200个物品，不如把它们打包成若干个“子包”，每个子包包含2的幂次张钞票，再加上一个余数包。这样物品数量就从Σ张数降到了Σlog₂张数。

怎么理解“2的幂次打包”？举个例子，12张50元纸币可以拆成四组：1张、2张、4张、5张。为什么是1、2、4、5？因为1、2、4这三组可以组合出0到7的任意数量，加上5这一组后，又可以覆盖5到12之间的任意数量，最终0到12都能被组合出来。反过来也可以验证：这个拆法不会产生超过12张的组合，因为四组加起来正好是12张。

换个更简单的类比：你要购买任意数量0到12之间的商品，与其让商家一张一张拿，不如提前打包成1、2、4、5四份，你要多少就选相应组合。每份“子包”在01背包里只能选一次，但组合出来的效果等价于可以取任意数量。

用代码实现也不复杂，核心逻辑就是不断从cnt里减掉2的幂，直到剩余不足：

int k = 1; while (cnt >= k) { int w = k * money; // 这个子包的总面额，也是它的“体积” int v = k * money; // 这个子包的价值，ATM问题里价值就是金额 items.push_back({w, v}); cnt -= k; k <<= 1; } if (cnt > 0) { items.push_back({cnt * money, cnt * money}); }

因为每种子包对应一个01背包物品，总物品数从之前的“总张数”变成了“每种面额拆出的组数之和”。对于数量为10万的纸币，几十组就能表示完，复杂度骤降。

2.3 单调队列优化：多重背包的进阶形态

二进制优化已经把复杂度压到 O(cash × Σlog₂张数)，绝大多数ATM题目已经够用。但如果你追求极致，或者数据范围大到二进制都吃力，还可以使用单调队列优化——把多重背包的状态转移看成“对每个余数分组做滑动窗口取最大值”。

这个思路稍复杂一点，核心是固定某个面额后，把背包容量按照对该面额的余数分成若干组，每一组内部用单调队列维护窗口内的最大dp值，从而把每种面额的更新从 O(cash × 张数) 降到 O(cash)。它对写题短平快帮助不大，但能加深对背包问题的理解。

三种做法复杂度对比如下：

实际做题时，多数情况用二进制优化就够了，优先把这个写熟练。

3. 完整C++实现：从状态定义到滚动数组

3.1 状态定义与转移方程

先说状态定义。我们用dp[j]表示“在当前已处理的物品里，能凑出的不超过j元的金额最大值”。换句话说，背包容量是j时，最多能拿到多少钱。因为ATM问题里一张面额为money的纸币，它的“重量”和“价值”都是money，所以转移方程写出来非常规整：

dp[j] = max(dp[j], dp[j - w] + v)

其中w是当前子包的总面额，v也是当前子包的总面额。为什么可以把二维dp压成一维？因为dp[j]只依赖上一轮处理物品时的数据，我们只需要一个一维数组原地更新，只要保证j的遍历顺序是从大到小就可以。

初始化时，全部dp[j]置为0。含义是“不取任何钞票，金额为0”，在“不超过上限”这个条件下永远合法。最后dp[cash]就是题目要求的答案。

3.2 可以直接复用的参考代码

下面是完整代码，已经考虑了二进制拆分、多组数据、滚动数组等核心细节，直接用C++17编译即可：

#include <bits/stdc++.h> using namespace std; struct Item { int cost; // 子包总面额，也是背包体积 int val; // 子包总价值，ATM问题里等于cost }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { int cash, m; cin >> cash >> m; // cash: 目标金额上限，m: 面额种类数 vector<Item> items; for (int i = 0; i < m; ++i) { int money, cnt; cin >> money >> cnt; // 面额和张数，注意输入顺序 // 二进制拆分：把cnt张钞票拆成1、2、4...和剩余部分 int k = 1; while (cnt >= k) { items.push_back({money * k, money * k}); cnt -= k; k <<= 1; } if (cnt > 0) { items.push_back({money * cnt, money * cnt}); } } vector<int> dp(cash + 1, 0); for (const auto& it : items) { // 超过背包容量的子包直接跳过 if (it.cost > cash) continue; // 01背包滚动数组更新，必须逆序遍历 for (int j = cash; j >= it.cost; --j) { dp[j] = max(dp[j], dp[j - it.cost] + it.val); } } cout << dp[cash] << "\n"; } return 0; }

这里有几个细节值得展开。第一个细节是二进制拆分循环里为什么写while (cnt >= k)而不是while (cnt > 0)。因为k是一个接一个翻倍的2的幂，cnt减到比k小的时候，剩余数量就直接作为最后一个子包，不再继续拆，这样能保证每个子包都对应“2的幂次张”或者“剩余张数”。第二个细节是if (it.cost > cash) continue;，这个判断可以避免无意义的循环，尤其当某种面额特别大、超过上限时，直接跳过会减少不少操作。

3.3 复杂度与内存占用估算

实际估算一下：假设有100种面额，每种面额最多10000张，容量上限cash是100000。二进制拆分后，每种面额大约拆出14个子包，总物品数约1400个。01背包的复杂度就是物品种类乘容量，即1400 × 100000 = 1.4亿次内层操作。这个量级在C++里通常一秒钟左右能跑完，大多数题目的时限都能接受。

内存方面，dp数组大小是cash+1个int，即使cash是10万也只有400KB左右，items数组只存拆分后的子包，数量也不大，完全不用担心内存问题。相比之下，如果走暴力拆分路线，总物品数可能达到上百万，dp更新次数直接破亿，还不算生成物品本身的开销，自然容易超时。

4. 实战排坑：四个最容易翻车的细节

4.1 滚动数组的遍历顺序写反，直接变成完全背包

这是最经典的一个坑。用一维数组做01背包时，内层循环必须从cash往小写，也就是逆序遍历。如果写成for (int j = it.cost; j <= cash; ++j)，那dp[j]就可能用到当前这轮已经更新过的dp[j - it.cost]，导致同一个子包被多次选择，相当于把一个“只选一次”的物品变成了“无限用”，代码跑完输出一个偏大的错误答案。

我见过很多人纠结“为什么看起来一模一样，一个AC一个WA”，最后发现就是j++和j--的区别。遇到这种问题，先用简单样例手推一遍dp数组的变化过程，马上就能看出来。

4.2 初始化到底用0还是负无穷

这取决于题目问的是“不超过现金上限的最大金额”还是“刚好等于现金上限的最大金额”。ATM题通常是前者，所以dp数组全初始化为0是安全的，因为“什么都不拿”一定是一个合法方案。dp[0]=0，其他也是0，意思是从0到cash的每个容量都天然存在一个什么都不拿的合法状态。

但如果某一天你把模板搬去解决“恰好凑满某个金额”的问题，那就必须把dp[1]到dp[cash]初始化成负无穷，只保留dp[0]=0。否则状态转移会把“凑不满”的非法状态当成合法状态来更新，导致答案错乱。负无穷一般取-0x3f3f3f3f，这个数大约是负的10亿多，做加法不容易溢出。

4.3 读入顺序和多组数据的边界情况

同一个题目在不同题库里，读入行的顺序经常不一样。有的先给面额再给张数，有的先给张数再给面额。样例数据很少，肉眼很难发现问题，所以最好的办法是对拍。写一个暴力拆分版本的程序作为基准，再写一个二进制优化版本，用随机输入跑一遍，比较输出是否完全一致。不一致就说明读入顺序或者处理逻辑有错。

还有一点容易被忽略：当cash等于0的时候，不能直接return 0，因为后续还有m组纸币信息需要读完。如果提前结束，下一组测试用例的数据就会错位，输出乱七八糟。正确的做法是先正常读完本组所有输入，再判断cash是否为0、输出0。

4.4 从“会写”到“写得快”的调试技巧

我自己的习惯是这样：遇到多重背包，先不要急着上优化，先在草稿纸上写一遍最朴素的暴力三重循环，确认状态定义和转移逻辑是对的。这步只花两分钟，但能避免后面以错为基础优化半天。暴力确认对之后再替换成二进制拆分，最后随机对拍一次。

对拍脚本也不需要多复杂：生成一组随机面额和张数，跑两个程序，逐行比较输出。只要输出对上了，基本就能放心提交。这个方法比盯着代码看到底是哪里写错要高效得多。

另外建议把“读入一组数据、拆分、背包更新、输出”这几步用注释分隔开，代码结构清晰了，查错时也更容易定位。二进制拆分的部分还可以单独抽成一个函数，主流程只负责调用，逼自己养成写函数而不是写一大坨的习惯。

5. 顺带聊聊这类模型能带到哪里去

5.1 从ATM取款到预算规划的建模套路

其实多重背包模型的应用场景非常多。比如购物预算问题：手里有一张金额固定的购物卡，商城里每种商品根据库存限购一定数量，目标是花掉尽可能多的卡内金额。再比如优惠券抵扣：手上有若干张不同面额的抵扣券，每种券有张数限制，要选出一组抵扣券让最终实付金额尽可能低。这些通通可以抽象成“有上限、有库存、价值最大化”的模型。

一旦把问题抽象到这个层面，做题就不再是“背模板”，而是“套模型”。判断一个题是不是多重背包，就看两个特征：是不是有总量上限，是不是每个物品有数量限制。如果只有上限没有数量限制，那是完全背包；如果每样最多一个，那是01背包；如果数量有限制，就是多重背包，数量一大就上二进制优化。

5.2 我自己常用的“先暴力后优化”工作流

说了这么多理论，最后分享一点个人经验。我以前遇到多重背包题，总想着一步到位直接写二进制优化，结果有时样例过了，交上去却错，排查半天才发现是思路本身出了问题。后来我调整了顺序：先花几分钟写一个最朴素的暴力拆分版本，确保它输出正确，然后在这个基础上加二进制优化，再用随机对拍确认两者结果一致。这套流程看起来多花了五分钟，实际上帮我省掉了很多无谓的WA时间。

还有一个小技巧值得记住：在二进制拆分的时候，拆出来的子包中如果存在两个子包体积相同，可以提前合并，但ATM题里money乘k的结构天然保证每个子包都是唯一的，不需要额外处理。真正需要小心的反而是bit移位写成k <<= 1而不是k *= 2时，k没用long long导致极端数据下溢出。平时多留个心眼，遇到超大面额时把相关变量改成long long，一劳永逸。

这套“识别模型、选对优化、暴力对拍验证”的思路，不光能解决ATM场景，拿到任何背包类问题面前都是通用的。写代码之前先想清楚三道题：状态是什么、容量是什么、转移怎么走。想明白了，剩下的事情就是按模板敲键盘而已。