C++ में वितरित किए जाने वाले न्यूनतम आइटम

समस्या कथन

आकार N की एक सरणी दी गई है जो बाल्टियों (buckets) को दर्शाती है, प्रत्येक सरणी इंडेक्स में आइटम हैं। K टूर दिए गए हैं जिनके भीतर सभी आइटम वितरित किए जाने हैं। 1 टूर में केवल एक बाल्टी से आइटम लेना अनुमत है। कार्य प्रति टूर वितरित किए जाने वाले न्यूनतम आइटम की संख्या बताना है ताकि सभी आइटम K टूर के भीतर वितरित किए जा सकें।

यदि 5 बाल्टियों में आइटम = {1, 3, 5, 7, 9} हैं और 10 टूर हैं, तो हम प्रति टूर 3 आइटम वितरित कर सकते हैं।

एल्गोरिदम

1. प्रति डिलीवरी वितरित किए जाने वाले न्यूनतम आइटम ढूंढें
2. 1 से बाल्टी में अधिकतम आइटम मान तक पुनरावृति करें और प्रत्येक बाल्टी के लिए आवश्यक टूर की गणना करें और कुल टूर ढूंढें
3. पहला ऐसा मान जिसका टूर K से कम या बराबर हो, आवश्यक संख्या देता है

C++ उदाहरण

#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[j] % 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