这题我第一次见是在刷OJ练习题时碰到的翁恺老师的C语言练习题里也有类似的题。题目本身不复杂给定一个工资金额用100、50、20、10、5、2、1元这些人民币面额去凑要求用的钞票总张数最少。说白了这就是个“找零钱”的模型只不过把“买东西找零”换成了“发工资备钞”的场景。但这道题是理解贪心算法最好的入门题之一因为它看起来简单背后却藏着“贪心选择性质”这个核心概念。什么时候贪心能用、什么时候不能答案全在这道题里。本文就从头到尾带你拆一遍从问题建模、C语言代码实现到边界处理、动态规划对照验证再到我实际踩过的坑一次说透。适合刚学完C语言数组和循环、准备进阶算法的同学也适合正在准备面试笔试题的人。看完你不仅能AC这道题还能顺手搞懂贪心算法的最核心判断标准。1. 问题本质与贪心思路拆解1.1 从“发工资”到“找零模型”先把这个实际场景抽象成数学问题。假设财务要给员工发一笔工资比如376元手头有100元、50元、20元、10元、5元、2元、1元这7种面额的人民币每种面额都足够多问最少需要多少张。这句话翻译成算法语言就是给定一个目标整数S和一个面额集合D {100, 50, 20, 10, 5, 2, 1}从D中选取若干张钞票使得面值总和恰好等于S并且钞票数量最少。这里有个关键前提每个面额的数量是无限的否则问题会复杂很多。现实中财务去银行取钱默认各种面额都能取到这个前提是合理的。很多同学一上来就想着用多重循环暴力枚举那确实能做但效率很低。如果只有7种面额暴力枚举勉强能跑但面额种类增加到几十种、目标金额到几十万循环嵌套就直接爆炸了。所以我们需要一个更聪明的算法。1.2 为什么人民币体系下贪心是对的贪心策略很简单粗暴每次都用当前能用的最大面额去凑直到凑完为止。拿376元举例先取100元能取3张还剩76元再取50元能取1张还剩26元再取20元能取1张还剩6元再取5元能取1张还剩1元最后取1元1张结束。合计31111 7张。直觉上这个结果已经很少了但你怎么确认它一定是最少的万一某个局部选择大面额反而导致后面被迫用很多小额钞票呢这个担心在人民币体系下不会发生原因在于人民币面额之间存在“整倍数关系”100 2×5050 2×20 1020 2×1010 2×55 2×2 12 2×1。每一张大面额都可以被若干张小面额严格替代而且替代的张数都大于等于2。所以当你用一张100元去替换两张50元时张数只会减少不会增加同理用大面额总是划算的。这就是贪心算法成立的关键性质在算法里叫“贪心选择性质”。1.3 一句话说清贪心算法的核心逻辑贪心算法的思想可以浓缩成一句话在每一步决策时都做出当前看起来最优的选择并且一旦做出就不回头。对于这道题每一步的最优选择就是“尽量用最大的面额”。因为大面额对“减少张数”的贡献是确定的不会因为后面的选择而改变。不过要注意贪心不是万能的。如果面额集合改成{1, 3, 4}目标金额为6贪心会先取4再取1和1共3张而最优解是33只要2张。所以只有具备贪心选择性质的系统才能用贪心算法。人民币1、2、5、10这种体系正好具备这也是题目默认用人民币的原因。2. 数据结构与函数设计2.1 面额表与计数表C语言实现的第一步是把这个7种面额存起来。我建议用一个一维数组来存面额然后开一个平行数组来存对应面额用了多少张。int denominations[7] {100, 50, 20, 10, 5, 2, 1}; int count[7] {0};这里的关键是面额数组必须从大到小排列因为贪心策略要求每次从最大面额开始尝试。如果你把数组写成{1, 2, 5, 10, 20, 50, 100}程序逻辑上也能写对但要么得倒序遍历要么得额外排序纯粹给自己添麻烦。为什么用数组而不是7个独立变量因为数组天然支持“循环遍历”你可以用同一个循环结构处理任意多的面额以后面额种类变了只需要改数组不需要改逻辑。这是工程上很常见的“数据驱动”思想把变化的部分放进数据而不是放进代码。2.2 接口设计把核心逻辑封装成函数很多初学者喜欢把所有代码全塞进main函数里这样写OJ题能过但不利于以后复用也不利于排查问题。我习惯把核心计算封装成一个独立函数这样主流程看起来非常清爽。/** * 计算最少需要的人民币张数 * * param salary 工资金额元 * param denoms 面额数组从大到小 * param n 面额种类数 * param count 输出参数每种面额的张数调用方传入长度为 n 的数组 * return 最少总张数如果无法凑出则返回 -1 */ int calcMinNotes(int salary, const int *denoms, int n, int *count) { int remaining salary; int total 0; for (int i 0; i n; i) { count[i] remaining / denoms[i]; remaining % denoms[i]; total count[i]; } return (remaining 0) ? total : -1; }两个设计细节值得单独说一下。第一用remaining保存剩余金额。每次用remaining / denoms[i]算出当前面额能用多少张再用remaining % denoms[i]更新剩余金额。除法和取模配合使用是这类问题最核心的操作。第二返回-1表示无法凑出。虽然人民币体系下1元面额保底一定能凑出任意正整数金额但把函数写成通用形式会更好。以后如果面额集合不含1就会出现剩余金额不为0的情况这时返回-1就能暴露问题。2.3 主流程代码完整可运行版本下面给出一个完整可编译运行的版本包含输入校验和输出明细。#include stdio.h #define KIND_COUNT 7 int calcMinNotes(int salary, const int *denoms, int n, int *count) { int remaining salary; int total 0; for (int i 0; i n; i) { count[i] remaining / denoms[i]; remaining % denoms[i]; total count[i]; } return (remaining 0) ? total : -1; } int main(void) { int denominations[KIND_COUNT] {100, 50, 20, 10, 5, 2, 1}; int count[KIND_COUNT] {0}; int salary; printf(请输入工资金额正整数单位元); if (scanf(%d, salary) ! 1 || salary 0) { printf(输入格式有误请重新运行程序。\n); return 1; } int minNotes calcMinNotes(salary, denominations, KIND_COUNT, count); if (minNotes 0) { printf(无法用现有面额凑出该金额。\n); return 1; } printf(工资 %d 元最少需要 %d 张人民币明细如下\n, salary, minNotes); for (int i 0; i KIND_COUNT; i) { if (count[i] 0) { printf(%5d 元%d 张\n, denominations[i], count[i]); } } return 0; }运行结果示例假设输入376请输入工资金额正整数单位元376 工资 376 元最少需要 7 张人民币明细如下 100 元3 张 50 元1 张 20 元1 张 5 元1 张 1 元1 张注意输出里我用%5d做了对齐这只是为了让控制台输出更好看不影响逻辑。如果你不需要明细只关心总张数可以把输出部分简化成一行的printf。3. 边界条件与鲁棒性处理3.1 输入合法性负数、零、非数字很多C语言新手写这道题测试用例总是“正常输入”一上线就被各种诡异输入搞崩。我强烈建议你在读入时就直接拦截非法输入。上面代码里我用了一句if (scanf(%d, salary) ! 1 || salary 0)一次做了两件事scanf返回成功读取的变量个数如果不是1说明用户输入的不是有效的十进制整数比如输入了abc即使读到了数字如果salary是0或负数也没有意义因为工资不可能是负数。这里有个细节||是短路运算符。如果scanf返回值不是1后面的salary 0根本不会执行也就不会出现“读取失败但变量被使用”的问题。这个顺序不能写反。3.2 金额类型选择int够不够用人民币工资场景下int类型取值范围是-2147483648到2147483647也就是约21亿绝大多数公司发工资都用不到这个上限。所以直接用int是够的。但如果你把题目扩展一下变成“计算一笔巨款需要多少张人民币”金额可能超过int范围那就得用long long。C语言里long long至少64位取值上限约922京基本不用担心。另外提醒一个常见的坑不要在金额计算中使用浮点数。如果你用double存金额再除以面额很可能会出现精度问题。例如100.0 - 99.9这种浮点运算结果不是0.1而是一个很接近0.1的数。这类金融场景里一切金额都应该用整数表示以“元”或“分”为单位避免浮点误差。3.3 无法凑出金额的情况与函数容错尽管人民币包含1元面额理论上任何正整数金额都能凑出来但如果你把这个函数复用到其他场景比如面额集合变成{3, 5}目标金额为7就凑不出来了。此时remaining最终会剩下1函数返回-1。写代码时保留这个容错分支是很重要的工程习惯。你永远不会知道将来会不会复用这个函数。而且保留-1返回值也方便你做单元测试和调试。如果你把“1元面额”去掉问题会变成一个经典的“硬币找零”问题贪心不适用需要用动态规划。这就是下一节要讲的验证环节。4. 正确性验证贪心与动态规划对照4.1 手算测试用例写完代码第一件事不是提交而是自己手算几组数据验证。我常用的几组测试用例输入金额贪心结果手算验证11张1元175元1张 2元1张共2张21010元1张199502020522共6张6100100元1张1376100×3 50×1 20×1 5×1 1×1共7张7用100元、50元、20元、10元、5元、2元、1元这个体系任何金额都能凑出来而且结果都很直观。手算验证时我建议你从大到小模拟一遍贪心过程别只看最终结果不然逻辑错了也不容易发现。4.2 动态规划对照实现为了确认贪心算法在人民币体系下确实正确最稳妥的办法是拿动态规划对照验证。动态规划的核心思路是dp[i]表示凑出金额i所需的最少张数初始dp[0]0其他为无穷大然后对每个面额逐个更新。#include stdio.h #include string.h #define MAX_AMOUNT 100000 #define INF 1000000000 int dp[MAX_AMOUNT 1]; int min(int a, int b) { return a b ? a : b; } int dpMinNotes(int salary, const int *denoms, int n) { if (salary MAX_AMOUNT) { return -1; // dp数组不够大实际应用需扩大 } for (int i 1; i salary; i) { dp[i] INF; } dp[0] 0; for (int i 1; i salary; i) { for (int j 0; j n; j) { if (i denoms[j]) { dp[i] min(dp[i], dp[i - denoms[j]] 1); } } } return dp[salary] INF ? -1 : dp[salary]; }动态规划的时间复杂度是O(salary × n)如果salary是376、n是7计算量很小但如果salary是100000就变成了70万次循环虽然还能接受但明显比贪心的O(n)慢得多。我实际做对照时会写一个测试脚本遍历1到10000的所有金额分别用calcMinNotes和dpMinNotes计算结果断言两者一致。这样能非常确定地证明在这个面额体系下贪心就是最优解。4.3 我踩过的坑数组大小和状态初始化动态规划对照写法有一个很典型的坑dp数组大小。如果你不开够MAX_AMOUNT 1一旦salary超过数组长度就会数组越界程序直接段错误或者出现随机结果。另一个坑是初始化。dp数组如果不把非0位置初始化为INFmin比较时会出现全0导致结果全是0张。这个错误特别隐蔽因为很多时候程序能跑而且不报错但结果完全不对。我在最初学动态规划时就曾在dp初始化上栽过跟头。后来养成了一个习惯凡是定义数组后马上用memset或者for循环初始化绝不依赖编译器默认清零。这个习惯在嵌入式开发和OJ刷题中都非常有用。5. 典型报错与避坑速查5.1 编译阶段常见问题报错/警告信息原因解决办法implicit declaration of function忘记在main前声明或定义函数把calcMinNotes函数体放到main之前或用函数声明expected ; after expression少写分号或花括号不匹配检查上一行是否漏了分号unused variable count定义了但没用上要么使用它要么删掉comparison of integer expressions of different signedness有符号数和无符号数比较统一用int或者把数组长度变量也改成int编译错误其实是最友好的因为编译器会明确告诉你在哪一行、什么类型的问题。真正头疼的是能编译通过但结果不对的情况。5.2 逻辑错误排查思路剩余金额没有更新。如果循环里只算count[i] remaining / denoms[i]却忘写remaining % denoms[i]每一轮计算用的都是原始金额结果会非常大。遇到结果异常大先检查有没有“状态更新”这一步。面额数组顺序不对。如果数组是升序但循环从下标0开始程序会用最小面额优先结果张数会很多。检查数组是否为降序。count数组未清零。如果count数组是局部变量且没有初始化里面是随机值累加结果会错。定义int count[7] {0};是最稳妥的。scanf格式与输入不匹配。用户输入376元这种带单位的字符串scanf(%d, salary)会读不到整数返回0。交互式程序里要提示用户输入纯数字。5.3 我个人的避坑心得说实话这题的代码量很小坑也不算多但有一类问题很值得单独提醒就是输出格式。很多OJ题目对输出要求非常严格比如要求“输出最少张数”结果你多打了一行“请输入...”就直接Wrong Answer。平时写练习代码可以随意但提交OJ时务必把调试用的printf删干净。另外我建议你顺手在代码里加一个总张数的累计变量不要每次都重新从count数组里加总。虽然多一次循环也不费事但直接在原循环里累加代码更简洁也少一次出错机会。最后一点写完函数后先单元测试再整体跑。我在工程实践中一直习惯把核心算法封装成纯函数输入输出都不依赖全局变量这样测试起来特别方便。你可以写一个临时main函数循环测1000组数据就像第4节说的那样一次就能验证多种情况。6. 从这道题延伸出去的算法学习路径6.1 变体练习输出找零方案并逆序显示非常推荐的一个变体是不仅要输出总张数还要输出每种面额用了多少张而且要求按面额从小到大输出。这时你只需要调整返回值结构或者把面额数组倒序处理。// 倒序遍历面额数组输出 for (int i KIND_COUNT - 1; i 0; i--) { if (count[i] 0) { printf(%5d 元%d 张\n, denominations[i], count[i]); } }这种变体能帮你巩固数组遍历方式也能用上指针和数组下标之间的灵活转换正好复习C语言基础语法。6.2 贪心不适用场景从“人民币”到“任意面额”前文提到的{1, 3, 4}面额集合、目标金额6就是一个经典的反例。贪心算法拿4然后1和1共3张但最优解是33共2张。为什么会有这种差异因为面额之间不再是“整倍数替代关系”。4不能用3加1替换出更少的张数但也不能用4本身带来任何优势。很多教材会用这个例子说明贪心算法必须证明贪心选择性质而不是靠直觉。要做到“证明”一般用贪心选择性质最优子结构两个标准。对于人民币体系可以用“大面额次数不少于任意最优解中该面额次数”的交换论证来证明这里不展开因为对初学者来说先会用动态规划做对照验证更实际。6.3 后续练习方向从贪心到动态规划如果你已经被这道题勾起了兴趣可以按这个顺序继续练习用贪心实现“找零钱”输出明细本题把面额改成{1, 3, 4}用动态规划实现并对比贪心结果解决“完全背包”问题跟硬币找零本质相同学习回溯算法解决带数量限制的找零问题。我在实际教学和带实习生的过程中发现能把这道题讲明白的人对贪心和动态规划的分界线就基本清晰了。很多人会误以为贪心是动态规划的子集其实它们是两种不同的策略贪心不考虑未来动态规划以空间换时间记录所有子状态。两者各有各的适用场景边界就在于“局部最优是否能推出全局最优”。我对你的建议是先把这道题C语言实现跑通再用动态规划对照跑一遍最后自己试着修改面额集合观察结果变化。这个过程走完你对贪心的理解就不再是背结论而是真的吃透了。
