最も効率的な方法で問題を解決するアルゴリズムを探しています。
問題の説明:
アイテムのリスト（正の整数のみが許可されています）と、同じ容量の固定数のビンがあります。これまで分枝限定アルゴリズムについて考えてきましたが、この場合、それが最善のアプローチであるかどうかはよくわかりません。
例：
アイテムのリストが与えられた場合:
(3, 4, 4, 2, 3, 9, 2)
そして、それぞれ9個の容量の3つのビンを詰める必要がありますこれ: (アイテムの順序は関係ありません)
[3, 4, 2], [4, 3, 2], [9]
これはビンパッキング問題 (NP 完全であることはわかっています) の変種だと思いますが、使用するビンの数を最小化しようとしていないので、より良い解決策があるのではないかと思います。
これは、マルチビン パッキングの問題です。
それぞれが特定のサイズの一連のアイテムと、それぞれが特定のサイズの一連のビンがある場合、アイテムが開梱されたままにならず、ビンの容量を超えないように、アイテムがビンに分配されていますか?
一般に、NP 困難です。ただし、おおよそまたは最適に効率的に解決できる特殊なケースがいくつかあります。
Wolfgang Stille aus Göppingen の論文を参照してください
これは、箱の数が与えられた場合に、箱に詰められるアイテムの数を最大化する箱詰め問題と同じです。
最適解がリスト内の項目の数以上である場合、その解は問題の解でもあります。最適解がリスト内の項目数よりも少ない場合、問題の解決策はありません。
ビン パッキング問題は NP 困難であるため、問題に対する多項式時間解もありません。ベスト フィット、ファースト フィットなど、ビン パッキング問題用に開発されたヒューリスティックを使用できます。しかし、それらは最適解が見つかることを保証するものではありません。