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

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

最近看一些算法相关的东西，才发现连经常用到的人民币面额的设计都是很有讲究的。比如，用不同面额的组合来分别表示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元，这种组合才是所用的钱币数最少的，而这时用前面的算法就得不到最优解了。