问题描述

假设在某国存在[1,x1,x2,x3,...,xn]多种货币，该国的自动贩卖机在找零时要遵循一个原则——“找零的总张数最少”。那么，该如何编写程序，帮助自动贩卖机自动找零呢？

问题分析

解决这一问题的最直接思路是穷举法。假设需要找零Y元，那么就通过所有的小于Y的货币，列举出找零的所有方案，进而比较哪个总张数最少。这种思路需要在计算中蕴含有大量的重复，时间复杂度极大。
类似问题的一个有效解法是使用动态规划的思想来处理。

求解找零所需要最少货币数

以面值为1，5，10，25的货币为例：

解决这一问题的关键在于，利用类似的等式，不断缩小问题的规模。当问题缩小为“需要多少张货币来找0元”时，问题的答案显然是0。
我们需要额外做的就是创建一个列表，用以保存比要计算的找零需求更小的需求。

   

    

     

      

     
     

      

       # need_change 为需要找零的金额，
      
     
    

     

      

     
     

      

       # currency_list 为该国货币的面值列表，
      
     
    

     

      

     
     

      

       # num_list 为需要找零的最少货币数目, num_list的长度至少为(need_change+1)
      
     
    

     

      

     
     

      

       def giveChange(need_change, currency_list, num_list):
      
     
    

     

      

     
     

      

        for change in range(need_change+1): #从0开始计算最少需要的货币数
      
     
    

     

      

     
     

      
 for currency in currency_list: #遍历每一种货币
      
     
    

     

      

     
     

      
 if (change-currency >= 0) and (num_list[change-currency]+1<num_list[change]): #计算最少货币需求数
      
     
    

     

      

     
     

      

        num_list[change] = num_list[change-currency] + 1
      
     
    

     

      

     
     

      
 return
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       def main():
      
     
    

     

      

     
     

      

        need_change = 63
      
     
    

     

      

     
     

      

        currency_list = [1,5,10,21,25]
      
     
    

     

      

     
     

      

        num_list = list(range(need_change+1)) #初始化num_list为0到need_change,共(need_change+1)个数
      
     
    

     

      

     
     

      

        giveChange(need_change, currency_list, num_list)
      
     
    

     

      

     
     

      

        print("%d 需要 %d 个货币来找零"%(need_change, num_list[need_change]))
      
     
    

     

      

     
     

      

       if __name__ == "__main__":
      
     
    

     

      

     
     

      
 main()
      
     
   
  

运行结果为：

63 需要 3 个货币来找零
  

仅仅输出了正确的货币数目是不够的，我们还需要输出具体是哪些面值的货币。

自动找零问题的解决

如同常见的，最短路径的记录一样。为输出具体是需要找哪些面值的货币的零钱，我们需要再上一步骤的基础上记录下每步求解最小化使用的货币。
为此，我们需要在添加一个列表，用以记录这个数值。

   

    

     

      

     
     

      

       # need_change 为需要找零的金额，
      
     
    

     

      

     
     

      

       # currency_list 为该国货币的面值列表，
      
     
    

     

      

     
     

      

       # num_list 为需要找零的最少货币数目, num_list的长度至少为(need_change+1)
      
     
    

     

      

     
     

      

       # used_list 为需要找零的最少货币数目, 长度与num_list相同
      
     
    

     

      

     
     

      

       def giveChange(need_change, currency_list, num_list, used_list):
      
     
    

     

      

     
     

      

        for change in range(need_change+1): #从0开始计算最少需要的货币数
      
     
    

     

      

     
     

      
 for currency in currency_list: #遍历每一种货币
      
     
    

     

      

     
     

      
 if (change-currency >= 0) and (num_list[change-currency]+1<=num_list[change]): #计算最少货币需求数
      
     
    

     

      

     
     

      

        num_list[change] = num_list[change-currency] + 1
      
     
    

     

      

     
     

      

        used_list[change] = currency #记录消耗的货币
      
     
    

     

      

     
     

      
 return
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       # 返回需要的货币
      
     
    

     

      

     
     

      

       def showChange(need_change, used_list):
      
     
    

     

      

     
     

      

        give_list = []
      
     
    

     

      

     
     

      
 while need_change > 0:
      
     
    

     

      

     
     

      

        give_list.append(used_list[need_change])
      
     
    

     

      

     
     

      

        need_change -= used_list[need_change]
      
     
    

     

      

     
     

      

        give_list.sort() #排序
      
     
    

     

      

     
     

      
 return give_list
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       def main():
      
     
    

     

      

     
     

      

        need_change = 64 #需要找零的钱数
      
     
    

     

      

     
     

      

        currency_list = [1,5,10,21,25] # 该国的货币面值列表
      
     
    

     

      

     
     

      

        num_list = list(range(need_change+1)) #初始化num_list为0到need_change,共(need_change+1)个数
      
     
    

     

      

     
     

      

        used_list = list(range(need_change+1)) #初始化used_list为0到need_change,共(need_change+1)个数
      
     
    

     

      

     
     

      

        giveChange(need_change, currency_list, num_list, used_list)
      
     
    

     

      

     
     

      

        print("%d 需要 %d 个货币来找零"%(need_change, num_list[need_change]))
      
     
    

     

      

     
     

      

        give_list = showChange(need_change, used_list)
      
     
    

     

      

     
     

      

        print(give_list)
      
     
    

     

      

     
     

      
 
      
     
    

     

      

     
     

      

       if __name__ == "__main__":
      
     
    

     

      

     
     

      
 main()
      
     
   
  

计算结果为：

   

    

     

      

     
     

      

       64 需要 4 个货币来找零
      
     
    

     

      

     
     

      

       [1, 21, 21, 21]