पायथन में सभी जॉब्स को खत्म करने का न्यूनतम समय खोजने का प्रोग्राम

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

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

वर्कर1: 2 + 5 + 3 = 10
वर्कर2: 1 + 8 = 9

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

हल करने के चरण

jobs सूची को रिवर्स ऑर्डर में सॉर्ट करें।
assign := पहले k जॉब्स की सूची
jobs := शेष जॉब्स की सूची
dp() फ़ंक्शन परिभाषित करें। यह i, assign लेगा:
- यदि i == len(jobs), तो max(assign) वापस करें।
- ans := infinity
- x को 0 से k - 1 तक लूप चलाएं:
  - assign := assign से नई सूची
  - assign[x] := assign[x] + jobs[i]
  - ans := min(ans, dp(i+1, assign))
  - assign[x] := assign[x] - jobs[i]
- ans वापस करें।
मुख्य मेथड से dp(0, assign) वापस करें।

उदाहरण

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

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