न्यूनतम पृष्ठों का आवंटन एक प्रोग्रामिंग समस्या है। आइए इस समस्या पर विस्तार से चर्चा करते हैं और देखते हैं कि इसका समाधान क्या हो सकता है।
कथन
आपको n विभिन्न पुस्तकों के पृष्ठों की संख्या दी गई है। साथ ही, m छात्र हैं जिन्हें पुस्तकें आवंटित की जानी हैं। पुस्तकें पृष्ठों की संख्या के आरोही क्रम में व्यवस्थित हैं। और प्रत्येक छात्र को कुछ लगातार पुस्तकें आवंटित की जा सकती हैं। प्रोग्राम को एक छात्र द्वारा पढ़े गए पृष्ठों की अधिकतम संख्या वापस करनी चाहिए जो न्यूनतम होनी चाहिए।
आइए एक उदाहरण लेते हैं इस समस्या को बेहतर तरीके से समझने के लिए,
इनपुट: books[] = {13, 43, 65, 87, 92} m = 2 आउटपुट: 179 व्याख्या
इस समस्या में, हमारे पास दो छात्र हैं जो पुस्तकें पढ़ रहे हैं। तो, पुस्तकों को उनके बीच वितरित करने के निम्नलिखित तरीके हो सकते हैं।
केस 1 - [13], [43, 65, 87, 92]
इससे एक छात्र द्वारा पढ़े गए पृष्ठों की अधिकतम संख्या 13/287 होती है
केस 2 - [13, 43], [65, 87, 92]
इससे एक छात्र द्वारा पढ़े गए पृष्ठों की अधिकतम संख्या 56/244 होती है
केस 3 - [13, 43, 65], [87, 92]
इससे एक छात्र द्वारा पढ़े गए पृष्ठों की अधिकतम संख्या 121/179 होती है
केस 4 - [13, 43, 65, 87], [92]
इससे एक छात्र द्वारा पढ़े गए पृष्ठों की अधिकतम संख्या 208/92 होती है
इन सभी 4 मामलों में से, परिणाम 179 है
इस उदाहरण ने समस्या को आपके लिए स्पष्ट कर दिया होगा। अब, आइए इसके पीछे के तर्क को समझते हैं और इसके लिए एक प्रोग्राम बनाते हैं।
इस समस्या को हल करने का एक आसान दृष्टिकोण बाइनरी सर्च एल्गोरिदम का उपयोग करना है। इस बाइनरी सर्च दृष्टिकोण के लिए, न्यूनतम और अधिकतम पृष्ठों की संख्या को 0 और सभी पुस्तकों के पृष्ठों के योग के रूप में इनिशियलाइज़ करें। और फिर इन मानों के मध्य को मध्यवर्ती परिणाम के रूप में तय करें जो एल्गोरिदम के आगे बढ़ने पर बदल जाएगा।
अब, मध्य मान का उपयोग करके हम अंतिम समाधान खोजने की संभावना का पता लगाने की कोशिश करेंगे। यदि वर्तमान मध्य के समाधान बनने की संभावना है, तो निचला आधा यानी न्यूनतम से मध्य तक खोजा जाता है। यदि यह मामला सही नहीं है तो दूसरा आधा यानी मध्य से अधिकतम तक खोजा जाता है।
इस विधि का उपयोग इस समस्या का समाधान खोजने के लिए किया जा सकता है लेकिन जैसे-जैसे छात्रों की संख्या बढ़ती है, यह एल्गोरिदम कम विश्वसनीय समाधान प्रदान करने लगता है।
उदाहरण
#include<bits/stdc++.h> using namespace std; bool isPossible(int arr[], int n, int m, int curr_min) ; int min_pages(int arr[], int n, int m) ; int main(){ int n = 5; int books[] = {13, 43, 65, 87, 92}; cout<<"पुस्तकों में पृष्ठों की संख्या हैं:\n"; for(int i = 0; i< n; i++){ cout<<books[i]<<"\t"; } int m = 2; cout<<"\nन्यूनतम पृष्ठों की संख्या = "<<min_pages(books, n, m)<<endl; return 0; } bool isPossible(int arr[], int n, int m, int curr_min){ int studentsRequired = 1; int curr_sum = 0; for (int i = 0; i < n; i++){ if (arr[i] > curr_min) return false; if (curr_sum + arr[i] > curr_min){ studentsRequired++; curr_sum = arr[i]; if (studentsRequired > m) return false; } else curr_sum += arr[i]; } return true; } int min_pages(int arr[], int n, int m){ long long sum = 0; if (n < m) return -1; for (int i = 0; i < n; i++) sum += arr[i]; int minimum = 0, maximum = sum; int result = INT_MAX; while (minimum <= maximum){ int mid = (minimum + maximum) / 2; if (isPossible(arr, n, m, mid)){ result = min(result, mid); maximum = mid - 1; } else minimum = mid + 1; } return result; } आउटपुट
पुस्तकों में पृष्ठों की संख्या हैं: 13 43 65 87 92 न्यूनतम पृष्ठों की संख्या = 179
