পাইথনে নতুন ডোনাট পেতে সর্বাধিক সংখ্যক গ্রুপ খুঁজে বের করার প্রোগ্রাম

ধরুন আমাদের একটি মান ব্যাচসাইজ এবং একটি অ্যারে গ্রুপ রয়েছে যেখানে গ্রুপ[i] বোঝায় যে একটি গ্রুপ[i] গ্রাহকরা দোকানে যাবেন। তাই একটি ডোনাট দোকান আছে যেটি প্রদত্ত ব্যাচসাইজের ব্যাচে ডোনাট বেক করে। তবে তাদের একটি নিয়ম আছে, পরবর্তী ব্যাচের যেকোনো ডোনাট পরিবেশন করার আগে তাদের অবশ্যই একটি ব্যাচের সমস্ত ডোনাট পরিবেশন করতে হবে। এবং প্রতিটি গ্রাহক ঠিক একটি ডোনাট পাবেন। যখন একটি গোষ্ঠী দোকানে প্রবেশ করে, তখন সেই গোষ্ঠীর সমস্ত গ্রাহকদের পরবর্তী কোনও গ্রুপকে সম্বোধন করার আগে অবশ্যই পরিবেশন করতে হবে। একটি দল খুশি হতে পারে যদি তারা সবাই তাজা ডোনাট পায়। (অন্য কথায় গ্রুপের প্রথম গ্রাহক শেষ গ্রুপ থেকে অবশিষ্ট ডোনাট গ্রহণ করেন না)।

আমরা গোষ্ঠীগুলিকে পুনর্বিন্যাস করতে পারি, এবং অবশেষে আমাদের দলগুলিকে পুনর্বিন্যাস করার পরে সর্বাধিক সম্ভাব্য সংখ্যক সুখী গোষ্ঠী খুঁজে বের করতে হবে৷

সুতরাং, যদি ইনপুটটি ব্যাচসাইজ =4 গ্রুপ =[2,1,8,4,3] এর মতো হয়, তবে আউটপুট 4 হবে কারণ আমরা তাদের [8,4,2,3,1] এর মতো পুনরায় সাজাতে পারি তাই প্রথমে, দ্বিতীয়, তৃতীয় ও চতুর্থ দল খুশি। আমরা প্রথম গ্রুপের জন্য দুটি ব্যাচ ডোনাট, দ্বিতীয় গ্রুপের জন্য একটি ব্যাচ এবং একটি ব্যাচ তৈরি করে তারপর তৃতীয় গ্রুপে এবং একটি চতুর্থ গ্রুপে পরিবেশন করতে পারি।

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

• l :=গ্রুপের সকল g-এর জন্য (g mod ব্যাচ সাইজ) সহ একটি তালিকা

• গণনা :=l

  এর উপাদানগুলির ফ্রিকোয়েন্সি সম্বলিত একটি মানচিত্র

• g :=সংখ্যার একটি তালিকা

• একটি ফাংশন dp() সংজ্ঞায়িত করুন। এটি sm, t

  লাগবে

• যদি t এর সর্বোচ্চ 0 এর সমান হয়, তাহলে

  • রিটার্ন 0

• উত্তর :=0

• arr :=t

• k এর জন্য রেঞ্জ 0 থেকে ব্যাচসাইজ - 1, করুন

  • যদি arr[k] 0 এর মত হয়, তাহলে

    • পরবর্তী পুনরাবৃত্তির জন্য যান

  • arr[k] :=arr[k] - 1

  • উত্তর :=সর্বাধিক উত্তর এবং dp((sm + k) মোড ব্যাচসাইজ, arr)

  • arr[k] :=arr[k] + 1

• উত্তর দিন +(1 যদি sm 0 এর মত হয় অন্যথায় 0)

• মূল পদ্ধতি থেকে dp(0, g)

  রিটার্ন করুন

উদাহরণ

আরও ভালোভাবে বোঝার জন্য আসুন নিম্নলিখিত বাস্তবায়ন দেখি

from collections import Counter
def solve(batchSize, groups):
   l = [g % batchSize for g in groups]
   count = Counter(l)
   g = [count[i] for i in range(batchSize)]

   def dp(sm, t):
      if max(t) == 0:
         return 0

      ans, arr = 0, list(t)
      for k in range(batchSize):
         if arr[k] == 0:
            continue
         arr[k] -= 1
         ans = max(ans, dp((sm + k) % batchSize, arr))
         arr[k] += 1
      return ans + (sm == 0)

   return dp(0, g)

batchSize = 4
groups = [2,1,8,4,3]
print(solve(batchSize, groups))

ইনপুট

4, [2,1,8,4,3]

আউটপুট

4