ビンパッキング問題

ビンパッキング問題（ビンパッキングもんだい）とは、離散数学の組合せ論の中のNP困難問題で、与えられた「荷物（重さや個数がついている）」をつめる「箱（ビンやコンテナなど）」の最小数を見つけるものである。問題を解くためにビン型（筒状型）の模型を使うのでこのように呼ばれる。

様々な解決方法（アルゴリズム）が考案されているが、あらゆる場合の箱の最小数を効率的に見つけることができるような万能なアルゴリズムはない（NP困難問題）。

単純な例

8台の新車をトラックで移動する。新車の重量はそれぞれ100キログラム単位で 33, 61, 58, 41, 50, 21, 60, 64 である。各トラックが、12,000 kg の重量まで運べるとき、全ての新車を一度に移動させるのに必要とされるトラックの最小数は、いくつであるか考える。まず、トラックを容量120のビンとし、新車は、そのビンに詰める荷物とする。具体的に調べることによって必要な箱の最小数を見つけることができるが、ここでは決められた手順（アルゴリズム）を使って解いていく。2つのアルゴリズムを紹介する。

アルゴリズムA

荷物を空いている容量が最大のビンに詰める。
どのビンにも荷物が入らないとき、新しいビンに詰める。

ビン1  ビン2  ビン3  ビン4  ビン5
|00|   |00|  |00|   |00|  |00|
|61|   |41|  |21|   |00|  |00|
|33|   |58|  |50|   |60|  |64|

この方法だと、ビンは5個（つまりトラック5台）必要となる。

アルゴリズムB

荷物を空いている容量が最小のビンに詰める。
どのビンにも荷物が入らないとき、新しいビンに詰める。

ビン1  ビン2  ビン3  ビン4
|00|   |21|  |00|   |00|
|61|   |41|  |60|   |00|
|33|   |58|  |50|   |64|

この方法だと、必要なビンは4個（トラック4台）である。

2つを比べるとAよりもBの方が良いアルゴリズムである。実際にはもっと優良なアルゴリズムがあるかもしれない。

単純な例

関連項目