การจัดสรรจำนวนหน้าขั้นต่ำเป็นปัญหาการเขียนโปรแกรม มาพูดคุยกันถึงปัญหานี้โดยละเอียดและดูว่ามีวิธีแก้ไขอย่างไร
คำชี้แจง
คุณจะได้รับ จำนวนหน้าของหนังสือ 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
