【C++】ビンパッキングアルゴリズムの実装方法とサンプルプログラム

ビンパッキング問題とは

ビンパッキング問題（Bin Packing Problem）は、切断在庫問題（カッティングストック問題）の一種です。異なる体積を持つ複数の物体を、それぞれ体積Vの容器（ビン）に収めるとき、使用するビンの本数が最小になるように詰め込むことを目指します。

計算複雑性理論の観点では、ビンパッキング問題はNP困難（NP-hard）な組合せ最適化問題に分類されます。そのため、大規模なインスタンスに対して厳密な最適解を効率的に求めることは困難で、実際には貪欲法などの近似解法が広く利用されています。

なお、ビンの数を1つに制限し、各アイテムが「体積」と「価値」の両方の属性を持つ場合、ビンに詰め込めるアイテムの価値の合計を最大化する問題へと変化します。これが有名な「ナップサック問題」です。

アルゴリズム

ここで紹介するのは、先頭のアイテムから順にビンへ詰め込んでいくシンプルな貪欲法です。現在のビンの残り容量を表す変数mを管理し、次のアイテムが入りきる場合はそのまま詰め込み、入りきらない場合には新しいビンを用意して同じアイテムを再度処理します。最後に、必要となったビンの総数を出力します。

開始
　　Binpacking(配列へのポインタ, ビンのサイズ, アイテム数)
　　bincount、m、i を宣言
　　bincount = 1、m = size で初期化
　　i = 0 からアイテム数まで繰り返し
　　if (m - *(a + i) > 0) の場合
　　　　m = m - *(a + i)
　　　　継続
　　それ以外の場合
　　　　bincount を増加
　　　　m = size に戻す
　　　　i をデクリメント
　　必要なビンの数を出力
終了

サンプルコード（C++）

#include<iostream>
using namespace std;
void binPacking(int *a, int size, int n) {
    int binCount = 1;
    int m = size;
    for (int i = 0; i < n; i++) {
        if (m - *(a + i) > 0) {
            m -= *(a + i);
            continue;
        } else {
            binCount++;
            m = size;
            i--;
        }
    }
    cout << "Number of bins required: " << binCount;
}
int main(int argc, char **argv) {
   cout << "Enter the number of items in Set: ";
   int n;
   cin >> n;
   cout << "Enter " << n << " items:";
   int a[n];
   for (int i = 0; i < n; i++)
      cin >> a[i];
   cout << "Enter the bin size: ";
   int size;
   cin >> size;
   binPacking(a, size, n);
}

実行結果

Enter the number of items in Set: 3
Enter 3 items:4
6
7
Enter the bin size: 26
Number of bins required: 1

この例では、サイズ4、6、7という3つのアイテムを、容量26のビンに詰め込んでいます。合計は4＋6＋7＝17となり、容量26以内にすべて収まるため、必要なビンは1つだけで済んでいます。

なお、上記のコードで使用している可変長配列（int a[n]）は標準C++の仕様ではなくGCCの拡張機能のため、移植性を重視する場合はstd::vectorの利用を推奨します。