本文實例講述了Python基于回溯法子集樹模板解決取物搭配問題。分享給大家供大家參考，具體如下：
問題
有5件不同的上衣，3條不同的褲子，4頂不同的帽子，從中取出一頂帽子、一件上衣和一條褲子作為一種搭配，問有多少種不同的搭配？
分析
換個角度看，現(xiàn)有頭、身、腿三個元素，每個元素都有各自的幾種狀態(tài)。
頭元素有['帽1', '帽2', '帽3', '帽4']共4種狀態(tài)，身元素有['衣1', '衣2', '衣3', '衣4', '衣5']共5種狀態(tài)，腿元素有['褲1', '褲2', '褲3']共3種狀態(tài)
從頭開始，自上而下，遍歷每個元素的所有狀態(tài)。
解的長度是固定的。
這里特別注意：每個元素的狀態(tài)數(shù)目不同！！！
套用子集樹模板即可
代碼
```python'''取物排列問題'''n = 3 # 3個元素
頭、身、腿3個元素各自的狀態(tài)空間
a = [['帽1', '帽2', '帽3', '帽4'],['衣1', '衣2', '衣3', '衣4', '衣5'],['褲1', '褲2', '褲3']]x = [0]*n # 一個解，長度固定，3元數(shù)組X = [] # 一組解
沖突檢測
def conflict(k):return False # 無沖突
套用子集樹模板
def match(k): # 到達第k個元素global n, a, x, Xif k >= n: # 超出最尾的元素 print(x) #X.append(x[:]) # 保存（一個解）else: for i in a[k]: # 直接a[k]，若間接則range(len(a[k]))。 遍歷第k個元素的對應的所有選擇狀態(tài)，不同的元素狀態(tài)數(shù)目不同 x[k] = i if not conflict(k): # 剪枝 match(k+1)
測試
match(0) # 從頭（第0個元素）開始
效果圖
希望本文所述對大家Python程序設計有所幫助。
新聞熱點
疑難解答
圖片精選
