ন্যূনতম পৃষ্ঠা বণ্টন একটি প্রোগ্রামিং সমস্যা। এটিকে বিস্তারিত আলোচনা করি এবং সমাধান দেখি।
সমস্য্যা বিবরণ
আপনাকে nটি বইয়ের পৃষ্ঠা সংখ্যা দেওয়া আছে। এছাড়া mটি ছাত্র আছে যাদের বই বাঁটা দিতে হবে। বইগুলো পৃষ্ঠা সংখ্যা অনুযায়ী আরোহী ক্রমে সাজানো আছে। এবং প্রতিটি ছাত্রকে কিছু সান্তানিক বই বাঁটা দিতে হবে। প্রোগ্রামটি সেই সর্বোচ্চ পৃষ্ঠা সংখ্যা ফেরত দেবে যা একটি ছাত্র পড়বে এবং যেটি ন্যূনতম হবে।
উদাহরণ দিয়ে বুঝি:
Input: books[] = {13, 43, 65, 87, 92}, m = 2
Output: 179
ব্যাখ্যা
দুইজন ছাত্র বই পড়বে। বই বাঁটার সম্ভাব্য উপায়গুলো:
CASE 1 - [13], [43, 65, 87, 92] - সর্বোচ্চ পৃষ্ঠা: 13 / 287
CASE 2 - [13, 43], [65, 87, 92] - সর্বোচ্চ পৃষ্ঠা: 56 / 244
CASE 3 - [13, 43, 65], [87, 92] - সর্বোচ্চ পৃষ্ঠা: 121 / 179
CASE 4 - [13, 43, 65, 87], [92] - সর্বোচ্চ পৃষ্ঠা: 208 / 92
এই ৪টি কেস থেকে ফলাফল ১৭৯।
এখন লজিক বুঝি। এই সমস্যা সমাধানের সহজ পদ্ধতি হলো বাইনারি সার্চ অ্যালগরিদম। এতে ন্যূনতম ও সর্বোচ্চ পৃষ্ঠা ০ এবং সব বইয়ের পৃষ্ঠার যোগফল হিসেবে ইনিশিয়ালাইজ করুন। তারপর মিড ভ্যালুকে ইন্টারমিডিয়েট রেজাল্ট হিসেবে ফিক্স করুন যা অ্যালগরিদম এগিয়ে যাওয়ার সাথে সাথে পরিবর্তন হবে।
মিড ভ্যালু ব্যবহার করে চূড়ান্ত সমাধানের সম্ভাবনা খুঁজে বের করুন। যদি করেন্ট মিড সমাধান হতে পারে, তবে নিচের आधা (minimum থেকে mid) সার্চ করুন। না হলে উপরের आधা (mid থেকে maximum) সার্চ করুন।
ছাত্র সংখ্যা বাড়লে এই অ্যালগরিদম কম নির্ভরযোগ্য সমাধান দিতে পারে।
C++ প্রোগ্রাম উদাহরণ
#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<The number of page in books are :
13 43 65 87 92
Minimum number of pages = 179
