私が箱と言うとき、私は輸送箱について話している.
ランダムなサイズの小さなアイテムがいくつかあり、できるだけ少ない箱に詰める必要があります。最適なボックス サイズを知る必要があります。
スペースを最適に使用するために必要なボックス サイズを計算できるアルゴリズムはありますか? できるだけ少ないボックスに多くのアイテムを収めるため。
利用可能な箱のサイズは、私が利用できる在庫からのものです。例として、限られた数の構成されたボックス サイズを作成できます。
これはビンパッキング問題の一般化であり、 NP困難であることを意味します。
これを確認するために、すべてのビンとパッケージの幅と高さが同じであり、さらにすべてのビン（パッケージではない）の長さが同じであると想像してください。次に、これは1次元の問題です。サイズVのビンと、サイズa 1、a 2、...、anのパッケージがあります。この単純化されたケースは、まさにビンパッキング問題です。したがって、あなたの問題に対する迅速な解決策は、ビンパッキングに対する迅速な解決策を私たちに与えるので、あなたの問題は少なくとも同じくらい難しいです。ビンパッキングはNP困難であるため、問題も同様です。
ただし、利用可能な近似アルゴリズムがいくつかあります。たとえば、単純なファーストフィットアルゴリズム（すべてのアイテムを最初のビンに入れる）が、最適なソリューションの2倍より悪くなることは決してないことを示すのは簡単です。
同様の「FirstFitDecreasing」アルゴリズム（アイテムを降順で並べ替えてから、すべてのアイテムを最初のビンに入れる）はさらに優れており、最適なソリューションの約25％以内に収まることが保証されます。MFFDと呼ばれるもう1つの少し複雑なアルゴリズムもあり、これは約20％以内であることを保証します。
そしてもちろん、7つのボックスしかないので、いつでもソリューションを総当たり攻撃することができます。これには約7nステップ（アイテムの数）が必要になるためn、このソリューションは12個以上のアイテムでは実行できません。
ナップザック問題のバリエーションについて説明しました。問題へのアプローチの詳細については、ウィキペディアの記事を参照してください。