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

ধরুন আমাদের কাছে কাজ নামে একটি অ্যারে আছে, যেখানে jobs[i] ith কাজটি সম্পূর্ণ করার জন্য প্রয়োজনীয় সময়ের পরিমাণ নির্দেশ করে। আমাদের আরও একটি মান আছে, তাদের আমরা কাজ বরাদ্দ করতে পারি। প্রতিটি কাজ ঠিক একজন কর্মীকে বরাদ্দ করা উচিত। এবং একজন শ্রমিকের কাজের সময় হল তাদের জন্য নির্ধারিত সমস্ত কাজ সম্পূর্ণ করতে মোট সময়। আমাদের যেকোন অ্যাসাইনমেন্টের সর্বনিম্ন সম্ভাব্য সর্বাধিক কাজের সময় খুঁজে বের করতে হবে।

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

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

তাই সর্বোচ্চ সময় 10।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

তালিকার কাজগুলিকে বিপরীত ক্রমে সাজান
বরাদ্দ করুন :=প্রথম k কাজের তালিকা
চাকরি :=বাকি চাকরির তালিকা
একটি ফাংশন dp() সংজ্ঞায়িত করুন। এটি i, assign
লাগবে
যদি আমি কাজের আকারের সমান হয়, তাহলে
- অ্যাসাইন সর্বাধিক ফেরত
উত্তর :=অসীম
0 থেকে k - 1 রেঞ্জের x এর জন্য, করুন
- assign :=assign থেকে একটি নতুন তালিকা
- বরাদ্দ [x] :=বরাদ্দ [x] + কাজ[i]
- উত্তর :=সর্বনিম্ন উত্তর এবং dp(i+1, assign)
- assign [x] :=বরাদ্দ [x] - কাজ[i]
উত্তর ফেরত দিন
মূল পদ্ধতি থেকে 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