Python में बिना संघर्ष वाली सर्वश्रेष्ठ टीम खोजने का प्रोग्राम

मान लीजिए हमारे पास दो सूचियां scores और ages हैं, जहां scores[i] और ages[i] बास्केटबॉल गेम में iवें खिलाड़ी के स्कोर और उम्र को दर्शाते हैं। हम उच्चतम समग्र स्कोर वाली टीम चुनना चाहते हैं। यहां टीम का स्कोर टीम में सभी खिलाड़ियों के स्कोर का कुल योग है। लेकिन हम गेम में संघर्ष की अनुमति नहीं देते। यहां एक संघर्ष मौजूद है यदि एक छोटा खिलाड़ी एक बड़े खिलाड़ी से सख्ती से अधिक स्कोर रखता है।

उदाहरण के लिए, यदि इनपुट है scores = [5,7,9,14,19], ages = [5,6,7,8,9], तो आउटपुट 54 होगा क्योंकि हम सभी खिलाड़ियों को चुन सकते हैं।

समाधान के चरण

sa := ages और scores से क्रमशः तत्व a और s लेकर बने जोड़ों की सूची
sa सूची को सॉर्ट करें
scores := sa से स्कोर की सूची
maxScore := 0
n := len(scores)
dp := लंबाई n की ऐरे और 0 से भरी
i को 0 से n-1 तक:
- score := scores[i]
- dp[i] := score
- j को 0 से i-1 तक:
  - यदि scores[j] <= score:
    - dp[i] := max(dp[i], dp[j] + score)
- maxScore := max(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]