C ++でのビンパッキング問題（使用されるビンの数を最小化する）？

それぞれ容量Cの異なる重みとビンのm個の要素が与えられた場合、実装されたビンの総数が最小になるように、各要素をビンに割り当てます。すべての要素の重みがビンの容量よりも小さいと想定する必要があります。

アプリケーション

• 複数のディスクにデータを配置します。

• トラックなどのコンテナの積み込み。

• 固定長のラジオ/テレビ局の休憩時間に広告を詰め込む。

• ジョブスケジューリング。

例

Input: weight[] = {4, 1, 8, 1, 4, 2}
Bin Capacity c = 10
Output: 2
We require at least 2 bins to accommodate all elements
First bin consists {4, 4, 2} and second bin {8, 2}

下界

ceil（）関数を使用して、必要なビンの最小数の下限をいつでも計算できます。下限は以下で指定できます-

• 最小数のビン>=ceil（（総重量）/（ビン容量））

• 上記の例では、最初の例の下限は「ceil（4 + 1 + 8 + 2 + 4 + 1）/10」=2です

• この問題には、次の近似アルゴリズムが実装されています。

オンラインアルゴリズム

これらのアルゴリズムは、要素が一度に1つずつ（順序は不明）到着するビンパッキング問題に対して実装され、次の要素を検討する前に、それぞれをビンに入れる必要があります。

次のフィット-

次の要素を処理するときは、最後の要素と同じビンに収まるかどうかを確認してください。そうでない場合にのみ、新しいビンを実装します。

以下は、このアルゴリズムのC++アプリケーションです。

// C++ program to calculate number of bins required implementing next fit algorithm.
#include <bits/stdc++.h>
using namespace std;
// We have to return number of bins needed implementing next fit online algorithm
int nextFit(int weight1[], int m, int C){
   // Result (Count of bins) and remaining capacity in current bin are initialized.
   int res = 0, bin_rem = C;
   // We have to place elements one by one
   for (int i = 0; i < m; i++) {
      // If this element can't fit in current bin
      if (weight1[i] > bin_rem) {
         res++; // Use a new bin
         bin_rem = C - weight1[i];
      }
      else
      bin_rem -= weight1[i];
      }
   return res;
}
// Driver program
int main(){
   int weight1[] = { 3, 6, 5, 8, 2, 4, 9 };
   int C = 10;
   int m = sizeof(weight1) / sizeof(weight1[0]);
   cout<< "Number of bins required in Next Fit : "
   <<nextFit(weight1, m, C);
   return 0;
}

出力

Number of bins required in Next Fit : 4

Next Fitは、単純なアルゴリズムとして扱われます。 m個の要素を処理するのに必要なのはO（m）時間とO（1）余分なスペースだけです。

First Fit-

次の要素を処理するときは、前のビンを順番に調べるかスキャンして、要素を最初に収まるビンに配置します。その時点で要素が既存のビンのいずれにも収まらない場合は、新しいビンのみを開始します。

例

// C++ program to find number of bins needed implementing First Fit algorithm.
#include <bits/stdc++.h>
using namespace std;
// We have to return number of bins needed implementing first fit online algorithm
int firstFit(int weight1[], int m, int C){
   // We have to initialize result (Count of bins)
   int res = 0;
   // We have to create an array to store remaining space in bins there can be maximum n bins
   int bin_rem[m];
   // We have to place elements one by one
   for (int i = 0; i < m; i++) {
      // We have to find the first bin that can accommodate weight1[i]
      int j;
      for (j = 0; j < res; j++) {
         if (bin_rem[j] >= weight1[i]) {
            bin_rem[j] = bin_rem[j] - weight1[i];
            break;
         }
      }
      // If no bin could accommodate weight1[i]
      if (j == res) {
         bin_rem[res] = C - weight1[i];
         res++;
      }
   }
   return res;
}
// Driver program
int main(){
   int weight1[] = { 2, 5, 4, 7, 1, 3, 8 };
   int C = 10;
   int m = sizeof(weight1) / sizeof(weight1[0]);
   cout<< "Number of bins required in First Fit : "
   <<firstFit(weight1, m, C);
   return 0;
}

