Đề bài
Cho một mảng kích thước N đại diện cho các thùng, mỗi chỉ số mảng chứa số lượng hàng hóa. Cho K chuyến đi mà trong đó tất cả hàng hóa cần được giao. Cho phép lấy hàng chỉ từ một thùng trong 1 chuyến. Nhiệm vụ là cho biết số lượng hàng hóa tối thiểu cần giao mỗi chuyến để tất cả hàng hóa có thể được giao trong K chuyến.
Nếu có 5 thùng với hàng hóa = {1, 3, 5, 7, 9} và 10 chuyến thì có thể giao 3 hàng mỗi chuyến. Bằng cách giao 3 hàng mỗi lần:
- Thùng 1 kích thước 1 do đó số chuyến cần = 1
- Thùng 2 kích thước 3 do đó số chuyến cần = 1
- Thùng 3 kích thước 5 do đó số chuyến cần = 2 (3 + 2 hàng mỗi chuyến)
- Thùng 4 kích thước 7 do đó số chuyến cần = 3 (3 + 3 + 1 hàng mỗi chuyến)
- Thùng 5 kích thước 9 do đó số chuyến cần = 3 (3 + 3 + 3 hàng mỗi chuyến)
Tổng số chuyến = 10
Thuật toán
1. Tìm số lượng hàng hóa tối thiểu cần phân phối mỗi lần giao 2. Duyệt từ 1 đến giá trị tối đa hàng trong một thùng và tính số chuyến cần cho mỗi thùng và tìm tổng số chuyến cho việc giao hoàn toàn 3. Giá trị đầu tiên có số chuyến nhỏ hơn hoặc bằng K cho số lượng cần tìm
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; }
Kết quả
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