पायथन में ताजा डोनट्स प्राप्त करने वाले समूहों की अधिकतम संख्या खोजने का कार्यक्रम

मान लीजिए कि हमारे पास एक मूल्य बैच आकार और एक सरणी समूह है जहां समूह [i] दर्शाता है कि समूह [i] ग्राहकों का एक समूह है जो दुकान पर जाएगा। तो एक डोनट की दुकान है जो दिए गए बैच आकार के बैचों में डोनट्स बनाती है। लेकिन उनका एक नियम है, अगले बैच के किसी भी डोनट को परोसने से पहले उन्हें एक बैच के सभी डोनट्स परोसना होगा। और प्रत्येक ग्राहक को ठीक एक डोनट मिलेगा। जब कोई समूह दुकान में प्रवेश करता है, तो किसी भी अगले समूह को संबोधित करने से पहले उस समूह के सभी ग्राहकों को सेवा दी जानी चाहिए। एक समूह खुश हो सकता है अगर वे सभी ताजा डोनट्स प्राप्त करते हैं। (दूसरे शब्दों में समूह का पहला ग्राहक अंतिम समूह से बचा हुआ डोनट स्वीकार नहीं करता है)।

हम समूहों को पुनर्व्यवस्थित कर सकते हैं, और अंत में हमें समूहों को पुनर्व्यवस्थित करने के बाद अधिकतम संभव संख्या में खुश समूहों को खोजना होगा।

इसलिए, यदि इनपुट बैचसाइज़ =4 समूह =[2,1,8,4,3] की तरह है, तो आउटपुट 4 होगा क्योंकि हम उन्हें [8,4,2,3,1] की तरह पहले पुनर्व्यवस्थित कर सकते हैं, दूसरे, तीसरे और चौथे समूह खुश हैं। हम पहले समूह के लिए डोनट्स के दो बैच बना सकते हैं, दूसरे समूह के लिए एक बैच बना सकते हैं, और एक बैच बना सकते हैं और फिर इसे तीसरे समूह को और एक को चौथे समूह को परोस सकते हैं।

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

• l :=समूहों में सभी g के लिए (g mod बैच आकार) के साथ एक सूची

• गिनती :=एक नक्शा जिसमें एल के तत्वों की आवृत्ति होती है

• g :=0 से लेकर बैच आकार के सभी i के लिए गिनती [i] की एक सूची

• एक फ़ंक्शन को परिभाषित करें dp() । इसमें sm, t

  . लगेगा

• यदि अधिकतम t 0 के समान है, तो

  • वापसी 0

• उत्तर :=0

• गिरफ्तार :=टी

• k के लिए 0 से लेकर बैच आकार -1 तक की श्रेणी में, करें

  • अगर गिरफ्तारी [के] 0 के समान है, तो

    • अगले पुनरावृत्ति के लिए जाएं

  • एआर [के]:=एआर [के] - 1

  • उत्तर:=अधिकतम उत्तर और डीपी ((एसएम + के) मॉड बैच आकार, गिरफ्तारी)

  • एआर [के]:=एआर [के] + 1

• वापसी उत्तर +(1 अगर एसएम 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