Chương trình tìm nhóm tốt nhất không có xung đột bằng Python

Giả sử chúng ta có hai danh sách được gọi là điểm số và độ tuổi, trong đó điểm số [i] và độ tuổi [i] thể hiện điểm số và tuổi của cầu thủ thứ i trong một trận đấu bóng rổ. Chúng tôi muốn chọn đội có điểm tổng cao nhất. Ở đây điểm của đội là tổng điểm của tất cả các cầu thủ trong đội. Nhưng chúng tôi không để xảy ra xung đột trong trò chơi. Ở đây sẽ xảy ra xung đột nếu người chơi trẻ hơn có số điểm cao hơn người chơi lớn tuổi hơn.

Vì vậy, nếu đầu vào là điểm =[5,7,9,14,19], age =[5,6,7,8,9], thì đầu ra sẽ là 54 vì chúng ta có thể chọn tất cả người chơi.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• sa:=danh sách các cặp được hình thành bằng cách lấy các phần tử a và s từ độ tuổi và điểm số tương ứng
• sắp xếp danh sách sa
• điểm số:=lập một danh sách các điểm số từ sa
• maxScore:=0
• n:=kích thước của điểm
• dp:=một mảng có độ dài n và điền bằng 0
• đối với tôi trong phạm vi từ 0 đến n - 1, thực hiện
  • điểm:=điểm [i]
  • dp [i]:=điểm
  • đối với j trong phạm vi từ 0 đến i - 1, thực hiện
    • nếu điểm [j] <=điểm, thì
      • dp [i]:=tối đa dp [i] và dp [j] + điểm
  • maxScore:=tối đa của maxScore và dp [i]
• trả về điểm maxScore

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

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

Đầu vào

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

Đầu ra

54