C++를 사용하여 배달할 최소 항목 수입니다.

문제 설명

크기의 배열이 주어지면 N은 버킷을 나타내며 각 배열 인덱스에는 항목이 포함됩니다. 모든 항목이 배달되어야 하는 K 투어가 주어집니다. 하나의 투어에서 하나의 버킷에서만 항목을 가져갈 수 있습니다. 임무는 모든 물품이 K 투어 내에서 배송될 수 있도록 투어당 배송되어야 하는 최소 물품 수를 알려주는 것입니다.

item ={1, 3, 5, 7, 9}인 버킷 5개가 있고 투어가 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