Python 비단방향 귀속 함수는 어떻게 모든 결과를 되돌려줍니까

귀속(recursion)은 신기한 프로그래밍 기교로 코드를 대폭 간소화하여 더욱 간결하게 보일 수 있다.그러나 귀속 디자인은 매우 추상적이어서 파악하기 어렵다.통상적으로 우리는 모두 위에서 아래로 사고하는 문제이고, 귀착은 아래에서 위로 문제를 해결하는 것이다. 이것이 바로 귀착이 직관적으로 보이지 않는 원인이다.
귀속과 관련된 개념에서 선형 귀속/비선형 귀속, 단방향 귀속/비단방향 귀속은 매우 중요하다. 귀속 기술을 파악하려면 반드시 깊이 이해해야 한다.귀속의 기본 개념에 대해 흥미를 가진 독자는 나의 블로그 를 참고할 수 있다.오늘은 배낭 문제에 대해서만 비단방향 귀속 함수가 어떻게 모든 결과를 되돌려주는지 이야기한다.
배낭 문제의 배후에는 세계 7대 수학 난제 중 하나인 다항식 복잡도의 불확실성 문제가 있다.프로그래머로서 이 문제를 대체적으로 조합 최적화의 문제로 이해할 수 있다.가방 문제는 일반적으로 이렇게 묘사된다. 한 조의 물품을 정하면 모든 물품은 자신의 무게와 가격이 있다. 한정된 총 무게 안에서 어떻게 선택해야 물품의 총 가격을 가장 높게 할 수 있는지.서로 다른 제한과 조건을 더하면 가방 문제는 많은 변종을 파생시킬 수 있다.예를 들어 아래의 이 문제는 가방 문제와 거리가 멀어 보이지만 실질적으로는 여전히 전형적인 가방 문제이다.
영웅 대전 게임에서 유저는 m개의 장비와 n명의 영웅을 가지고 있습니다. 그는 모든 영웅에게 0개 또는 여러 개의 장비를 분배할 수 있습니다. 서로 다른 영웅이 서로 다른 수의 장비를 가지고 있으면 서로 다른 공격력을 얻을 수 있습니다.유저는 어떻게 이 m개 장비를 분배하여 n개 영웅이 획득한 공격력과 최대를 얻을 수 있습니까?유저가 장비 5 개와 영웅 3 명을 보유한 것을 예로 들면 아래 표는 총 3 행 6열로 3 명의 영웅이 각각 0 개에서 5 개의 장비를 가지고 있을 때의 공격력을 대응한다.
0가지
1 건
2 건
세 가지
4건
5건
영웅
0
일
삼
오
칠
구
영웅2
0
일
일
삼
삼
칠
영웅
0
삼
사
오
육
칠
가방 문제에 익숙하지 않아도 문제 풀이 방향을 찾기 어렵지 않다.

가능한 모든 장비 분배 방안을 찾아라

각 방안의 공격치를 계산한다

공격치의 최대 분배 방안을 선택한다

1. 가능한 모든 장비 분배 방안 찾기

m개 장비를 n명의 영웅에게 분배하는 모든 방안을 찾아내는 것이 문제 해결의 핵심이다.여기에서 순환 플러그인은 통하지 않는다. 왜냐하면 플러그인 층수는 입력 변수이기 때문이다.차례차례 돌아가는 것은 내가 생각한 실행 가능한 방법이다.

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

귀속 함수 bag, 장비 3개를 영웅 2명에게 분배하는 모든 방안을 출력했다.분명히 이것은 일방적인 귀속이 아니다. 왜냐하면 같은 등급에서 여러 차례 귀속 호출이 있기 때문이다. 이것은 귀속 과정이 여러 차례 귀속 출구에서 나왔다는 것을 의미한다.비단방향 귀속은return을 사용하여 결과를 되돌릴 수 없습니다.그렇다면 어떻게 귀속 함수를 모든 방안으로 되돌려줍니까?아래의 예를 보십시오.

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

위의 코드에서 귀속 함수를 호출하기 전에 전역적인 목록 대상result를 만들고 매개 변수로 귀속 함수에 전달합니다.귀속 호출이 끝나면 모든 장비 분배 방안은 목록 대상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 비단방향 귀속 함수가 모든 결과를 어떻게 되돌려주는지에 관한 이 글은 여기에 소개되었습니다. 더 많은 Python 비단방향 귀속 내용은 이전의 글을 검색하거나 아래의 관련 글을 계속 훑어보십시오. 앞으로 많은 응원 부탁드립니다!