Pythonでn回の操作後に最大スコアを見つけるプログラム

サイズが2*nのnumsという配列があるとします。この配列に対してn個の操作を実行する必要があります。 i番目の操作（1インデックス）では、次のことを行います。

• xとyの2つの要素を選択します。

• 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：=numsのサイズ

• dp：=サイズ（2 ^ n）の配列で、-1で埋めます

• 関数dfs（）を定義します。これはマスクを取ります、t

• マスクが（2 ^ n-1）と同じ場合、

  • 0を返す

• dp [mask]が-1と同じでない場合、

  • dp[マスク]

    を返します

• ma：=0

• 0からnの範囲のiの場合、実行

  • 2 ^ i ANDマスクがゼロ以外の場合、

    • 次のイテレーションに行く

  • i +1からn-1の範囲のjの場合、実行

    • 2 ^ j ANDマスクがゼロ以外の場合、

      • 次のイテレーションに行く

    • next：=dfs（mask OR 2 ^ i OR 2 ^ j、t + 1）+ gcd（nums [i]、nums [j]）* t

    • ma：=nextとmaの最大値

• dp [マスク]：=ma

• dp[マスク]

  を返します

• mainメソッドから、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]

出力

14