Tuyên bố vấn đề
Cho một mảng có kích thước, N đại diện cho các nhóm, mỗi chỉ số mảng chứa các mục. Cho K chuyến tham quan trong đó tất cả các mặt hàng cần được giao. Chỉ được phép lấy đồ từ một thùng trong 1 lần tham quan. Nhiệm vụ là cho biết số lượng tối thiểu các mặt hàng cần được giao cho mỗi chuyến tham quan để tất cả các mặt hàng có thể được giao trong K chuyến tham quan.
Nếu có 5 nhóm với mục ={1, 3, 5, 7, 9} và 10 chuyến tham quan thì chúng tôi có thể giao 3 mặt hàng cho mỗi chuyến tham quan Bằng cách giao 3 mặt hàng cùng một lúc,
-
Kích thước nhóm thứ nhất là 1 do đó số lượng chuyến tham quan được yêu cầu =1
-
Kích thước nhóm thứ 2 là 3 do đó số lượng chuyến tham quan được yêu cầu =1
-
Kích thước nhóm thứ 3 là 5 do đó số lượng chuyến tham quan được yêu cầu =2 (3 + 2 món trên mỗi chuyến tham quan)
-
Kích thước nhóm thứ 4 là 7 do đó số lượng chuyến tham quan được yêu cầu =3 (3 + 3 + 1 mục mỗi chuyến tham quan)
-
Kích thước nhóm thứ 5 là 9 do đó số lượng chuyến tham quan được yêu cầu =3 (3 + 3 + 3 món cho mỗi chuyến tham quan)
Tổng số chuyến tham quan =10
Thuật toán
1. find the minimum number of items to be distributed per delivery 2. iterate from 1 to the maximum value of items in a bucket and calculate the number of tours required for each bucket and find the total number of tours for complete delivery 3. The first such value with tours less than or equals K gives the required number
Ví dụ
#include <iostream>
#include <climits>
#include <cmath>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int minItemsDeliveried(int *arr, int n, int k){
int maxElement = INT_MIN;
for (int i = 0; i < n; ++i) {
maxElement = max(maxElement, arr[i]);
}
for (int i = 1; i < maxElement + 1; ++i) {
int tours = 0;
for (int j = 0; j < n; ++j) {
if (arr[i] % i == 0) {
tours += arr[j] / i;
} else {
tours += floor(arr[j] / i) + 1;
}
}
if (tours <= k) {
return i;
}
}
return 1;
}
int main(){
int arr[] = {1, 3, 5, 7, 9};
int k = 10;
cout << "Minimum items to be delivered = " <<
minItemsDeliveried(arr, SIZE(arr), k) << endl;
return 0;
} Đầu ra
Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -
Minimum items to be delivered = 3