algorithm - オブジェクトのペアを別々のビンに並べ替えます

Question

同じサイズのオブジェクトペア（マスターコピー/スレーブコピー）がN個あります。マスターコピーとスレーブコピーの両方がビンに含まれないように、それぞれ容量の異なるM個のビンにコピーを分散させたいと思います。

最も効率的なアルゴリズムは何ですか？さらに重要なことに、（実際に解を生成せずに）特定の入力に対して可能な解があるかどうかを調べるための最も効率的なアルゴリズムは何ですか？

Answer 1

簡単な解決策は次のとおりです。

Mバケットを容量に従って降順で並べ替えます：x1、x2、..、xm

一番上の2つのバケットを選択し、そのペアにオブジェクトを割り当て、2つのバケットの使用可能な容量を減らし、バケットを再配置します。ヒープを使用してバケットを追跡でき、複雑さはO（n）に近いです。

すべてのオブジェクトが割り当てられるまで繰り返します。

Answer 2

ブルートフォースよりも優れたものを想像するのは難しいです。残りの容量を降順で優先キュー内のMビンを追跡し、各オブジェクトペアをキュー内の最初の2つのビンに追加します。キューのバランスを取り直して繰り返します。Mビンの総容量>=2 * Nの場合、解決策が存在します。

それは複雑さのように思われますO（N * log M）

注：正確に3つのビンの場合、N> M1 + M2の解は存在しません。ここで、Mnは、M0の容量に関係なく、範囲0..Mのnの容量の降順でソートされたビンnの容量です。

同様に、正確に2つのビンの場合、ソリューションはN<=M1に対してのみ存在します。