【python算法书】硬币找零问题？

题目：窝窝要去商店买棒棒糖，她怎么样才能用最少个数的硬币买到心仪的糖果呢？

分析：找零问题的贪心算法求解。为了满足我们要用最少的硬币数量支付指定额度的金额这一要求，每次使用可选的最大金额付款符合一贯“贪心”的习惯。根据常识，在当前阶段，使用可用的最大面值金额支付剩余待找零额度，可以使后面的待找零额度尽量小，从而更有可能促使之后支付需要的硬币数量尽量少。

code:

def findO(par, sum):

    # 从面值最大的元素开始遍历

    i = len(par) - 1

    while i >= 0:

        if sum >= par[i]:

            n = int(sum // par[i])  # 用该币值的个数

            change = n * par[i]  # 扣掉该币值使用的总数

            sum = float("%.6f" % (sum - change))  # 剩余的钱

            print("用了%d个%1.2f元硬币"%(n, par[i]))

        i -= 1

if __name__ == "__main__":

    par = [0.05, 0.1, 0.2, 0.5, 1.0, 2.0]  # 存储每种硬币面值，从小到大

    sum = 5.65

    findO(par, sum)