Pythonで競合のない最良のチームを見つけるためのプログラム

スコアと年齢という2つのリストがあるとします。ここで、scores[i]とages[i]は、バスケットボールゲームのi番目のプレーヤーのスコアと年齢を表します。総合スコアが最も高いチームを選びたい。ここで、チームのスコアは、チーム内のすべてのプレーヤーのスコアの合計です。ただし、ゲーム内での競合は許可されていません。ここでは、若いプレーヤーのスコアが古いプレーヤーよりも厳密に高い場合、競合が発生します。

したがって、入力がスコア=[5,7,9,14,19]、年齢=[5,6,7,8,9]の場合、すべてのプレーヤーを選択できるため、出力は54になります。

これを解決するには、次の手順に従います-

• sa：=年齢とスコアからそれぞれ要素aとsを取得して形成されたペアのリスト
• リストを並べ替える
• スコア：=saからのスコアのリストを作成する
• maxScore：=0
• n：=スコアのサイズ
• dp：=長さnの配列で、0で埋めます
• 0からn-1の範囲のiの場合、do
  • スコア：=スコア[i]
  • dp [i]：=スコア
  • 0からi-1の範囲のjの場合、do
    • スコア[j]<=スコアの場合、
      • dp [i]：=dp[i]とdp[j]+スコアの最大値
  • maxScore：=maxScoreとdp[i]の最大値
• maxScoreを返す

例

理解を深めるために、次の実装を見てみましょう-

def solve(scores, ages):
   sa = [[a,s] for a,s in zip(ages,scores)]

   sa.sort()
   scores = [s for a,s in sa]

   maxScore = 0
   n = len(scores)
   dp = [0] * n

   for i in range(n):
      score = scores[i]
      dp[i] = score

      for j in range(i):
         if scores[j] <= score:
            dp[i] = max(dp[i],dp[j] + score)
      maxScore = max(maxScore, dp[i])

   return maxScore

scores = [5,7,9,14,19]
ages = [5,6,7,8,9]
print(solve(scores, ages))

入力

[5,7,9,14,19], [5,6,7,8,9]

出力

54