C++を使用して配信されるアイテムの最小数。

問題の説明

サイズの配列が与えられると、Nはバケットを表し、各配列インデックスにはアイテムが含まれます。すべてのアイテムを配達する必要があるKツアーを考えます。 1回のツアーで1つのバケットからのみアイテムを取得できます。タスクは、すべてのアイテムをKツアー内で配信できるように、ツアーごとに配信する必要のあるアイテムの最小数を指示することです。

アイテム={1、3、5、7、9}のバケットが5つあり、ツアーが10の場合、一度に3つのアイテムを配信することで、ツアーごとに3つのアイテムを配信できます。

• 最初のバケットサイズは1であるため、必要なツアーの数=1

• 2番目のバケットサイズは3であるため、必要なツアーの数=1

• 3番目のバケットサイズは5であるため、必要なツアーの数=2（ツアーごとに3 + 2アイテム）

• 4番目のバケットサイズは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