'''找零問題'''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)