ビンパッキングアルゴリズム（びんぱっきんぐあるごりずむ）
最終更新：2026/4/27
ビンパッキングアルゴリズムは、異なるサイズのアイテムを、容量が限られた複数のビンに、使用するビンの数を最小化するように詰め込むための最適化アルゴリズムである。
別名・同義語 詰め込み問題ナップサック問題（関連問題）
ポイント
この問題はNP困難であり、厳密解を求めるのは難しいが、様々な近似アルゴリズムが存在する。現実の資源配分問題に応用される。
ビンパッキングアルゴリズムとは
ビンパッキングアルゴリズムは、組合せ最適化問題の一種であり、与えられたサイズのアイテムを、容量が固定されたビンに詰め込む際に、使用するビンの数を最小化することを目的とします。この問題は、現実世界の様々な資源配分問題に応用できます。例えば、トラックへの荷物の積み込み、メモリの割り当て、ファイルのディスクへの保存などが挙げられます。
問題の複雑性
ビンパッキング問題はNP困難であることが知られています。これは、問題の規模が大きくなるにつれて、厳密解を求めるための計算時間が指数関数的に増加することを意味します。そのため、現実的な時間内に最適な解を見つけることは困難な場合があります。
代表的なアルゴリズム
厳密解を求めるのが難しいことから、様々な近似アルゴリズムが提案されています。代表的なアルゴリズムとしては、以下のようなものがあります。
- First-Fitアルゴリズム: アイテムを順番に取り出し、最初に収まるビンに詰め込む。
- Best-Fitアルゴリズム: アイテムを順番に取り出し、最も隙間が少なくなるビンに詰め込む。
- Worst-Fitアルゴリズム: アイテムを順番に取り出し、最も隙間が大きいビンに詰め込む。
- First-Fit Decreasingアルゴリズム: アイテムをサイズが大きい順にソートし、First-Fitアルゴリズムを適用する。
- Best-Fit Decreasingアルゴリズム: アイテムをサイズが大きい順にソートし、Best-Fitアルゴリズムを適用する。
一般的に、First-Fit DecreasingアルゴリズムやBest-Fit Decreasingアルゴリズムの方が、First-FitアルゴリズムやBest-Fitアルゴリズムよりも良い結果が得られる傾向があります。
応用例
ビンパッキングアルゴリズムは、以下のような様々な分野で応用されています。