本文實例講述了Python基于回溯法子集樹模板解決找零問題。分享給大家供大家參考，具體如下：

問題

有面額10元、5元、2元、1元的硬幣，數量分別為3個、5個、7個、12個。現在需要給顧客找零16元，要求硬幣的個數最少，應該如何找零？或者指出該問題無解。

分析

元素——狀態空間分析大法：四種面額的硬幣看作4個元素，對應的數目看作各自的狀態空間，遍歷狀態空間，其它的事情交給剪枝函數。

解的長度固定：4

解的編碼：(x1,x2,x3,x4) 其中x1∈[0,1,2,3], x2∈[0,1,2,3,4,5], x3∈[0,1,2,...,7], x4∈[0,1,2,...,12]

求最優解，增添全局變量：best_x, best_num

套用回溯法子集樹模板。

代碼

'''找零問題'''n = 4a = [10, 5, 2, 1] # 四種面額b = [3, 5, 7, 12] # 對應的硬幣數目（狀態空間）m = 53 # 給定的金額x = [0]*n  # 一個解（n元0-b[k]數組）X = []  # 一組解best_x = [] # 最佳解best_num = 0 # 最少硬幣數目# 沖突檢測def conflict(k):  global n,m, x, X, a, b, best_num  # 部分解的金額已超  if sum([p*q for p,q in zip(a[:k+1], x[:k+1])]) > m:    return True  # 部分解的金額加上剩下的所有金額不夠  if sum([p*q for p,q in zip(a[:k+1], x[:k+1])]) + sum([p*q for p,q in zip(a[k+1:], b[k+1:])]) < m:    return True  # 部分解的硬幣個數超best_num  num = sum(x[:k+1])  if 0 < best_num < num:    return True  return False # 無沖突# 回溯法（遞歸版本）def subsets(k): # 到達第k個元素  global n, a, b, x, X, best_x, best_num  if k == n: # 超出最尾的元素    #print(x)    X.append(x[:]) # 保存（一個解）    # 計算硬幣數目，若最佳，則保存    num = sum(x)    if best_num == 0 or best_num > num:      best_num = num      best_x = x[:]  else:    for i in range(b[k]+1): # 遍歷元素 a[k] 的可供選擇狀態: 0, 1, 2, ..., b[k] 個硬幣      x[k] = i      if not conflict(k): # 剪枝        subsets(k+1)# 測試subsets(0)print(best_x)

效果圖

更多關于Python相關內容可查看本站專題：《Python數據結構與算法教程》、《Python Socket編程技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》、《Python入門與進階經典教程》及《Python文件與目錄操作技巧匯總》

希望本文所述對大家Python程序設計有所幫助。