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 ：

- Find out all possible equipment allocation plans
- Calculate the attack value of each scheme
- Select the allocation scheme with the largest attack value

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 .

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

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.

- 利用Python爬虫获取招聘网站职位信息
- Using Python crawler to obtain job information of recruitment website
- Several highly rated Python libraries arrow, jsonpath, psutil and tenacity are recommended
- Python装饰器
- Python实现LDAP认证
- Python decorator
- Implementing LDAP authentication with Python
- Vscode configures Python development environment!
- In Python, how dare you say you can't log module? ️
- 我收藏的有关Python的电子书和资料
- python 中 lambda的一些tips
- python中字典的一些tips
- python 用生成器生成斐波那契数列
- python脚本转pyc踩了个坑。。。
- My collection of e-books and materials about Python
- Some tips of lambda in Python
- Some tips of dictionary in Python
- Using Python generator to generate Fibonacci sequence
- The conversion of Python script to PyC stepped on a pit...
- Python游戏开发，pygame模块，Python实现扫雷小游戏
- Python game development, pyGame module, python implementation of minesweeping games
- Python实用工具，email模块，Python实现邮件远程控制自己电脑
- Python utility, email module, python realizes mail remote control of its own computer
- 毫无头绪的自学Python，你可能连门槛都摸不到！【最佳学习路线】
- Python读取二进制文件代码方法解析
- Python字典的实现原理
- Without a clue, you may not even touch the threshold【 Best learning route]
- Parsing method of Python reading binary file code
- Implementation principle of Python dictionary
- You must know the function of pandas to parse JSON data - JSON_ normalize()
- Python实用案例，私人定制，Python自动化生成爱豆专属2021日历
- Python practical case, private customization, python automatic generation of Adu exclusive 2021 calendar
- 《Python实例》震惊了，用Python这么简单实现了聊天系统的脏话，广告检测
- "Python instance" was shocked and realized the dirty words and advertisement detection of the chat system in Python
- Convolutional neural network processing sequence for Python deep learning
- Python data structure and algorithm (1) -- enum type enum
- 超全大厂算法岗百问百答（推荐系统/机器学习/深度学习/C++/Spark/python）
- 【Python进阶】你真的明白NumPy中的ndarray吗？
- All questions and answers for algorithm posts of super large factories (recommended system / machine learning / deep learning / C + + / spark / Python)
- [advanced Python] do you really understand ndarray in numpy?
- 【Python进阶】Python进阶专栏栏主自述：不忘初心，砥砺前行
- [advanced Python] Python advanced column main readme: never forget the original intention and forge ahead
- python垃圾回收和缓存管理
- java调用Python程序
- java调用Python程序
- Python常用函数有哪些?Python基础入门课程
- Python garbage collection and cache management
- Java calling Python program
- Java calling Python program
- What functions are commonly used in Python? Introduction to Python Basics
- Python basic knowledge
- Anaconda5.2 安装 Python 库（MySQLdb）的方法
- Python实现对脑电数据情绪分析
- Anaconda 5.2 method of installing Python Library (mysqldb)
- Python implements emotion analysis of EEG data
- Master some advanced usage of Python in 30 seconds, which makes others envy it
- python爬取百度图片并对图片做一系列处理
- Python crawls Baidu pictures and does a series of processing on them
- python链接mysql数据库
- Python link MySQL database