पायथन में कुछ असाइनमेंट को पूरा करके हम अधिकतम क्रेडिट प्राप्त करने का कार्यक्रम प्राप्त कर सकते हैं

मान लीजिए कि हमारे पास एक ही आकार की दो सूचियां हैं, ये समय सीमा और क्रेडिट हैं और वे पाठ्यक्रम असाइनमेंट का प्रतिनिधित्व कर रहे हैं। यहां डेडलाइन [i] असाइनमेंट I के लिए डेडलाइन दिन दिखाती है और क्रेडिट्स [i] असाइनमेंट के लिए हमें मिलने वाले क्रेडिट की मात्रा को दर्शाता है। हमारे पास एक असाइनमेंट पूरा करने के लिए एक दिन है, और इसे समय सीमा से पहले या उससे पहले पूरा किया जा सकता है। हम एक ही समय में कई असाइनमेंट नहीं कर सकते। हमें असाइनमेंट के कुछ सबसेट को पूरा करके अधिकतम क्रेडिट प्राप्त करना होगा।

इसलिए, यदि इनपुट डेडलाइन =[1, 2, 2, 2] क्रेडिट =[4, 5, 6, 7] की तरह है, तो आउटपुट 18 होगा, क्योंकि हम दिन 0 पर क्रेडिट 5 के साथ असाइनमेंट पूरा कर सकते हैं, पूरा करें 1 दिन में क्रेडिट 6 के साथ असाइनमेंट और 3 दिन क्रेडिट 7 के साथ असाइनमेंट पूरा करें।

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

• a :=समय सीमा और क्रेडिट की एक जोड़ी बनाएं और क्रेडिट के आधार पर उन्हें अवरोही क्रम में क्रमबद्ध करें
• अगर a खाली है, तो
  • वापसी 0
• res :=आकार की एक सूची (1 + अधिकतम समय सीमा) और 0 से भरें
• उत्तर:=0
• प्रत्येक जोड़ी (i, j) के लिए a, do
  • k के लिए I से 0 तक की श्रेणी में, 1 से घटाएं
    • यदि रेस [के] 0 है, तो
      • res[k] :=1
      • उत्तर:=उत्तर + जे
      • लूप से बाहर आएं
• वापसी उत्तर

आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -

उदाहरण

class Solution:
   def solve(self, deadlines, credits):
      a = sorted(list(zip(deadlines, credits)), key=lambda x: x[1], reverse=True)
      if not a:
         return 0
      res = [0] * (max(deadlines) + 1)
      ans = 0
      for i, j in a:
         for k in range(i, -1, -1):
            if not res[k]:
               res[k] = 1
               ans += j
               break
      return ans
     
ob = Solution()
deadlines = [1, 2, 2, 2]
credits = [4, 5, 6, 7]
print(ob.solve(deadlines, credits))

इनपुट

[1, 2, 2, 2], [4, 5, 6, 7]

आउटपुट

18