10.4.2　货币选择问题

三酷猫去购物中心购买价格为2555元的手机，他手里有100元20张、50元20张、20元3张、10元1张、5元12张，怎么支付所需要钱的数量最少？

这是一个典型的贪心算法求解问题，先用最大面值100元支付最多张数的钱、再用50元支付最多张数的钱，依次类推，直至满足支付，把分解的所有面值的钱相加，就得到最少钱的张数。

代码文件：10_4_2_SelectMoney.py

(https://www.daowen.com)

上述代码执行结果如下：

注意

本算法正确解答的前提，对不同面值的钱按面值进行从大到小的排序。无序或升序排序的钱记录，都会导致算法结果不正确。