पायथन में सभी कार्यों को पूरा करने के लिए न्यूनतम समय खोजने का कार्यक्रम

मान लीजिए कि हमारे पास जॉब्स नामक एक सरणी है, जहां जॉब्स [i] ith जॉब को पूरा करने के लिए आवश्यक समय की मात्रा को इंगित करता है। हमारे पास एक और मूल्य k भी है, उन्हें हम कार्य सौंप सकते हैं। प्रत्येक कार्य ठीक एक कार्यकर्ता को सौंपा जाना चाहिए। और एक कार्यकर्ता का कार्य समय उसे सौंपे गए सभी कार्यों को पूरा करने में लगने वाला कुल समय है। हमें किसी भी नियत कार्य का न्यूनतम संभव अधिकतम कार्य समय ज्ञात करना है।

इसलिए, यदि इनपुट जॉब्स =[2,1,3,8,5], k =2 की तरह है, तो आउटपुट 10 होगा क्योंकि, हम जॉब असाइन कर सकते हैं जैसे:

कार्यकर्ता1:2 + 5 + 3 =10
कार्यकर्ता 2:1 + 8 =9

तो अधिकतम समय 10 है।

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

सूची कार्यों को उल्टे क्रम में क्रमबद्ध करें
असाइन करें:=पहली k नौकरियों की सूची
नौकरियां :=शेष नौकरियों की सूची
एक फ़ंक्शन को परिभाषित करें dp() । इसमें मुझे, असाइन करना होगा
अगर मैं नौकरियों के आकार के समान हूं, तो
- अधिकतम असाइनमेंट लौटाएं
उत्तर:=अनंत
x के लिए 0 से k-1 की श्रेणी में, करें
- असाइन करें :=असाइन से एक नई सूची
- असाइन करें [x]:=असाइन करें [x] + नौकरियां [i]
- उत्तर:=न्यूनतम उत्तर और डीपी (i+1, असाइन करें)
- असाइन करें [x]:=असाइन करें [x] - नौकरियां [i]
वापसी उत्तर
मुख्य विधि से वापसी dp(0, असाइन करें)

उदाहरण

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

def solve(jobs, k):
   jobs.sort(reverse=True)
   assign = tuple(jobs[:k])
   jobs = jobs[k:]

   def dp(i, assign):
      if i == len(jobs):
         return max(assign)

      ans = float('inf')
      for x in range(k):
         assign = list(assign)
         assign[x] += jobs[i]
         ans = min(ans, dp(i+1, tuple(assign)))
         assign[x] -= jobs[i]

      return ans

   return dp(0, assign)

jobs = [2,1,3,8,5]
k = 2
print(solve(jobs, k))

इनपुट

[2,1,3,8,5], 2