Python에서 충돌 없이 최고의 팀을 찾는 프로그램

<시간/>

score[i]와 age[i]는 농구 경기에서 i번째 선수의 점수와 나이를 나타내는 두 개의 목록에서 점수와 연령이라는 두 개의 목록이 있다고 가정합니다. 전체 점수가 가장 높은 팀을 선택하려고 합니다. 여기서 팀 점수는 팀의 모든 플레이어 점수의 합계입니다. 그러나 우리는 게임에서 충돌을 허용하지 않습니다. 어린 선수가 나이가 많은 선수보다 점수가 엄격하게 높은 경우 충돌이 존재합니다.

따라서 입력이 점수 =[5,7,9,14,19], 연령 =[5,6,7,8,9]인 경우 모든 플레이어를 선택할 수 있으므로 출력은 54가 됩니다.

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

sa :=연령과 점수에서 각각 요소 a와 s를 취하여 형성된 쌍의 목록
목록 정렬
scores :=sa의 점수 목록 만들기
최대 점수:=0
n :=점수 크기
dp :=길이가 n이고 0으로 채워진 배열
0 ~ n - 1 범위의 i에 대해
- 점수 :=점수[i]
- dp[i] :=점수
- 0 ~ i - 1 범위의 j에 대해
  - 점수[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]