5

この問題を解決する方法を教えてください。

k 個の要素を含む集合 S が与えられます。

ここで、集合 S を x 個のサブセットに分割して、各サブセットの要素数の差が 1 以下になり、各サブセットの合計が互いにできるだけ近くなるようにする必要があります。

例 1: {10, 20, 90, 200, 100} は 2 つのサブセットに分割する必要があります

解決策:{10,200}{20,90,100}

合計は 210 と 210

例 2: {1、1、2、1、1、1、1、1、1、6}

解決策:{1,1,1,1,6}{1,2,1,1,1}

合計は 10 と 6 です。

4

3 に答える 3

2

解決策は 2 段階で考えられます。

ステージ1

サブセットの数 N を選択することから始めます。可能であれば、元のセット S を並べ替えます。S から最大の N 個の数を順番にサブセット 1 から N に分配します。S サブセットから次の N 個の最大数を逆の順序で、N から 1 に分配します。すべての数が分配されるまで繰り返します。

S を並べ替えることができない場合は、S の各数値を、最小のエントリと最小の合計を持つサブセット (またはサブセットの 1 つ) に分配します。

これで、N 個のサブセットがすべて互いに 1 以内のサイズになり、合計がほぼ同じになるはずです。

ステージ 2

ここで、おおよその解を絞り込んでみてください。最大の合計サブセット L と最小の合計サブセット M を選択します。M の数値よりも小さいが、2 つのサブセット間の絶対差を大きくしない L の数値を選択します。2 つの数字を入れ替えます。繰り返す。サブセットのすべてのペアに交換可能な番号があるわけではありません。各スワップは、サブセットを同じサイズに保ちます。

時間に余裕がある場合は、徹底的な検索を行うことができます。そうでない場合は、いくつかの明白なケースを選択してみてください。差が減少しない場合は、数値を交換しないでください。そうしないと、無限ループが発生する可能性があります。

一部のサブセットに少なくとも 2 つのメンバーがある場合は、ステージをインターリーブできます。

于 2011-07-21T20:59:16.477 に答える
1

この問題の簡単なアルゴリズムはありません。

最も簡単なハード問題としても知られている、2セットでこれを解決するパーティション問題を確認してください。この問題はNP完全であり、Web上でそれを解決するためのすべてのアルゴリズムを見つけることができるはずです。

セットの数を選択できるため、問題が少し異なることはわかっていますが、前のソリューションの解決策から自分自身を刺激することができます。

例えば ​​：

これを一連の線形計画法に変換できます。kをセット内の要素の数とします。

{a1 ... ak} is your set

For i = 2 to k:

   try to solve the following program:
        xjl = 1 if element j of set is in set number l (l <= i) and 0 otherwise

        minimise max(Abs(sum(apxpn) -sum(apxpm)) for all m,n) // you minimise the max of the difference between 2 sets.

        s.t 
        sum(xpn) on n = 1
        (sum(xkn) on k)-(sum(xkm) on k) <= 1 for all m n // the number of element in 2 list are different at most of one element.
        xpn in {0,1}

  if you find a min less than one    then stop
  otherwise continue

end for

私の記法が明確であることを願っています。

このプログラムの複雑さは指数関数的であり、これを解くための多項式の方法を見つけた場合、P = NPを精査するので、これ以上うまくいくとは思いません。

編集

あなたのコメントを見ました、サブセットのサイズの制約を誤解しました（2セットの違いだと思いました）更新する時間がありません。時間があるときに更新します。sryy

編集2

私は線形計画法を編集しました、そしてそれはそれがするように頼まれたことをするはずです。制約を追加しました。

この解決策は最適ではないかもしれませんが、今回は問題が完全に理解されていることを願っています

于 2011-07-21T17:12:13.987 に答える
0

私は科学者ではないので、2つのアプローチを試してみます。

アイテムを並べ替えた後、両方の「端」から移動し、最初と最後を実際のセットに移動してから、次のセットに移動してループします。

それで：

  1. セットの合計の違いを確認し、役立つ場合はアイテムをシャッフルします。
  2. 結果のセットを適切にコーディングし、遺伝的アルゴリズムを試します。
于 2011-07-21T17:29:40.020 に答える