โปรแกรมค้นหาทีมที่ดีที่สุดที่ไม่มีข้อขัดแย้งใน Python

สมมติว่าเรามีสองรายการที่เรียกว่าคะแนนและอายุ โดยที่ scores[i] และ ages[i] แทนคะแนนและอายุของผู้เล่นในเกมบาสเก็ตบอล เราต้องการเลือกทีมที่มีคะแนนรวมสูงสุด คะแนนของทีมคือผลรวมคะแนนของผู้เล่นทุกคนในทีม แต่เราไม่อนุญาตให้มีความขัดแย้งในเกม มีข้อขัดแย้งหากผู้เล่นอายุน้อยกว่ามีคะแนนสูงกว่าผู้เล่นที่มีอายุมากกว่าอย่างเคร่งครัด

ดังนั้น หากอินพุตเป็นคะแนน =[5,7,9,14,19] อายุ =[5,6,7,8,9] ผลลัพธ์จะเป็น 54 เนื่องจากเราสามารถเลือกผู้เล่นทั้งหมดได้

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• sa :=รายการของคู่ที่เกิดขึ้นจากองค์ประกอบ a และ s จากวัยและคะแนนตามลำดับ
• เรียงลำดับรายการ sa
• คะแนน :=ทำรายการคะแนนจาก sa
• คะแนนสูงสุด :=0
• n :=ขนาดของคะแนน
• dp :=อาร์เรย์ความยาว n และเติม 0
• สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
  • คะแนน :=คะแนน[i]
  • dp[i] :=คะแนน
  • สำหรับ j ในช่วง 0 ถึง i - 1 ทำ
    • ถ้าคะแนน[j] <=คะแนน แล้ว
      • dp[i] :=สูงสุดของ dp[i] และ dp[j] + คะแนน
  • maxScore :=สูงสุดของ maxScore และ dp[i]
• คืนคะแนนสูงสุด

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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