पायथन में अधिकतम औसत पास अनुपात खोजने का कार्यक्रम

मान लीजिए कि हमारे पास कक्षाओं की एक सूची है जहां कक्षाएं [i] का प्रतिनिधित्व करती हैं [pass_i, total_i] क्रमशः ith कक्षा की परीक्षा उत्तीर्ण करने वाले छात्रों की संख्या और ith कक्षा के छात्रों की कुल संख्या का प्रतिनिधित्व करती है। हमारे पास एक और मूल्य अतिरिक्त है। यह उन मेधावी छात्रों की अतिरिक्त संख्या को इंगित करता है जिन्हें उन्हें सौंपी गई किसी भी कक्षा की परीक्षा उत्तीर्ण करने की गारंटी है। हमें प्रत्येक अतिरिक्त छात्रों को एक कक्षा में इस तरह से असाइन करना होगा जो सभी कक्षाओं में उत्तीर्ण छात्रों की औसत संख्या को अधिकतम करे। एक कक्षा का उत्तीर्ण अनुपात उस कक्षा के छात्रों की संख्या से निर्धारित होता है जो कक्षा के छात्रों की कुल संख्या से विभाजित होगा। और औसत उत्तीर्ण अनुपात सभी वर्गों के उत्तीर्ण अनुपातों का योग कक्षाओं की संख्या से विभाजित होता है। हमें अतिरिक्त छात्रों को आवंटित करने के बाद अधिकतम संभव औसत पास अनुपात का पता लगाना होगा।

इसलिए, यदि इनपुट कक्षाओं की तरह है =[[2,3], [4,6], [3,3]], अतिरिक्त =3, तो आउटपुट 0.83809 होगा, क्योंकि पहली कक्षा में दो अतिरिक्त छात्र और एक जोड़ें अनुपात को अधिकतम करने के लिए दूसरी कक्षा से अतिरिक्त छात्र, इसलिए अब औसत है (4/5 + 5/7 + 3/3)/3 =0.83809।

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

h :=कक्षाओं में प्रत्येक जोड़ी (a, b) के लिए (a/b-(a + 1)/(b + 1), a, b) जैसे टुपल्स की सूची
एच को ढेर करें
जबकि अतिरिक्त गैर-शून्य है, करें
- (v, a, b) :=h के ऊपर, और इसे h से हटा दें
- (ए, बी) :=(ए + 1, बी + 1)
- (-(a + 1) /(b + 1) + a / b, a, b) ढेर में डालें
- अतिरिक्त:=अतिरिक्त - 1
एच के सभी टुपल्स से औसत वापसी

उदाहरण

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

import heapq
def solve(classes, extra):
   h = [(a / b - (a + 1) / (b + 1), a, b) for a, b in classes]
   heapq.heapify(h)
   while extra:
      v, a, b = heapq.heappop(h)
      a, b = a + 1, b + 1
      heapq.heappush(h, (-(a + 1) / (b + 1) + a / b, a, b))
      extra -= 1
   return sum(a / b for v, a, b in h) / len(h)

classes = [[2,3],[4,6],[3,3]]
extra = 3
print(solve(classes, extra))

इनपुट

[[2,3],[4,6],[3,3]], 3