C++で解くビンパッキング問題：使用するビン（容器）の数を最小化するアルゴリズム徹底解説

異なる重みを持つ m 個の要素と、容量 C のビン（容器）が与えられたとき、すべての要素をビンに割り当て、使用するビンの総数を最小限に抑えることを目指します。ここでは、すべての要素の重みがビンの容量以下であると仮定します。

この問題は「ビンパッキング問題」と呼ばれ、NP困難な組合せ最適化問題の一つです。そのため、実用的には近似アルゴリズムを用いて良好な解を高速に求めるアプローチが一般的です。

応用例

• 複数のディスクへのデータ配置
• トラックなどコンテナへの積み込み
• ラジオ・テレビ局の固定長スポット枠への広告詰め込み
• ジョブスケジューリング

例

入力: weight[] = {4, 1, 8, 1, 4, 2}
ビン容量 c = 10
出力: 2
すべての要素を収めるには少なくとも2つのビンが必要です。
1つ目のビンは {4, 4, 2}、2つ目のビンは {8, 2} となります。

下界（必要なビン数の最小値の見積もり）

ceil() 関数を使えば、必要な最小ビン数の下界を常に計算できます。下界は次のように表されます。

• 最小ビン数 >= ceil(（総重量） / （ビン容量）)
• 上記の例では、「ceil((4 + 1 + 8 + 2 + 4 + 1) / 10)」= 2 が下界になります。

オンラインアルゴリズム

これらのアルゴリズムは、要素が一度に1つずつ（順序不明で）到着し、次の要素を考慮する前に各要素を必ずどこかのビンに配置しなければならない、という状況に対応するものです。

Next Fit（ネクストフィット）

次の要素を処理する際、直前の要素と同じビンに入るかどうかだけを確認します。入らなかった場合のみ新しいビンを使用します。

// Next Fit アルゴリズムで必要なビン数を計算する C++ プログラム
#include <bits/stdc++.h>
using namespace std;

// Next Fit オンラインアルゴリズムで必要なビン数を返す
int nextFit(int weight1[], int m, int C){
    // 結果（ビン数）と現在のビンの残り容量を初期化
    int res = 0, bin_rem = C;
    // 要素を1つずつ配置する
    for (int i = 0; i < m; i++) {
        // この要素が現在のビンに入らない場合
        if (weight1[i] > bin_rem) {
            res++; // 新しいビンを使用
            bin_rem = C - weight1[i];
        }
        else
            bin_rem -= weight1[i];
    }
    return res;
}

// ドライバプログラム
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（ファーストフィット）

次の要素を処理する際、既存のビンを先頭から順に走査し、最初に収まるビンに要素を配置します。どの既存ビンにも入らない場合は、新しくビンを作成します。

// First Fit アルゴリズムで必要なビン数を求める C++ プログラム
#include <bits/stdc++.h>
using namespace std;

// First Fit オンラインアルゴリズムで必要なビン数を返す
int firstFit(int weight1[], int m, int C){
    // 結果（ビン数）を初期化
    int res = 0;
    // 各ビンの残り容量を格納する配列（最大 n 個のビンがあり得る）
    int bin_rem[m];
    // 要素を1つずつ配置する
    for (int i = 0; i < m; i++) {
        // 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;
            }
        }
        // どのビンにも weight1[i] を収容できなかった場合
        if (j == res) {
            bin_rem[res] = C - weight1[i];
            res++;
        }
    }
    return res;
}

// ドライバプログラム
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

上記の First Fit の実装は O(m²) の時間計算量を持ちますが、自己平衡二分探索木を利用することで O(m log m) 時間で実行できます。

Best Fit（ベストフィット）

この手法の考え方は、次の要素を「最もきつく」収まる場所に配置するというものです。つまり、配置後に残る空き容量が最小になるビンを選びます。

// Best Fit アルゴリズムで必要なビン数を計算する C++ プログラム
#include <bits/stdc++.h>
using namespace std;

// Best Fit オンラインアルゴリズムで必要なビン数を返す
int bestFit(int weight1[], int m, int C){
    // 結果（ビン数）を初期化
    int res = 0;
    // 各ビンの残り容量を格納する配列（最大 n 個のビンがあり得る）
    int bin_rem[m];
    // 要素を1つずつ配置する
    for (int i = 0; i < m; i++){
        // weight1[i] を収容できる最適なビンを探す
        int j;
        // 最小残り空き容量と最適ビンのインデックスを初期化
        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];
            }
        }
        // どのビンにも weight1[i] を収容できなければ新しいビンを作成
        if (min == C + 1) {
            bin_rem[res] = C - weight1[i];
            res++;
        }
        else // 最適なビンに要素を割り当てる
            bin_rem[bi] -= weight1[i];
    }
    return res;
}

// ドライバプログラム
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

Best Fit も、自己平衡二分探索木を利用すれば O(m log m) 時間で実行可能です。

オフラインアルゴリズム

オフライン版では、すべての要素を事前に把握しています。オンラインアルゴリズムの課題は、特に大きな要素がシーケンスの後半に現れた場合、その配置が難しくなることです。この問題は、入力シーケンスをソートして大きな要素から先に配置することで克服できます。

First Fit Decreasing（ファーストフィット・ディクリージング）

// First Fit Decreasing アルゴリズムで必要なビン数を求める C++ プログラム
#include <bits/stdc++.h>
using namespace std;

/* 上記の firstFit() を流用 */
int firstFit(int weight1[], int m, int C){
    // 結果（ビン数）を初期化
    int res = 0;
    // 各ビンの残り容量を格納する配列（最大 n 個のビンがあり得る）
    int bin_rem[m];
    // 要素を1つずつ配置する
    for (int i = 0; i < m; i++) {
        // 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;
            }
        }
        // どのビンにも weight1[i] を収容できなかった場合
        if (j == res) {
            bin_rem[res] = C - weight1[i];
            res++;
        }
    }
    return res;
}

// First Fit Decreasing オフラインアルゴリズムで必要なビン数を返す
int firstFitDec(int weight1[], int m, int C){
    // まずすべての重みを降順にソート
    sort(weight1, weight1 + m, std::greater<int>());
    // ソート済みの要素に対して First Fit を呼び出す
    return firstFit(weight1, m, C);
}

// ドライバプログラム
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 Decreasing では、要素を事前にソートするため、サンプル入力に対して最良の結果（3つのビン）が得られました。

First Fit Decreasing も、自己平衡二分探索木を利用すれば O(m log m) 時間で実行できます。

まとめ

ビンパッキング問題はNP困難であるため、厳密な最適解を求めるのは大規模データでは非現実的です。Next Fit は高速だが精度は低く、First Fit・Best Fit はバランス型、First Fit Decreasing はオフライン処理が可能な場合に最も良い結果をもたらす傾向があります。用途やデータの性質に応じて適切なアルゴリズムを選択しましょう。