遞歸（ recursion）是一種神奇的編程技巧，可以大幅簡(jiǎn)化代碼，使之看起來(lái)更加簡(jiǎn)潔。然而遞歸設(shè)計(jì)卻非常抽象，不容易掌握。通常，我們都是自上而下的思考問(wèn)題， 遞歸則是自下而上的解決問(wèn)題——這就是遞歸看起來(lái)不夠直觀的原因。

和遞歸相關(guān)的概念里，線性遞歸/非線性遞歸、單向遞歸/非單向遞歸，是非常重要的，要想掌握遞歸技術(shù)，就必須要深入理解。關(guān)于遞歸的基本概念，有興趣的讀者，可以參考我的博客《Python 遞歸算法指歸》。今天，僅就背包問(wèn)題談非單向遞歸函數(shù)如何返回全部結(jié)果。

背包問(wèn)題的背后，是世界七大數(shù)學(xué)難題之一，多項(xiàng)式復(fù)雜程度的非確定性問(wèn)題。作為程序員，可以將該問(wèn)題大致上理解為組合優(yōu)化的問(wèn)題。背包問(wèn)題通常被這樣描述：給定一組物品，每種物品都有自己的重量和價(jià)格，在限定的總重量?jī)?nèi)，如何選擇，才能使得物品的總價(jià)格最高。如果加上不同的限制和條件，背包問(wèn)題可以衍生出很多變種。比如，下面這道題看起來(lái)和背包問(wèn)題相去甚遠(yuǎn)，實(shí)質(zhì)上仍然是一個(gè)典型的背包問(wèn)題。

在一款英雄對(duì)戰(zhàn)游戲中，玩家擁有m件裝備和n位英雄，他可以給每一位英雄分配0件或多件裝備，而不同的英雄擁有不同數(shù)目的裝備時(shí)將獲得不同的攻擊力。玩家如何分配這m件裝備，可以使得n個(gè)英雄獲得的攻擊力的和最大？以玩家擁有5件裝備和3位英雄為例，下表共有3行6列，對(duì)應(yīng)著3位英雄分別擁有從0到5件裝備時(shí)的攻擊力。

即使不熟悉背包問(wèn)題，也不難找到解題思路：

• 找出所有可能的裝備分配方案
• 計(jì)算每一個(gè)方案的攻擊值
• 選擇攻擊值最大的分配方案

1. 找出所有可能的裝備分配方案

找出將m件裝備分配給n位英雄的所有方案是解決問(wèn)題的核心。這里，循環(huán)嵌套是行不通的，因?yà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位英雄的全部方案。顯然，這不是一個(gè)單向遞歸，因?yàn)樵谕患?jí)有多次遞歸調(diào)用，這意味著遞歸過(guò)程有多次從遞歸出口走出。對(duì)于非單向遞歸，是不能使用return返回結(jié)果的。那么，如何讓遞歸函數(shù)返回全部方案呢？請(qǐng)看下面的例子。

>>> 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]]

上面的代碼中，在調(diào)用遞歸函數(shù)之前，先創(chuàng)建一個(gè)全局的列表對(duì)象result，并作為參數(shù)傳遞給遞歸函數(shù)。遞歸調(diào)用結(jié)束后，全部的裝備分配方案就保存在列表對(duì)象result中。

2. 計(jì)算每一個(gè)方案的攻擊值

遍歷56種分配方案，計(jì)算每一種方案的攻擊力之和，保存到一個(gè)新的列表v中。p為3位英雄分別擁有從0到5件裝備時(shí)的攻擊力。

>>> 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列表最大值的序號(hào)，進(jìn)而得到攻擊力最大的裝備分配方案。

>>> max(v)
10
>>> result[v.index(max(v))] 
[4, 0, 1]

最佳分配方案是第1位英雄持有4件裝備，第2位英雄沒(méi)有裝備，第3位英雄持有1件裝備，此時(shí)3位英雄的攻擊力之和為最大，其值為10。

到此這篇關(guān)于Python非單向遞歸函數(shù)如何返回全部結(jié)果的文章就介紹到這了,更多相關(guān)Python非單向遞歸返回 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論