- 正在填写
- 被读取
- 答案
硬币找零问题
给定几种硬币,怎样用尽可能少的硬币刚好付清一个金额?一共又有多少种付法?先取最大硬币的贪心做法对真实货币有效,但对某些硬币组合会失败。而由较小金额逐步算出每个金额的表格,总能得到正确答案。 点按托盘里的硬币,把它放到柜台上;点按柜台上的硬币,把它拿回来。计量条会朝目标金额逐渐填满:用尽可能少的硬币正好凑出这个金额。“最少硬币”显示最佳答案,“贪心”显示总是取不超过剩余金额的最大硬币会得到什么,但结果不一定最少。在面板中修改硬币面值(以分为单位)和金额。“表格”视图展示动态规划如何找到最少硬币,或如何数出凑成该金额的方法数:按“播放”观看表格逐步填满,或按“单步”和“后退”一次走一步,拖动步骤滑块可跳到任意位置。每种硬币都可以使用任意多次。选中表格时,方向键逐步前进或后退,空格键播放或暂停,Home 和 End 跳到开头和结尾。
它是如何运作的
- 点按托盘里的硬币,正好凑出这个金额,看进度条按美分逐渐填满。
- 尽量少用硬币,然后按“最少硬币”或“贪心”进行比较。
- 打开“表格”视图并按播放,观看每个单元格读取它所依赖的较小金额。
最少硬币
金额 0 不需要硬币。对每个更大的金额,尝试每枚不比它大的硬币:用掉这枚硬币后剩下的是一个更小的金额,已经在表中,所以再加一枚硬币就得到一个候选。最小的候选填入格子,给出它的那枚硬币记在下面一行。表格填满后,从目标金额倒推读出硬币:取它的最后一枚硬币,转到剩下的金额,重复直到 0。
方法数
为了计算组合而不是排列,表格每行加入一种硬币。一个格子统计用到本行为止的硬币凑出其金额的方法数:不用最新硬币的方法,即上方的格子,加上至少用一次最新硬币的方法,即同一行中向左数硬币面值那么多列的格子。由于硬币按固定顺序加入,1 + 2 和 2 + 1 是同一种方法,只算一次。
常见问题
为什么贪心方法会失败?
贪心总是取不超过剩余金额的最大硬币,而且从不回头重新考虑。硬币为 1、3、4,金额为 6 时,它先取 4,再取 1 和 1:共三枚,而两枚 3 就够了。对于欧元或美元这样的硬币体系,贪心恰好是最优的;这样的体系称为规范硬币系统。
计算方法数和计算排列数有什么区别?
方法数把 1 + 2 和 2 + 1 看作同一种组合;排列数则分别计算。本应用通过逐行加入硬币来计算方法数。若要计算排列数,则改为依次遍历每个金额,并对每个金额尝试每种硬币。
硬币找零算法有多快?
两张表所需的步数都是硬币种类数乘以金额。金额在几千以内时很快,但金额可能是一个巨大的数,所以按位数来衡量时,这个问题一般是 NP 困难的。
如果某个金额凑不出来怎么办?
它的格子保持为 ∞,例如硬币为 2 和 5 时的金额 1 和 3。在“方法数”模式中,它的计数就是 0。
会向任何地方发送数据吗?
不会。所有计算都在你的浏览器中完成,你最近的设置保存在本浏览器的本地存储中。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器