値のリストを最適にグループ化するアルゴリズム

Question

複数の番号があります。 1つのグループのすべての数値の合計があらかじめ定義された最小値と最大値の間になるように、それらをいくつかのグループにグループ化する必要があります。ポイントは可能な限りグループ化されていない数字が少ないまま残されます。

Input: 
    min, max: range for sum of numbers 
    N1, N2, N3 ... Ni: numbers to group 
Output: 
    [N1,N3,N5],[Ni,Nj,Nk,Nm...]...: groups where sum of numbers is between min and max 
    Na,Nb,Nc...: numbers, left ingrouped. 

Answer 1

効率性が心配されていない場合は、それぞれの可能なグループ化を生成し、説明した意味で最適かつ最適なグループを選択するだけです。明らかに、これは数値の任意の有限リストに対しても機能します（定義上、最適です）。

効率が望ましい場合は、問題はやや難しくなるようです。私は考え続けます。

EDIT：この問題は、少なくとも「サブセット合計」と同じくらい難しいように思えます。そのように、私が提供するソリューションよりもはるかに優れているとは思えません（つまり、

Answer 2

この問題は、サイズがmaxのビンにビンにパッキングされていると面白い目的で見ることができます。最低でもビンにパックされていないアイテムの数を最小限に抑えます。ビンパッキングの文献からの1つのアイデアは、「小さな」アイテム（この場合、max - minに対して小さいアイテム）は簡単にパックできるが、コンビナトリアル爆発の可能性の大部分について説明責任があるということである。ビン詰め物のために何か大きなアイテムを巧みに使い、小さいものを記入してください。可能性の数を減らす別の方法は、数値を丸めて、より小さな集合に属するようにすることです。ビンのパッキング（ラウンドアップ）のためにそれを行う方法はやや明白ですが、この問題に対して何をすべきかははっきりしていません。

---

これらのアイデアをどのようにインスタンス化できるかの例を示します。 max = 1、min = 1/2とする。 max = 2、min = 1/2のときの最適値と競合する解を見つけようとします。 （それは恐ろしいかもしれませんが、OPTがより高い基準に保たれているこの近似保証が文献で時々使用されています）

1ラウンドごとに2の累乗までの大きさそれ以上の場合、包装することはできません。サイズが2または1または1/2の大きなアイテムには、独自のビンが割り当てられます。サイズが1/4以下の小物は以下のように扱われます。サイズが1/4以下の2つのアイテムが同じサイズの場合は、それらを1つのスーパーアイテムに結合します。サイズ1/2の新しいアイテムをすべて自分のビンに詰める。残りの部分の合計サイズは1/2未満です。別のビンにスペースがある場合は、そこに入れます。それ以外の場合は、自分のビンを与えてください。

max = 2で得られる解の品質は、max = 1の場合のOPTの品質と少なくとも同等です。max = 1の最適解を取って、項目サイズを丸めます。アイテムのサイズが小さいので、不良ビンのセットは同じままです。各ビンは、各アイテムが従来の2倍未満であるため、2未満を格納します。今度は、2の累乗で与えたパッキングアルゴリズムが最適であることを示すだけで十分です。私はそれを運動として残します。

私はこれを瞬時に完全なアルゴリズムに一般化するとは思っていません。私は仕事に戻らなければなりませんが、ALGがmax = 1 +εを使用してOPTにmax = 1を処理させ、2の累乗で（1 +ε）の代わりに丸めのステップを実行してから、おそらく動的プログラムを使用して小さなアイテムをパックする方法を見つけ出します。