Phân bổ số lượng trang tối thiểu là một vấn đề lập trình. Hãy thảo luận chi tiết vấn đề này và xem đâu có thể là giải pháp cho nó.
Tuyên bố
Bạn được cung cấp số trang của n cuốn sách khác nhau . Ngoài ra, có m sinh viên những cuốn sách sẽ được giao cho ai. Các cuốn sách được sắp xếp theo thứ tự tăng dần về số trang. Và mỗi học sinh có thể được giao một số cuốn sách liên tiếp. Chương trình phải trả về số trang tối đa mà học sinh đọc phải là số trang tối thiểu.
Hãy lấy một ví dụ để hiểu vấn đề này theo cách tốt hơn,
Input : books[] = {13 , 43, 65, 87, 92}
m = 2
Output : 179 Giải thích
Trong bài toán này, chúng ta có hai học sinh đang đọc sách. Vì vậy, có thể có những cách sau để phân phối sách giữa chúng.
TRƯỜNG HỢP 1 - [13], [43, 65, 87, 92]
Điều này làm cho số trang tối đa mà một sinh viên đọc là 13/287
TRƯỜNG HỢP 2 - [13, 43], [65, 87,92]
Điều này làm cho số trang tối đa mà một sinh viên đọc là 56/244
TRƯỜNG HỢP 3 - [13, 43, 65], [87, 92]
Điều này làm cho số trang tối đa mà một sinh viên đọc là 121/179
TRƯỜNG HỢP 4 - [13, 43, 65, 87], [92]
Điều này làm cho số trang tối đa mà một sinh viên đọc là 208/92
Trong tất cả 4 trường hợp này, kết quả là 179
Ví dụ này chắc hẳn đã làm rõ vấn đề cho bạn. Bây giờ, hãy hiểu logic đằng sau nó và tạo một chương trình cho nó.
Để giải quyết vấn đề này, một cách tiếp cận dễ dàng là sử dụng thuật toán tìm kiếm nhị phân. Đối với phương pháp tìm kiếm nhị phân này, hãy khởi tạo số trang tối thiểu và tối đa là 0 và tổng số trang của tất cả các sách. Và sau đó sửa phần giữa của các giá trị này làm kết quả trung gian sẽ thay đổi khi thuật toán tiến hành thêm.
Bây giờ, bằng cách sử dụng giá trị trung bình, chúng tôi sẽ cố gắng tìm ra khả năng để tìm ra giải pháp cuối cùng. Nếu phần giữa hiện tại có cơ hội trở thành một giải pháp, thì nửa dưới, tức là tối thiểu đến giữa đang được tìm kiếm. Nếu trường hợp này không đúng thì nửa còn lại, tức là từ trung bình đến tối đa sẽ được tìm kiếm.
Phương pháp này có thể được sử dụng để tìm giải pháp cho vấn đề này nhưng khi số lượng sinh viên tăng lên, thuật toán này có xu hướng đưa ra một giải pháp kém tin cậy hơn.
Ví dụ
#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;
} Đầu ra
The number of page in books are : 13 43 65 87 92 Minimum number of pages = 179