## How do Python non unidirectional recursive functions return all results? This classic knapsack question gives the answer

Tianyuan prodigal son 2020-11-13 09:06:14
python non unidirectional recursive functions

recursive （ recursion） It's a magic programming technique , Can greatly simplify the code , Make it look simpler . But recursive design is very abstract , It's not easy to master . Usually , We are all thinking from the top down , Recursion is a bottom-up solution —— That's why recursion doesn't seem intuitive enough .

In the concept of recursion , Linear recursion / Nonlinear recursion 、 One way recursion / Non unidirectional recursion , It's very important , To master recursion , We have to understand . About the basic concept of recursion , Interested readers , Please refer to my blog 《Python Recursive algorithm refers to 》. today , In this paper, we discuss how non unidirectional recursive functions return all results .

Behind the knapsack problem , It's one of the seven mathematical problems in the world , The uncertainty of polynomial complexity . As a programmer , This problem can be roughly understood as a combinatorial optimization problem . The knapsack problem is usually described as ： Given a set of items , Each item has its own weight and price , Within the total weight limit , How to choose , To maximize the total price of the item . If you add different restrictions and conditions , Knapsack problem can be derived from many varieties . such as , The following question seems far from the knapsack problem , It's still a typical knapsack problem in essence .

In a hero to war game , Players have m Pieces of equipment and n hero , He can assign to every hero 0 Pieces or pieces of equipment , Different heroes will gain different attack power when they have different numbers of equipment . How players allocate this m Pieces of equipment , You can make n A hero gains the most attack power ？ With players owning 5 Pieces of equipment and 3 Take heroes for example , The following table is common 3 That's ok 6 Column , Corresponding 3 Each of the heroes has his own from 0 To 5 The attack power of equipment .

0 Pieces of 1 Pieces of 2 Pieces of 3 Pieces of 4 Pieces of 5 Pieces of
hero 1 0 1 3 5 7 9
hero 2 0 1 1 3 3 7
hero 3 0 3 4 5 6 7

Even if you're not familiar with knapsack problems , It's not hard to find a solution ：

1. Find out all possible equipment allocation plans
2. Calculate the attack value of each scheme
3. Select the allocation scheme with the largest attack value

## 1. Find out all possible equipment allocation plans

Find out m Pieces of equipment are assigned to n All the solutions of heroes are at the heart of the solution . here , Loop nesting doesn't work , Because nesting levels are input variables . Recursion is the way I think it works .

``````>>> 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) # take 3 Pieces of equipment are assigned to 2 The whole plan of Heroes
[0, 0]
[0, 1]
[0, 2]
[0, 3]
[1, 0]
[1, 1]
[1, 2]
[2, 0]
[2, 1]
[3, 0]
``````

Recursive function bag, Printed out will be 3 Pieces of equipment are assigned to 2 The whole plan of Heroes . obviously , It's not a one-way recursion , Because there are multiple recursive calls at the same level , This means that the recursive process goes out of the recursive exit many times . For non unidirectional recursion , Can't use return Return the result of . that , How to get recursive functions to return all solutions ？ Please see the following example .

``````>>> 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) # take 5 Pieces of equipment are assigned to 3 hero , share 56 There are three kinds of distribution schemes
>>> 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]]
``````

In the above code , Before calling recursive functions , First create a global list object result, And pass it as an argument to the recursive function . After the recursive call ends , All equipment allocation schemes are saved in the list object result in .

## 2. Calculate the attack value of each scheme

Traverse 56 There are three kinds of distribution schemes , Calculate the sum of the attack power of each scheme , Save to a new list v in .p by 3 Each of the heroes has his own from 0 To 5 The attack power of equipment .

``````>>> 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. Select the allocation scheme with the largest attack value

find v The ordinal number of the maximum value of the list , Then get the equipment distribution scheme with the largest attack power .

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

The best allocation scheme is 1 Heroes hold 4 Pieces of equipment , The first 2 One hero is not equipped , The first 3 Heroes hold 1 Pieces of equipment , here 3 The sum of attack power of heroes is the biggest , Its value is 10.