ビンパッキング問題#

読み: びんぱっきんぐもんだい
英名: Bin Packing Problem

いくつかの品物をビンの中に詰め込むことを考える．ビンパッキング問題は，全ての品物を詰め込むために必要なビンの本数を最も少なくするためにはどのような詰め込み方をすると良いのかを求める問題のことである．ただし，ビンと品物には容量が与えられていて，ビン（十分な数用意されているものとする）については全て同じ容量だが品物についてはそれぞれ異なるものとする．また，各ビンについて詰め込む品物の容量の合計はビンの容量以下である必要がある．

なお，ここで取り上げたのはビン・品物の容量のみを考慮し形状については考慮しない一次元のビンパッキング問題であるが，形状（幅・高さ）等を考慮した多次元のビンパッキング問題に対する研究もなされている．