ビンパッキング問題

ウィキペディア

ビンパッキング問題

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/06/10 05:53 UTC 版)

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

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

標準的な定義

ゲイリー、ジョンソンによる著書『Computers and Intractability』で記述されているビンパッキング問題の定義を以下で説明する。

入力：有限個のアイテム集合 $I$

この項目は、数学に関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（プロジェクト:数学／Portal:数学）。

• 表示
• 編集