पायथन में बिना किसी विरोध के सर्वश्रेष्ठ टीम खोजने का कार्यक्रम

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

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

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• sa :=आयु और अंकों से तत्वों a और s को लेकर बनने वाले युग्मों की सूची
• सूची को क्रमबद्ध करें
• स्कोर:=सा से प्राप्त अंकों की सूची बनाएं
• अधिकतम स्कोर:=0
• n :=स्कोर का आकार
• dp :=लंबाई n की एक सरणी और 0 से भरें
• मैं के लिए 0 से n -1 की सीमा में, करो
  • स्कोर:=स्कोर[i]
  • dp[i] :=स्कोर
  • जे के लिए 0 से i-1 की श्रेणी में, करें
    • यदि स्कोर[j] <=स्कोर, तो
      • dp[i] :=अधिकतम dp[i] और dp[j] + स्कोर
  • अधिकतम स्कोर:=अधिकतम स्कोर और डीपी[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