পৃষ্ঠাগুলির একটি ন্যূনতম সংখ্যা বরাদ্দ একটি প্রোগ্রামিং সমস্যা. আসুন এই সমস্যাটি বিস্তারিতভাবে আলোচনা করি এবং এর সমাধান কি হতে পারে।
বিবৃতি
আপনাকে n ভিন্ন বইয়ের পৃষ্ঠার সংখ্যা দেওয়া হয়েছে . এছাড়াও, সেখানে m ছাত্র আছে৷ যাকে বই বরাদ্দ করা হবে। বইগুলো পৃষ্ঠা সংখ্যার ঊর্ধ্বক্রম অনুসারে সাজানো হয়েছে। এবং প্রত্যেক শিক্ষার্থীকে পরপর কিছু বই বরাদ্দ করা যেতে পারে। প্রোগ্রামটি একজন শিক্ষার্থীর দ্বারা পড়া সর্বাধিক সংখ্যক পৃষ্ঠা ফেরত দেবে যা সর্বনিম্ন হওয়া উচিত।
এই সমস্যাটিকে আরও ভালভাবে বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
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
