【C++】K回の配達ですべての荷物を届けるための1回あたり最小運搬個数を求める

問題の概要

サイズ N の配列が与えられます。この配列の各インデックスは「バケツ」を表しており、それぞれのバケツにはいくつかの荷物（アイテム）が入っています。ここで、K 回の配達ですべての荷物を届け終えるという条件が課されます。ただし、1 回の配達で荷物を取り出せるのは1 つのバケツからだけというルールがあります。

このとき、「すべての荷物を K 回以内で配達し切るために、1 回あたり最低何個の荷物を運べばよいか」を求めるのが本問題です。

具体例

バケツが 5 つあり、それぞれに入っている荷物の数が {1, 3, 5, 7, 9}、配達可能な回数が 10 回であるとします。この場合、1 回あたり 3 個ずつ運べば全体をちょうど 10 回で配達できます。

• 1 番目のバケツ：1 個入り → 必要な配達回数 = 1 回
• 2 番目のバケツ：3 個入り → 必要な配達回数 = 1 回
• 3 番目のバケツ：5 個入り → 必要な配達回数 = 2 回（3 個 + 2 個）
• 4 番目のバケツ：7 個入り → 必要な配達回数 = 3 回（3 個 + 3 個 + 1 個）
• 5 番目のバケツ：9 個入り → 必要な配達回数 = 3 回（3 個 + 3 個 + 3 個）

合計の配達回数 = 10 回

アルゴリズム

1. 1 回の配達で運ぶべき最小の荷物数を求めます。
2. 1 からバケツ内の最大値まで順に候補となる値を試し、その値で各バケツを配り切るのに必要な配達回数を計算し、合計を求めます。
3. 合計の配達回数が K 以下になる最初の値が答えとなります。

C++での実装例

#include <iostream>
#include <climits>
#include <cmath>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int minItemsDelivered(int *arr, int n, int k){
    // バケツ内の最大値を求める
    int maxElement = INT_MIN;
    for (int i = 0; i < n; ++i) {
        maxElement = max(maxElement, arr[i]);
    }
    // 1個ずつから最大値まで順に試す
    for (int i = 1; i <= maxElement; ++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;
            }
        }
        // 配達回数がK以下ならその値が答え
        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 = " <<
    minItemsDelivered(arr, SIZE(arr), k) << endl;
    return 0;
}

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Minimum items to be delivered = 3

計算量と改善のポイント

この実装では、候補の値ごとにすべてのバケツを走査するため、時間計算量は O(N × M) となります（M はバケツ内の最大値）。候補の値が大きくなるほど必要な配達回数は単調に減少する性質があるため、線形探索の代わりに二分探索を使えば、時間計算量を O(N log M) まで削減でき、大規模な入力に対しても高速に動作します。