পাইথনে সব কাজ শেষ করার ন্যূনতম সময় খুঁজে বের করার প্রোগ্রাম

আমাদের একটি অ্যারে আছে jobs, যেখানে jobs[i] নির্দেশ করে i-তম কাজ সম্পন্ন করার জন্য প্রয়োজনীয় সময়। আমাদের আরও একটি মান k আছে, যাদের কাছে আমরা কাজ বান্টব করতে পারি। প্রতিটি কাজ ঠিক একজন কর্মীর কাছে বান্টব করতে হবে। এবং একজন কর্মীর কাজের সময় হলো তাকে বান্টব করা সব কাজের সময়ের যোগফল। আমাদের যেকোনো বান্টবാര জন্য সর্বাধিক কর্মীর কাজের সময়ের ন্যূনতম সম্ভাব্য মান বের করতে হবে।

উদাহরণস্বরূপ, ইনপুট jobs = [2,1,3,8,5], k = 2 হলে আউটপুট হবে 10 কারণ, আমরা কাজ বান্টব করতে পারি:

কর্মী ১: 2 + 5 + 3 = 10
কর্মী ২: 1 + 8 = 9

তাই সর্বাধিক সময় ১০।

সমাধানের ধাপসমূহ (ব্যাকট্র্যাকিং + প্রুনিং)

jobs লিস্টটি রিভার্স সর্ট করুন
assign := jobs[:k] (প্রথম k কাজ)
jobs := jobs[k:] (বাকি কাজগুলো)
dp() ফাংশন ডিফাইন করুন। এটি i, assign ইনপুট নেবে:
- যদি i == len(jobs) হয়, তবে max(assign) রিটার্ন করুন
- ans := infinity
- x = 0 থেকে k-1 পর্যন্ত লুপ চালান:
  - assign := list(assign)
  - assign[x] += jobs[i]
  - ans := min(ans, dp(i+1, tuple(assign)))
  - 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