Python基于回溯法子集樹模板解決找零問題示例

更新時間：2017年09月11日 11:17:19 作者：羅兵

這篇文章主要介紹了Python基于回溯法子集樹模板解決找零問題,簡單描述了找零問題并結合具體實例形式分析了Python使用回溯法子集樹模板解決找零問題的步驟、實現(xiàn)方法與相關操作技巧,需要的朋友可以參考下

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

問題

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

分析

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

解的長度固定：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]

求最優(yōu)解，增添全局變量：best_x, best_num

套用回溯法子集樹模板。

代碼

'''找零問題'''
n = 4
a = [10, 5, 2, 1] # 四種面額
b = [3, 5, 7, 12] # 對應的硬幣數(shù)目（狀態(tài)空間）
m = 53 # 給定的金額
x = [0]*n  # 一個解（n元0-b[k]數(shù)組）
X = []  # 一組解
best_x = [] # 最佳解
best_num = 0 # 最少硬幣數(shù)目
# 沖突檢測
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
  # 部分解的硬幣個數(shù)超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[:]) # 保存（一個解）
    # 計算硬幣數(shù)目，若最佳，則保存
    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] 的可供選擇狀態(tài): 0, 1, 2, ..., b[k] 個硬幣
      x[k] = i
      if not conflict(k): # 剪枝
        subsets(k+1)
# 測試
subsets(0)
print(best_x)

效果圖