面试算法问题
来源：1-1 欢迎大家来到算法与数据结构的世界
慕沐201348
2020-08-12 23:45:23
老师好,之前在面试的时候遇到了一个算法题,没有什么思路,希望老师有时间的时候能帮我解答一下
小明有1元硬币a个，2元硬币b个，5元硬币c个，现在小明想把这些硬币分给其他人，要求：
每种硬币，最多拿1个；
每个人拿到的钱数不同；
问，小明最多分给多少个人硬币？
输入，a.b.c三个整数；
输出 分给最多的人数；
写回答
1回答
-
liuyubobobo
2020-08-13
每种硬币最多只能使用 1 个，那其实三种硬币组成的不同的钱数只能有 7 种组合，对应 001，010，011，100，101，110，111。
用回溯法遍历一遍所有这 7 种钱数的组合，看每一中组合能不能被 a，b，c 覆盖。如果能，记录这个组合分给了多少人。取最多的。一共 7 种钱数，回溯 2^7 不过 128 种可能。
这是一个典型的回溯问题。对回溯算法的学习，建议看我的《玩转算法面试》：https://coding.imooc.com/class/82.html
继续加油！：）
0
相似问题