【C++】ちょうどK個のコップを満たすのに必要なボトルの最小本数を求める

問題文

容量がそれぞれ与えられた N 個のコップに水を入れることを考えます。このとき、ちょうど K 個のコップを満たすために必要なボトルの最小本数を求めるのが課題です。なお、ボトル1本あたりの容量は 100 単位とします。

例

N = 5、K = 4、capacity[] = {1, 2, 3, 2, 1} の場合を見てみましょう。

• 容量の小さい方から4つのコップ(1, 1, 2, 2)を選ぶと、必要な水の総量は 6 単位になります。
• ボトル1本の容量は 100 単位あるため、わずか 1 本のボトルで十分です。

アルゴリズム

この問題は貪欲法を用いることで効率的に解けます。

• ちょうど K 個のコップを満たすには、容量の小さい方から K 個のコップを選ぶ。

• 必要なボトルの本数は、次の式で計算できます。

  (選んだ K 個のコップの容量の合計) ÷ (ボトル1本の容量) の切り上げ値

容量の小さいコップから順に選ぶことで、必要な水の総量が最小になり、結果としてボトルの本数も最小になります。

サンプルコード(C++)

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
int minBottles(int *capacity, int n, int k) {
   sort(capacity, capacity + n);
   int sum = 0;
   for (int i = 0; i < k; ++i) {
      sum += capacity[i];
   }
   return ceil((double)sum/100);
}
int main() {
   int capacity[] = {1, 2, 3, 2, 1};
   cout << "Min bottles required = " <<minBottles(capacity, 5, 4) << endl;
   return 0;
}

実行結果

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

Min bottles required = 1

計算量とまとめ

このアルゴリズムの計算量は、ソートに O(N log N)、先頭 K 個の合計算出に O(K) となり、非常に効率的です。「容量の小さいものから選ぶ」という貪欲な戦略を取るだけで、ボトルの最小本数が保証される点がポイントです。