python換零錢_Python算法之零錢兌換問題的解法

比如：顧客購物買37元東西，給了100元，要找63元，那最少數量就是1張50元，1張10元，3張1元，一共4張。

方法一： 貪心政策

解決這個問題，最直覺的就是使用貪心政策。我們會從最大面值的錢開始，用最多的數量。有餘額再到下一個最大面值，還用最多的數量，一直到1元為止。

def chage_give(coins_list, change):

solutions = []

s_list = sorted(coins_list, reverse=True)

for coin in s_list:

coins_num = change // coin

solutions += [coin,] * coins_num

change = change - coin * coins_num

if coins_num < 0:

break

return len(solutions)

if __name__ == "__main__":

print(chage_give([1, 5, 10, 20, 50, 100], 63))

運作程式，輸出列印結果：

>>> 5

貪心政策在人民币的體系下表現還好，但是如果當存在有21元的面值，貪心政策就會失效。因為63元的最優解是3個面值21元。

方法二：遞歸調用的方式求解

既然貪心政策在特殊的面值下會失效，那我們用遞歸解決這個問題吧。

遞歸的三個首先條件，我們先确定基本結束條件：剩餘需要兌換的零錢正好等于某面值。例如找零10元，答案就是1張10元。

其次是縮小問題的規模：

找零減去 1元 後， 求兌換零錢的最少數量(遞歸調用自身);

找零減去 5元 後， 求兌換零錢的最少數量;

找零減去 10元後， 求兌換零錢的最少數量;

找零減去 20元後， 求兌換零錢的最少數量;

找零減去 50元後， 求兌換零錢的最少數量;

上述 5項 中選擇最小的一個

def change_give_recursion(coins_list, change):

min_coins = change

# 當要兌換的零錢的值正好等于面值清單中其中一項，就直接傳回 1

if change in coins_list:

return 1

else:

# 對各種面值都試用遞歸調用自身，但選擇數量最小的一個。

for i in [ c for c in coins_list if c < change]:

coin_num = 1 + change_give_recursion(coins_list, change - i)

if coin_num < min_coins:

min_coins = coin_num

return min_coins

if __name__ == "__main__":

print(change_give_recursion([1, 5, 10, 20, 50, 100], 63))

運作程式，輸出列印結果：

>>> 5

上面遞歸解法雖然能解決問題，但最大的問題是：非常低效！例如對63元的兌換問題需要進行6千多萬的遞歸調用，有太多的重複計算。是以優化這個算法，我們需要消除重複的計算。

我們可以用一個表将計算過的中間結果儲存起來，在計算之前查表看看是否已經計算過。這個算法的中間結果就是部分找零的最優解，在遞歸調用之前先查找表中是否已有部分找零的最優解，如果有，直接傳回最優解而不進行遞歸調用，如果沒有，才進行遞歸調用。

既然存在問題，我們就要做改進，改進後如下：

def change_give_recursion(coins_list, change, known_result):

min_coins = change

if change in coins_list:

# 如果兌換的零錢正好等于其中一個币值，就先将這個結果記錄下來

known_result[change] = 1

return 1

elif known_result[change] > 0: # 如果已經存在這個零錢值的結果記錄就直接傳回

return known_result[change]

else:

for i in [ c for c in coins_list if c < change]:

coin_num = 1 + change_give_recursion(coins_list, change - i, known_result)

if coin_num < min_coins:

min_coins = coin_num

# 将得到的結果儲存下來，後面調用是供之後檢查

known_result[change] = min_coins

return min_coins

if __name__ == "__main__":

print(change_give_recursion([1, 5, 10, 20, 50, 100], 63, [0] * 64))

改進後的解法，極大的減少了遞歸調用次數。對63元的兌換問題僅需要進行221次的遞歸調用，是改進前的三十萬分之一。這種中間結果記錄的方法叫做“memoization”（記憶化/函數值緩沖）技術，提高了遞歸解法的性能，這種方法的應用如緩沖。

方法三：動态規劃解法

動态規劃（Dynamic programming，簡稱DP）主要用來解決一些希望找到問題最優解的優化問題

找零兌換的動态規劃算法從最簡單的“1元錢找零”的最優解開始，逐漸遞加上去，直到我們需要的找零數。在找零遞加的過程中，設法保持每一分錢的遞加都是最優解，一直加到求解找零數，自然得到最優解。

遞加的過程能保持最優解的關鍵是，其依賴于更少錢數最優解的計算，而更少錢數的最優解已經得到了。問題的最優解包含了更小規模子問題的最優解，這是一個最優化問題能夠用動态規劃政策解決的必要條件。

計算11分錢的兌換法，我們做如下幾步：

1、減去1分錢，剩下10分錢查表最優解是1

2、然後減去5分錢，剩下6分錢查表最優解是2

3、最後減去10分錢，剩下1分錢查表最優解是1

通過上述最小值得到最優解：2個硬币

def change_give_dynamic(coins_list, change, min_coins):

for cents in range(1, change + 1):

coins_count = cents

for j in [c for c in coins_list if c < cents]:

if min_coins[cents - j] + 1 < coins_count:

coins_count = min_coins[cents - j] + 1

min_coins[cents] = coins_count

return min_coins[change]

if __name__ == "__main__":

print(change_give_dynamic([1, 5, 10, 20, 50, 100], 63, [0] * 64))