2020-11-18 ビンパッキング問題 ナップサック問題 パッキング問題
ビンパッキング問題
ビンパッキング問題（ビンパッキングもんだい）とは、離散数学の組合せ論の中のNP困難問題で、与えられた「荷物（重さや個数がついている）」をつめる「箱（ビンやコンテナなど）」の最小数を見つけるものである。問題を解くためにビン型（筒状型）の模型を使うのでこのように呼ばれる。
様々な解決方法（アルゴリズム）が考案されているが、あらゆる場合の箱の最小数を効率的に見つけることができるような万能なアルゴリズムはない（NP困難問題）。
関連する問題
Wikipedia英語版のほうが記事内容が圧倒的に充実している。CS関連は英語記事を参照したほうが良いかもしれない。