Python에서 n 작업 후 최대 점수를 찾는 프로그램

<시간/>

크기가 2*n인 num이라는 배열이 있다고 가정합니다. 이 배열에 대해 n개의 작업을 수행해야 합니다. i번째 연산(1-인덱싱됨)에서 다음을 수행합니다.

x와 y의 두 요소를 선택하십시오.
i*gcd(x, y)의 점수를 얻습니다.
배열 번호에서 x와 y를 제거합니다.

n개의 연산을 수행한 후 얻을 수 있는 최대 점수를 찾아야 합니다.

따라서 입력이 nums =[6,2,1,5,4,3]과 같으면 최적의 선택이 (1 * gcd(1, 5)) + (2 * gcd( 2, 4)) + (3 * gcd(3, 6)) =1 + 4 + 9 =14

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

n :=숫자 크기
dp :=크기(2^n)의 배열이고 -1로 채움
dfs() 함수를 정의합니다. 마스크가 필요합니다. t
마스크가 (2^n - 1)과 같으면
- 0 반환
dp[mask]가 -1과 같지 않으면
- 반환 dp[마스크]
엄마 :=0
0에서 n 사이의 i에 대해 수행
- 2^i AND 마스크가 0이 아니면
  - 다음 반복으로 이동
- i + 1에서 n - 1 사이의 j에 대해 다음을 수행하십시오.
  - 2^j AND 마스크가 0이 아니면
    - 다음 반복으로 이동
  - 다음 :=dfs(마스크 OR 2^i OR 2^j, t+1) + gcd(nums[i], nums[j])*t
  - ma :=다음 및 ma의 최대값
dp[마스크] :=ma
반환 dp[마스크]
기본 메서드에서 dfs(0, 1)
를 반환합니다.

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다.

from math import gcd
def solve(nums):
   n = len(nums)
   dp = [-1] * (1 << n)

   def dfs(mask, t):
      if mask == (1 << n) - 1:
         return 0
      if dp[mask] != -1:
         return dp[mask]
      ma = 0
      for i in range(n):
         if (1 << i) & mask:
            continue
         for j in range(i + 1, n):
            if (1 << j) & mask:
               continue
            next = dfs(mask | (1 << i) | (1 << j), t + 1) + gcd(nums[i], nums[j]) * t
            ma = max(next, ma)
      dp[mask] = ma
      return dp[mask]

   return dfs(0, 1)

nums = [6,2,1,5,4,3]
print(solve(nums))

입력

[6,2,1,5,4,3]

Python에서 n 작업 후 최대 점수를 찾는 프로그램

예시

입력

출력