さまざまなサイズのデータの塊を複数のビンに梱包します
https://stackoverflow.com/questions/4521390
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
編集：この問題は「ストックの問題を切断」と呼ばれるようです
ビン内のチャンクの（スペース）最適な配置を提供するアルゴリズムが必要です。 1つの方法は、最初に大きなチャンクを置くことです。ただし、この例では、そのアルゴリズムがどのように失敗するかをご覧ください。
Chunks Bins
-----------------------------
AAA BBB CC DD ( ) ( )
Algorithm Result
-----------------------------
biggest first (AAABBB ) (CC )
optimal (AAACCDD) (BBB)
「最大の最初」はDDには適合できません。たぶんそれはこのようなテーブルを構築するのに役立ちます：
Size 1: ---
Size 2: CC, DD
Size 3: AAA, BBB
Size 4: CCDD
Size 5: AAACC, AAADD, BBBCC, BBBDD
Size 6: AAABBB
Size 7: AAACCDD, BBBCCDD
Size 8: AAABBBCC, AAABBBDD
Size 10: AAABBBCCDD
解決
これは基本的にのバリアントです ビンパッキング 問題。この問題はNPハードであることが知られているため、複雑なケース（つまり、多くのオブジェクトとビンを含む）に効率的な最適アルゴリズムを見つけることを期待しないでください。
ただし、オブジェクト/ビンの数が比較的小さい場合は、可能なすべての組み合わせを徹底的に検索するだけで問題ありません。 深さfirst検索.
これは非常に簡単に実装できます。最初のオブジェクトを使用してから、各ビンに最初のオブジェクトを順番に配置してアルゴリズムを再帰的に再実行します（つまり、使用可能なビン空間からオブジェクトのサイズを差し引く）。最後に、これまでに見つかった最高の「ソリューション」を追跡し、すべての組み合わせを試した後、これを最後の答えとして返すだけです。
また、このアルゴリズムアルゴリズムをより速く実行できるようにすることもできます。
- 等しいサイズのすべてのオブジェクトを同等と考える
- 検索ツリーを剪定する（つまり、ブランチから早めに戻る）可能性がある場合は、すでに完璧なフィット感を見つけたときに最新のソリューションを打ち負かすことができない場合
問題のサイズに関するコメントに基づいて更新されます
対処すべき非常に多くのチャンクがあるように見えることを考えると、以下を試してみることができます。
- 上記のように徹底的な検索を使用して、最大の10-20チャンクに適合します
- 最大の適合アプローチを使用して、残りを割り当てます
他のヒント
ミケラは正しい：この複数 ナップザック 問題（ビンパッキングの問題のバリアント）は NPハード.
ここにいくつかのオプションがあります（同様の質問で私の答えからコピーされました）：
ブルートフォース、またはさらに良いことに、枝と縛られています。スケーリングしません（まったく！）が、最適なソリューションであることがわかります（おそらく私たちの生涯ではありません）。
決定論的アルゴリズム：チャンクを最大サイズのサイズで並べ替えて、そのリストを1つずつ進めて、残りの場所を最適な場所に割り当てます。それは非常に速く終了しますが、ソリューションは最適（または実行可能）とはほど遠い場合があります。 これは、何がうまくいかないかを示す素敵な写真です。 しかし、あなたがそれをシンプルに保ちたいなら、それが道です。
決定論的アルゴリズムの結果から始まります。これにより、人間が思いついたものよりも優れた合理的な時間で非常に良い結果が得られます。あなたがそれを与える時間と問題の難しさに応じて、それが最適な解決策であるかもしれないし、そうでないかもしれません。そこには、いくつかのライブラリがあります。 Drools Planner （オープンソースJava）。
この問題の一般的な最良のアルゴリズムはまだ存在していません（参照 ビンパッキングの問題）。ウィキペディアでいくつかの異なるアプローチを見つけることができ、「ビンパッキングの問題」と「ナップサックの問題」のためにグーグルでグーグルを見つけることもできます。
ドナルド・クヌース ダンスリンク アルゴリズムは、「正確なカバー」問題の解決策を見つけるのが迅速です。
