समस्या कथन
आकार की एक सरणी को देखते हुए, एन बाल्टी का प्रतिनिधित्व करता है, प्रत्येक सरणी सूचकांक जिसमें आइटम होते हैं। के दौरों को देखते हुए जिसमें सभी वस्तुओं की डिलीवरी की आवश्यकता है। 1 टूर में केवल एक बाल्टी से आइटम लेने की अनुमति है। कार्य प्रति टूर डिलीवर करने के लिए आवश्यक वस्तुओं की न्यूनतम संख्या बताना है ताकि सभी आइटम K टूर्स के भीतर डिलीवर किए जा सकें।
अगर आइटम के साथ 5 बाल्टी हैं ={1, 3, 5, 7, 9} और 10 टूर तो हम एक बार में 3 आइटम डिलीवर करके प्रति टूर 3 आइटम डिलीवर कर सकते हैं,
-
पहली बाल्टी का आकार 1 है इसलिए आवश्यक यात्राओं की संख्या =1
-
दूसरी बाल्टी का आकार 3 है इसलिए आवश्यक यात्राओं की संख्या =1
-
तीसरी बाल्टी का आकार 5 है इसलिए आवश्यक यात्राओं की संख्या =2 (3 + 2 आइटम प्रति टूर)
-
चौथी बाल्टी का आकार 7 है इसलिए आवश्यक यात्राओं की संख्या =3 (3 + 3 + 1 आइटम प्रति टूर)
-
5वीं बाल्टी का आकार 9 है इसलिए आवश्यक यात्राओं की संख्या =3 (3 + 3 + 3 आइटम प्रति टूर)
यात्राओं की कुल संख्या =10
एल्गोरिदम
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
उदाहरण
#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;
} आउटपुट
जब आप उपरोक्त प्रोग्राम को संकलित और निष्पादित करते हैं। यह निम्न आउटपुट उत्पन्न करता है -
Minimum items to be delivered = 3