动态规划法（二）找零钱问题

ゝ一纸荒年。 2022-05-24 13:52 184阅读 0赞

本次博客尝试以storyline的方式来写作，如有不足之处，还请多多包涵~~

## 问题的诞生 ##

我们故事的主人公叫做丁丁，他是一个十几岁的小男孩，机智聪颖，是某某杂货店的小学徒。在他生活的国度里，只流通面额为1,3,4的硬币。复杂这家店的店长，叫做老王，是个勤奋实干的中年人，每天都要跟钱打交道。  
  有一天，他心血来潮，叫住正在摆放货物的丁丁，对他说道：“丁丁，你不是学过计算机方面的算法吗？我这里正好有个问题，不知你能解答不？”  
  一听到算法，丁丁的眼睛里闪出光芒，这正是自己的兴趣所在。于是，他连忙凑到柜台，好奇地问题：“什么问题啊？”  
  老王也不多说废话，他知道丁丁的聪慧之处，直接了当地说道：“你看啊，每次顾客们买完东西付款后，我们都要找零给他们，我们这边所有的硬币（1,3,4）都是充足的，我想知道一共有多少种找零方式？比如说找零为4的话，就有4=1+1+1+1=3+1=1+3=4共4种方式。”  
  乍听到这个问题，丁丁有点蒙圈了，因为4的情况是简单的，但是随着找零的面额增加，数量的变化就没有什么规律了。他示意掌柜出去走走，掌柜也欣然同意。

## 递归？动态规划？ ##

此时我们的主人公正坐在湖边静静地思考，脑海中涌现出各种各样的计算机算法。突然，递归法进入了他的视野，对，就是递归法！他认真地整理着思路：

1.  考虑面额为n的情况，假设n=x1\+x2\+...\+xm  n = x 1 + x 2 + . . . + x m .那么，只需考虑最后一个数xm=1,3,4  x m = 1 , 3 , 4 的情形。当xm=1,3,4  x m = 1 , 3 , 4 ，剩下的面额为n−1,n−3,n−4.  n − 1 , n − 3 , n − 4. 
2.  假设面额为n的找零方式为f(n)  f ( n ) ，则f(n)=f(n−1)\+f(n−3)\+f(n−4)  f ( n ) = f ( n − 1 ) + f ( n − 3 ) + f ( n − 4 ) ，这样就能按照递归法来做了。
3.  最后，只需要确定初值即可，f(0)=f(1)=f(2)=1,f(3)=2.  f ( 0 ) = f ( 1 ) = f ( 2 ) = 1 , f ( 3 ) = 2.

问题似乎到这就解决了，因为有了这个递推式，那么，直接定义一个函数就能解决问题了。等等，他想起昨天看到的博客“[动态规划法（一）从斐波那契数列谈起][Link 1]”。对了，对于递推式，可以用动态规划法解决啊。于是，他顺手写了一下Python代码：

import time
    
    # calculate the number of ways of integer n can be write the sum of 1,3,4
    def sum_part_dp(n):
        if n <= 2:
            return 1
        elif n == 3:
            return 2
    
        first = 1
        second = 1
        third = 1
        fourth = 2
    
        # repeat n-3 times
        for _ in range(n-3):
            answer = first + second + fourth
            first = second
            second = third
            third = fourth
            fourth = answer
    
        return fourth
    
    n = 40
    t1 = time.time()
    s = sum_part_dp(n)
    t2 = time.time()
    print('面额:%s,方法数:%s,耗时：%s'%(n, s, t2-t1))

他迅速地敲完了以上代码，运行，得到结果：

面额:40,方法数:119814916,耗时：0.0

Bingo,搞定！他满怀欣喜地将这个结果告诉了掌柜老王，老王看了，也禁不住点点头，心想：计算机算法真有用啊！

## 再一次的挑战 ##

可是老王也是一个有想法的人，他看着丁丁这么干脆利落地解决了这个问题，决心再出一个难题考考他。他清了清喉咙，对丁丁说道：“刚才的问题解答得很棒啊，值得表扬 ！但是现在呢，我这又有个麻烦事。每次找零，怎样找零才能使得找零的硬币数最少呢？”  
  丁丁笑而不语，他点了点头，就抱着他的电脑离开了。老王望着他离去的背影，心想：这个问题要是能解决，以后找零也就省了不少麻烦。不知这次丁丁要用多长时间？  
  有了上个问题的积累，丁丁对于解决这个问题满怀信心。还是跟刚才的解答方法一样，先用递归，假设面额为n  n 的找零所用最少硬币数为f(n) f ( n )，则f(n)=min\{ f(n−1)\+1,f(n−3)\+1,f(n−4)\+1\}.  f ( n ) = m i n \{ f ( n − 1 ) + 1 , f ( n − 3 ) + 1 , f ( n − 4 ) + 1 \} . 采用自底向上的动态规划法，记录每个子问题的解，避免重复求解，这样就能得到f(n)  f ( n ) 的值了。那么，怎样才能记录每个子问题的解呢？用Python中的字典啊！这样，硬币数量是得到了，可是具体的找零方式呢？不难，只要用一个变量记录刚才表达式中是取f(n−1)  f ( n − 1 ) 还是f(n−3)  f ( n − 3 ) 还是f(n−4)  f ( n − 4 ) ，对应面额为1,3,4,再递归地求解下去即可。  
  他写下了Python代码：

# 找零钱问题
    # 找零钱字典，key为面额,value为最小硬币数
    change_dict = {}
    
    # 动态规划法解决问题
    # 时间复杂度：多项式时间
    # 只求解最小的硬币数量
    def rec_change(M, coins):
        change_dict[0] = 0
        s = 0
    
        for money in range(1, M+1):
            num_of_coins = float('inf')
    
            for coin in coins:
                if money >= coin:
                    # 记录每次所用的硬币数量
                    if change_dict[money-coin]+1 < num_of_coins:
                        num_of_coins = change_dict[money-coin]+1
                        s = coin #记录每次找零的面额
    
            change_dict[money] = num_of_coins
        return change_dict[M],s
    
    # 求出具体的找零方式
    # 用path变量记录每次找零的面额
    def method(M, coins):
        print('Total denomination is %d.'%M)
        nums, path = rec_change(M, coins)
        print('The smallest number of coins is %d.'%nums)
        print('%s'%path, end='')
    
        while M-path > 0:
            M -= path
            nums, path = rec_change(M, coins)
            print(' -> %s'%path, end='')
        print()
    
    coins = (1, 3, 4)
    method(50, coins)

运行结果如下：

Total denomination is 50.
    The smallest number of coins is 13.
    3 -> 3 -> 4 -> 4 -> 4 -> 4 -> 4 -> 4 -> 4 -> 4 -> 4 -> 4 -> 4

几分钟后，当掌柜老王看到这个结果后，惊讶得目瞪口呆！在这家小小的杂货店里，也许藏着一位计算机天才，他这样想到。  
  而我们的主人公呢？此时，他已经向着斜阳，走在县城的小道上，踌躇满志，准备着去外面的世界看一看~~

***注意：***本人现已开通两个微信公众号： 用Python做数学（微信号为：python\_math）以及轻松学会Python爬虫（微信号为：easy\_web\_scrape）， 欢迎大家关注哦~~

[Link 1]: https://blog.csdn.net/jclian91/article/details/80475836