零钱兑换方法问题

收藏到CSDN网摘


ACM经常有换零钱的问题,例如将一元的纸币兑换成5角,2角,1角,5分,2分和1分的硬币,有多少种兑换方法?根据纸币面额和硬币种类,问题的复杂程度不同(例如欧拉工程就有一道类似题目,兑换英国的钱币),最简单的办法是暴力求解,可用多层循环求解,一般循环层数可以比硬币种类少1,因为最后一个1分的硬币可以用前面求和<=(小于等于)面额来化简.如果小于面额,说明有多个1分币,如果恰好等于面额,则没有1分币.不过如果硬币种类特别多,循环的方法将不是一个理想的方法(当然,只要硬币给定,循环的代码总是能写出来的,时间足够,计算机也的确可以运行得出结果).

这类问题经过变换可以变为"一个大数如何写成几个小数之和的形式"的问题,此类问题的通解应当是通过分析来递归求解.

UPDATE: 加入了一个参数,可以避免重复求解子问题(算是动态规划还是备忘录?)

def getChange(amount, changes, method):
    if (amount,tuple(changes)) in method:
        return method[(amount,tuple(changes))]
    elif amount==0:
        return 1
    elif amount<0 or len(changes)==0:
        return 0
    else:
        a = getChange(amount-changes[0],changes,method)
        b = getChange(amount,changes[1:],method)
        method[(amount-changes[0],tuple(changes))] = a
        method[(amount,tuple(changes[1:]))] = b
        return a+b

N = 10
print getChange(N,range(1,N+1),{})

================================================= 分析:(为简单将3元兑换为1元与2元) 其过程可以看做: 总方法 = 不含第一种钱币的方法 + 肯定含第一种钱币的方法.然后对于2种情况,可分别递归解决.作图如下:

左边是不含第一种钱币的方法,右边是必定包含第一种钱币的方法.不含第一种钱币,因此钱币种类的list长度就减少1;必定包含第一种钱币,面额就要减少第一种钱币的数量.如此递归下去,对于每一个左子树,list长度减小,对于每一个右子树,面额减小.递归出口就是:面额为0,当面额为0时,就找到了一种兑换方法.当钱币list长度为空或者面额为负数表示当前拆分无法兑换. python实现的零钱兑换递归解法(欧拉工程31题)

#! /usr/bin/env python

def getChange(amount, changes):
##    print 'solve', amount, changes
    if amount==0:
        return 1
    elif amount<0 or len(changes)==0:
        return 0
    else:
        return getChange(amount-changes[0],changes)+getChange(amount,changes[1:])
        
    

def main():
    amount = 200
    changes = [1,2,5,10,20,50,100,200]
    print getChange(amount, changes)
        
if __name__=='__main__':
    main()