Python非單向遞歸函數(shù)如何返回全部結果
遞歸（ recursion）是一種神奇的編程技巧，可以大幅簡化代碼，使之看起來更加簡潔。然而遞歸設計卻非常抽象，不容易掌握。通常，我們都是自上而下的思考問題， 遞歸則是自下而上的解決問題——這就是遞歸看起來不夠直觀的原因。
和遞歸相關的概念里，線性遞歸/非線性遞歸、單向遞歸/非單向遞歸，是非常重要的，要想掌握遞歸技術，就必須要深入理解。關于遞歸的基本概念，有興趣的讀者，可以參考我的博客《Python 遞歸算法指歸》。今天，僅就背包問題談非單向遞歸函數(shù)如何返回全部結果。
背包問題的背后，是世界七大數(shù)學難題之一，多項式復雜程度的非確定性問題。作為程序員，可以將該問題大致上理解為組合優(yōu)化的問題。背包問題通常被這樣描述：給定一組物品，每種物品都有自己的重量和價格，在限定的總重量內，如何選擇，才能使得物品的總價格最高。如果加上不同的限制和條件，背包問題可以衍生出很多變種。比如，下面這道題看起來和背包問題相去甚遠，實質上仍然是一個典型的背包問題。
在一款英雄對戰(zhàn)游戲中，玩家擁有m件裝備和n位英雄，他可以給每一位英雄分配0件或多件裝備，而不同的英雄擁有不同數(shù)目的裝備時將獲得不同的攻擊力。玩家如何分配這m件裝備，可以使得n個英雄獲得的攻擊力的和最大？以玩家擁有5件裝備和3位英雄為例，下表共有3行6列，對應著3位英雄分別擁有從0到5件裝備時的攻擊力。
| 0件 | 1件 | 2件 | 3件 | 4件 | 5件 | |
|---|---|---|---|---|---|---|
| 英雄1 | 0 | 1 | 3 | 5 | 7 | 9 |
| 英雄2 | 0 | 1 | 1 | 3 | 3 | 7 |
| 英雄3 | 0 | 3 | 4 | 5 | 6 | 7 |
即使不熟悉背包問題，也不難找到解題思路：
- 找出所有可能的裝備分配方案
- 計算每一個方案的攻擊值
- 選擇攻擊值最大的分配方案
1. 找出所有可能的裝備分配方案
找出將m件裝備分配給n位英雄的所有方案是解決問題的核心。這里，循環(huán)嵌套是行不通的，因為嵌套層數(shù)是輸入變量。遞歸是我想到的可行的方法。
>>> def bag(m, n, series=list()):
if n == 1:
for i in range(m+1):
print(series+[i])
else:
for i in range(m+1):
bag(m-i, n-1, series+[i])
>>> bag(3,2) # 將3件裝備分配給2位英雄的全部方案
[0, 0]
[0, 1]
[0, 2]
[0, 3]
[1, 0]
[1, 1]
[1, 2]
[2, 0]
[2, 1]
[3, 0]
遞歸函數(shù)bag，打印出了將3件裝備分配給2位英雄的全部方案。顯然，這不是一個單向遞歸，因為在同一級有多次遞歸調用，這意味著遞歸過程有多次從遞歸出口走出。對于非單向遞歸，是不能使用return返回結果的。那么，如何讓遞歸函數(shù)返回全部方案呢？請看下面的例子。
>>> def bag(m, n, result, series=list()): if n == 1: for i in range(m+1): result.append(series+[i]) #print(result[-1]) else: for i in range(m+1): bag(m-i, n-1, result, series+[i]) >>> result = list() >>> bag(5, 3, result) # 將5件裝備分配給3位英雄，共有56種分配方案 >>> len(result) 56 >>> result [[0, 0, 0], [0, 0, 1], [0, 0, 2], [0, 0, 3], [0, 0, 4], [0, 0, 5], [0, 1, 0], [0, 1, 1], [0, 1, 2], [0, 1, 3], [0, 1, 4], [0, 2, 0], [0, 2, 1], [0, 2, 2], [0, 2, 3], [0, 3, 0], [0, 3, 1], [0, 3, 2], [0, 4, 0], [0, 4, 1], [0, 5, 0], [1, 0, 0], [1, 0, 1], [1, 0, 2], [1, 0, 3], [1, 0, 4], [1, 1, 0], [1, 1, 1], [1, 1, 2], [1, 1, 3], [1, 2, 0], [1, 2, 1], [1, 2, 2], [1, 3, 0], [1, 3, 1], [1, 4, 0], [2, 0, 0], [2, 0, 1], [2, 0, 2], [2, 0, 3], [2, 1, 0], [2, 1, 1], [2, 1, 2], [2, 2, 0], [2, 2, 1], [2, 3, 0], [3, 0, 0], [3, 0, 1], [3, 0, 2], [3, 1, 0], [3, 1, 1], [3, 2, 0], [4, 0, 0], [4, 0, 1], [4, 1, 0], [5, 0, 0]]
上面的代碼中，在調用遞歸函數(shù)之前，先創(chuàng)建一個全局的列表對象result，并作為參數(shù)傳遞給遞歸函數(shù)。遞歸調用結束后，全部的裝備分配方案就保存在列表對象result中。
2. 計算每一個方案的攻擊值
遍歷56種分配方案，計算每一種方案的攻擊力之和，保存到一個新的列表v中。p為3位英雄分別擁有從0到5件裝備時的攻擊力。
>>> p = [
[0,1,3,5,7,9],
[0,1,1,3,3,7],
[0,3,4,5,6,7]
]
>>> v = list()
>>> for item in result:
v.append(p[0][item[0]] + p[1][item[1]] + p[2][item[2]])
>>> v
[0, 3, 4, 5, 6, 7, 1, 4, 5, 6, 7, 1, 4, 5, 6, 3, 6, 7, 3,
6, 7, 1, 4, 5, 6, 7, 2, 5, 6, 7, 2, 5, 6, 4, 7, 4, 3, 6,
7, 8, 4, 7, 8, 4, 7, 6, 5, 8, 9, 6, 9, 6, 7, 10, 8, 9]
3. 選擇攻擊值最大的分配方案
找出v列表最大值的序號，進而得到攻擊力最大的裝備分配方案。
>>> max(v) 10 >>> result[v.index(max(v))] [4, 0, 1]
最佳分配方案是第1位英雄持有4件裝備，第2位英雄沒有裝備，第3位英雄持有1件裝備，此時3位英雄的攻擊力之和為最大，其值為10。
到此這篇關于Python非單向遞歸函數(shù)如何返回全部結果的文章就介紹到這了,更多相關Python非單向遞歸返回 內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
下面小編就為大家?guī)硪黄獪\談scrapy 的基本命令介紹。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-06-06
這篇文章主要為大家詳細介紹了python實現(xiàn)飛行棋游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-02-02
這篇文章主要介紹了Python解決爬蟲程序卡死問題，文章圍繞主題展開詳細內容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-05-05
Python?按規(guī)則解析并替換字符串中的變量及函數(shù)(示例代碼)
這篇文章主要介紹了Python?按規(guī)則解析并替換字符串中的變量及函數(shù),本文通過示例代碼給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-11-11
本文主要講述了Python文件基礎知識，包括文件的打開、讀寫、關閉操作、使用循環(huán)讀寫文件及迭代器的知識。具有很好的參考價值。下面跟著小編一起來看下吧2017-03-03
這篇文章主要介紹了pycharm配置python 設置pip安裝源為豆瓣源，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-02-02
這篇文章主要介紹了python中棧的原理及實現(xiàn)方法,結合實例形式分析了Python棧的概念、原理、常見操作方法及相關使用技巧,需要的朋友可以參考下2019-11-11
Python實現(xiàn)數(shù)據(jù)清洗的示例詳解
這篇文章主要通過五個示例帶大家深入了解下Python實現(xiàn)數(shù)據(jù)清洗的具體方法，文中的示例代碼講解詳細，對我們學習Python有一定幫助，需要的可以參考一下2022-08-08
這篇文章主要介紹了使用python?xmlrpc連接odoo方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-01-01
今天小編就為大家分享一篇對Python中畫圖時候的線類型詳解，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2019-07-07