27、数据结构与算法Python:找零兑换问题的递归解法

找零兑换问题:递归解法

我们来找一种肯定能找到最优解的方法

贪心策略是否有效依赖于具体的硬币体系

首先是确定基本结束条件, 兑换硬币这个问题最简单直接的情况就是, 需要兑换的找零, 其面值正好等于某种硬币

如找零25分,答案就是1个硬币!
*

其次是减小问题的规模, 我们要对每种硬币尝试1次, 例如美元硬币体系:

找零减去1分(penny)后,求兑换硬币最少数量(递归调用自身);
找零减去5分(nikel)后,求兑换硬币最少数量
找零减去10分(dime)后,求兑换硬币最少数量
找零减去25分(quarter)后,求兑换硬币最少数量
上述4项中选择最小的一个。
*

找零兑换问题:递归解法代码

def recMC(coinValueList, change):
    minCoins = change
    if change in coinValueList:
        return 1
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC(coinValueList, change-i)
            if numCoins < minCoins:
                minCoins = numCoins
    return minCoins

print(recMC([1, 5, 10, 25], 63))

递归解法虽然能解决问题, 但其最大的问题是: 极! 其! 低! 效!

对63分的兑换硬币问题,需要进行67,716,925次递归调用!在我这台笔记本电脑上花费了40秒时间得到解:6个硬币
*

找零兑换问题:递归解法分析

以26分兑换硬币为例, 看看递归调用过程(377次递归的一小部分)

我们发现一个重大秘密,就是重复计算太多!例如找零15分的,出现了3次!而它最终解决还要52次递归调用很明显,这个算法致命缺点是重复计算
*

找零兑换问题:递归解法改进

对这个递归解法进行改进的关键就在于消除重复计算

我们可以用一个表将计算过的中间结果保存起来,在计算之前查表看看是否已经计算过

这个算法的中间结果就是部分找零的最优解, 在递归调用过程中已经得到的最优解被记录下来

在递归调用之前,先查找表中是否已有部分找零的最优解如果有, 直接返回最优解而不进行递归调用,如果没有,才进行递归调用

找零兑换问题:递归解法改进代码

def recMC(coinValueList, change, knownResults):
    minCoins = change
    # 递归基本结束条件
    if change in coinValueList:
    	# 记录最优解
        knownResults[change] = 1
        return 1
    elif knownResults[change] > 0:
    	# 查表成功,直接用最优解
        return knownResults[change]
    else:
        for i in [c for c in coinValueList if c <= change]:
            numCoins = 1 + recMC(coinValueList, change-i, knownResults)
            if numCoins < minCoins:
                minCoins = numCoins
                # 找到最优解,记录到表中
                knownResults[change] = minCoins
    return minCoins

print(recMC([1, 5, 10, 25], 63, [0]*64))

改进后的解法, 极大减少了递归调用次数

对63分兑换硬币问题,仅仅需要221次递归调用是改进前的三十万分之一,瞬间返回!
*

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: