某个国家一共发行了a1, a2, a3, …, ak种不同面额的钞票, 为了方便起见, 假设a1 < a2 < … < ak· 现在手上有n, 请问要如何把n兑换成a1, a2, a3, ……, ak这些钞票,使得所用钞票的量为最少

说明: 先说一个最常见的例子, 如果有1元、5元、10元3种, 而又有107元要兑换, 于是a1=1, a2=5, a3=10, n=107。兑换方式很简单, 用面额最大的去除, 那就是最大面额钞票的张数, 比如说n/a3 = 107/10 = 10,亦即10元的10张; 除过之后就会有余数7, 再用次大面额的钞票去除, 得商数1(7/5 = 1), 余数2, 所以5元的一张; 再把余数用第三大面额去除(2/1)得商数2, 余数0, 于是1元的两张, 但余数为0, 于是就没有剩下来的钱了, 因此最后结果是10元10张, 5元1张, 1元两张。假若n=78, 那就是10元7张, 5元1张, 1元3张, 一般书中就是这样讲的, 不过对1元、5元、10元这个例子而言, 倒也是正确。如果钞票的面额是1元、3元、4元(奇怪的数字,是吧?), 要兑换10元呢? 用上面的方法, 有4元两张(104=2,余2)、1元两张, 一共用了4张钞票。但若用两张3元、1张4元, 也兑出了10元, 却只用了3张钞票.

这个例子说明, 寻常所用的方法固然可以兑换钞票, 但钞票张数却不是最少的; 此外问题是, 请写一个程序, 输入a1,a2…, ak钞票面额, 以及n个欲兑换的钱数, 输出钞票张数最少的兑换方式。

解答见make_change.py