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

ปัญหา

scores[i], ages[i] คะแนนและอายุผู้เล่น ต้องการทีมคะแนนรวมสูงสุด โดยไม่มีข้อขัดแย้ง: ผู้เล่นอายุน้อยกว่ามีคะแนนสูงกว่าผู้เล่นอายุมากกว่าอย่างเคร่งครัด

ตัวอย่าง

scores=[5,7,9,14,19], ages=[5,6,7,8,9] → 54 (เลือกทุกคนได้เพราะคะแนนเพิ่มตามอายุ)

ขั้นตอนการแก้ปัญหา

1. sa := list of (age, score) เรียงตามอายุ แล้วคะแนน
2. scores := [s for a,s in sa]
3. DP: dp[i] = คะแนนสูงสุดจบที่ i
4. วน i 0..n-1:
   • dp[i] = scores[i]
   • วน j 0..i-1: ถ้า scores[j] <= scores[i]: dp[i] = max(dp[i], dp[j] + scores[i])
   • อัปเดต maxScore
5. คืน maxScore

การนำไปใช้งาน (Python)

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