पृष्ठों की न्यूनतम संख्या आवंटित करना एक प्रोग्रामिंग समस्या है। आइए इस समस्या पर विस्तार से चर्चा करें और देखें कि इसका समाधान क्या हो सकता है।
बयान
आपको n विभिन्न पुस्तकों के पृष्ठों की संख्या . दी गई है . साथ ही, मी छात्र . भी हैं जिन्हें किताबें सौंपी जानी हैं। पुस्तकों को पृष्ठों की संख्या के आरोही क्रम में व्यवस्थित किया गया है। और प्रत्येक विद्यार्थी को कुछ क्रमागत पुस्तकें दी जा सकती हैं। कार्यक्रम को एक छात्र द्वारा पढ़े गए पृष्ठों की अधिकतम संख्या लौटानी चाहिए जो न्यूनतम होनी चाहिए।
आइए इस समस्या को बेहतर तरीके से समझने के लिए एक उदाहरण लेते हैं,
Input : books[] = {13 , 43, 65, 87, 92}
m = 2
Output : 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<<"The number of page in books are :\n";
for(int i = 0 ; i< n; i++){
cout<<books[i]<<"\t";
}
int m = 2;
cout<<"\nMinimum number of pages = "<<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;
} आउटपुट
The number of page in books are : 13 43 65 87 92 Minimum number of pages = 179