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)
效果圖
更多關于Python相關內(nèi)容可查看本站專題：《Python數(shù)據(jù)結構與算法教程》、《Python Socket編程技巧總結》、《Python函數(shù)使用技巧總結》、《Python字符串操作技巧匯總》、《Python入門與進階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》
希望本文所述對大家Python程序設計有所幫助。
相關文章
這篇文章主要介紹了關于DataFrame中某列值的替換map(dict),具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-02-02
Python轉json時出現(xiàn)中文亂碼的問題及解決
這篇文章主要介紹了Python轉json時出現(xiàn)中文亂碼的問題及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
在本篇文章中我們給大家分享了關于python開發(fā)游戲的前期準備以及用到的工具等內(nèi)容，需要的朋友們跟著參考下。2019-05-05
Python如何使用qrcode生成指定內(nèi)容的二維碼并在GUI界面顯示
現(xiàn)在二維碼很流行,大街小巷大小商品廣告上的二維碼標簽都隨處可見,下面這篇文章主要給大家介紹了關于如何使用qrcode生成指定內(nèi)容的二維碼并在GUI界面顯示的相關資料,需要的朋友可以參考下2022-09-09
本文主要介紹了Python中如何向函數(shù)傳遞列表，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-03-03
這篇文章主要介紹了python實現(xiàn)rsa加密實例詳解的相關資料,需要的朋友可以參考下2017-07-07
使用python requests模塊發(fā)送http請求及接收響應的方法
用 python 編寫 http request 消息代碼時,建議用requests庫,因為requests比urllib內(nèi)置庫更為簡捷,requests可以直接構造get,post請求并發(fā)送,本文給大家介紹了使用python requests模塊發(fā)送http請求及接收響應的方法,需要的朋友可以參考下2024-03-03
正則表達式對大家來說應該都不陌生，下面這篇文章主要給大家介紹了關于Django框架教程之正則表達式URL誤區(qū)的相關資料，文中通過示例代碼介紹的非常詳細，需要的朋友可以參考借鑒，下面隨著小編來一起學習學習吧。2018-01-01
Python?LeNet網(wǎng)絡詳解及pytorch實現(xiàn)
LeNet主要用來進行手寫字符的識別與分類，并在美國的銀行中投入了使用。本文主要為大家詳細介紹了LetNet以及通過pytorch實現(xiàn)LetNet，感興趣的小伙伴可以學習一下2021-11-11
這篇文章主要介紹了將python文件打包exe獨立運行程序方法詳解,需要的朋友可以參考下2020-02-02