动态规划——最少硬币找零问题（python）

1. 问题描述

2. 思路

刚开始是想利用贪心算法。假如要找的零钱总额为49元，先找10块的，能够找40块，再继续找5块的，能够找5块，再继续找2块的，能够找4块。找够49元的最少纸币数为4 + 1 + 2 = 7。可是有些状况可能不太行，例如：有纸币1元、3元、4元，要找6元的零钱，若是按照贪心算法的话，是找一张4元和两张1元，一共3张纸币。可是找6块钱的话，最少的方法应该是找两张3块。所以贪心算法在这里是失效的。
进一步，能够利用动态规划的算法来进行求解：python

2.1 动态规划

经过这个递归公式咱们能够进行填表。表格的初始化方式不太同样。咱们以三种纸币一、三、4，找6块钱的零钱为例。因为表的第一行表示用面额为0的纸币找钱，那么找任意数量的钱，都须要无穷多的纸币，所以标的第一行初始化为python可以支持的最大数。第一列表示须要找0块钱（不须要找钱），用什么面额的钱找，都只须要0张，所以除了第一格，第一列统一初始化为0。表中的其余初始化为0。
web

2.2 python代码

import sys
max = sys.maxsize
def giveChange(coinList,totalCoin):
    result = [[0 for i in range(totalCoin + 1)] for j in range(len(coinList) + 1)]
    for j in range(totalCoin+1):
            result[0][j] = max
    for i in range(1,len(coinList)+1):
        for j in range(1,totalCoin + 1):
            if j >= coinList[i-1]:
                result[i][j] = min(result[i - 1][j], result[i][j - coinList[i - 1]]+1)
            else:
                result[i][j] = result[i-1][j]
    return result,result[i][j]
print(giveChange([1,3,4],6))
# 运行结果：
([[9223372036854775807, 9223372036854775807, 9223372036854775807, 9223372036854775807, 9223372036854775807, 9223372036854775807, 9223372036854775807], 
[0, 1, 2, 3, 4, 5, 6], 
[0, 1, 2, 1, 2, 3, 2], 
[0, 1, 2, 1, 1, 2, 2]],
 2)

最后找6块钱用的最少的纸币数是2张。算法