颜林林的个人网站

关于人民币面额与找零的问题

2009-07-02 10:18

我们太容易习以为常,不知道应该算是好事还是坏事。

最近看一些算法相关的东西,才发现连经常用到的人民币面额的设计都是很有讲究的。比如,用不同面额的组合来分别表示1~9元:

1元 = 1元
2元 = 2元
3元 = 2元 + 1元
4元 = 2元 + 2元
5元 = 5元
6元 = 5元 + 1元
7元 = 5元 + 2元
8元 = 5元 + 2元 + 1元
9元 = 5元 + 2元 + 2元

上面列举的组合都是使用钱币数最少的(比如8元若全用2元,则需要4张)。

仔细分析,才发现这里暗含了一个玄机:要想在找零时使用最少的钱币数(假设每种面额的钱币都足够多),则每次都选取不大于所要表示的金额的最大面额的钱币。比如表示8元:首先选取不大于8元的最大面额,即5元;再选取不大于剩下金额(3元)的最大面额,即2元;最后再选择1元,则得到5+2+1的组合。这是一种贪婪算法,而我们的货币面额体系则保证了该贪婪算法始终能得到最优解。所以,也难怪银行不发行其他的面额(如4元等),否则:8元=4元+4元,这种组合才是所用的钱币数最少的,而这时用前面的算法就得不到最优解了。