出力

Number of bins required in First Fit : 4

上記のFirstFitの実装にはO（m2）時間がかかりますが、First Fitは、自己平衡二分探索木を実装するO（m log m）時間で使用できます。

ベストフィット-

コンセプトは、次のアイテムを最もタイトな位置に配置することです。つまり、少なくとも空のスペースが残るようにビンに入れます。

例

// C++ program to calculate number of bins required implementing Best fit algorithm.
#include <bits/stdc++.h>
using namespace std;
// We have to returns number of bins required implementing best fit online algorithm
int bestFit(int weight1[], int m, int C){
   // We have to initialize result (Count of bins)
   int res = 0;
   // We have to create an array to store remaining space in bins there can be maximum n bins
   int bin_rem[m];
   // Place elements one by one
   for (int i = 0; i < m; i++){
      // Find the best bin that can accomodate weight1[i]
      int j;
      // We have to initialize minimum space left and index of best bin
      int min = C + 1, bi = 0;
      for (j = 0; j < res; j++){
         if (bin_rem[j] >= weight1[i] && bin_rem[j] - weight1[i] < min) {
         bi = j;
         min = bin_rem[j] - weight1[i];
      }
   }
   // We create a new bin,if no bin could accommodate weight1[i],
   if (min == C + 1) {
         bin_rem[res] = C - weight1[i];
         res++;
      }
   else // Assign the element to best bin
   bin_rem[bi] -= weight1[i];
   }
   return res;
}
// Driver program
int main(){
   int weight1[] = { 2, 5, 4, 7, 1, 3, 8 };
   int C = 10;
   int m = sizeof(weight1) / sizeof(weight1[0]);
   cout<< "Number of bins required in Best Fit : "
   <<bestFit(weight1, m, C);
   return 0;
}

出力

Number of bins required in Best Fit : 4

ベストフィットは、自己平衡二分探索木を実装するO（m log m）時間でも適用できます。

オフラインアルゴリズム

オフラインバージョンの場合、すべての要素が事前に用意されています。オンラインアルゴリズムの問​​題は、特にシーケンスの後半で発生する場合、大きな要素をパックすることが難しいことです。入力シーケンスを並べ替え、大きな要素を最初に配置することで、これを克服できます。

ファーストフィット減少-

例

// C++ program to locate number of bins needed implementing First Fit Decreasing algorithm.
#include <bits/stdc++.h>
using namespace std;
/* We copy firstFit() from above */
int firstFit(int weight1[], int m, int C){
   // We have to initialize result (Count of bins)
   int res = 0;
   // We have to create an array to store remaining space in bins there can be maximum n bins
   int bin_rem[m];
   // We have to place elements one by one
   for (int i = 0; i < m; i++) {
      // We have to find the first bin that can accommodate weight1[i]
      int j;
      for (j = 0; j < res; j++) {
         if (bin_rem[j] >= weight1[i]) {
         bin_rem[j] = bin_rem[j] - weight1[i];
         break;
      }
   }
   // If no bin could accommodate weight1[i]
      if (j == res) {
         bin_rem[res] = C - weight1[i];
         res++;
      }
   }
return res;
}
// We have to returns number of bins required implementing first fit decreasing offline algorithm
int firstFitDec(int weight1[], int m, int C){
   // At first we sort all weights in decreasing order
   sort(weight1, weight1 + m, std::greater<int>());
   // Now we call first fit for sorted items
   return firstFit(weight1, m, C);
}
// Driver program
int main(){
   int weight1[] = { 2, 5, 4, 7, 1, 3, 8 };
   int C = 10;
   int m = sizeof(weight1) / sizeof(weight1[0]);
   cout<< "Number of bins required in First Fit "
   << "Decreasing : " << firstFitDec(weight1, m, C);
   return 0;
}

出力

Number of bins required in First Fit Decreasing : 3

First Fitを減らすと、要素が最初に並べ替えられるため、サンプル入力に対して最良の結果が生成されます。

First Fit Decreasingは、自己平衡二分探索木を実装するO（m log m）時間でも使用できます。