2

数を揃えました。私が使用しているセットは 66 ですが、2 つの等しいセットに分割できる任意のサイズのセットにすることができます (例: それぞれ 33)。

番号は連続しておらず、相互に関連していません。重複する可能性があります。

33 の 1 つのセットの一部が 33 の他のセットの一部と等しくなるように、2 つのセット間で数値を分配する方法があるかどうかを判断するための数学アルゴリズムが必要です。

元。1, 8, 5, 12 = 8, 8, 8, 2 (両辺が 26 に等しい)。

私はこれらが等しいことを知っています。存在する場合、この分布を見つけるアルゴリズムが必要です。

4

3 に答える 3

4

数字を並べ替えます。

最高から始めて、合計が低いセットに次の番号を追加します。

たとえば、数字 9 7 3 3 2 の場合:

S0 = S1 = 0

9～S0、S0=9、S1=0

7 ～ S1、S0 = 9、S1 = 7

3～S1、S0=9、S1=10

3～S0、S0=12、S1=10

2 ～ S1、S0 = 12、S1 = 12

このアルゴリズムは、可能な限り差の少ない 2 つのセットを提供します。

于 2012-09-18T07:06:28.723 に答える
1

あなたの仕事は、パーティションの問題をよく知っています。それに関する情報は wiki で見つけることができます: http://en.wikipedia.org/wiki/Partition_problem

NPフルタスクです。近似アルゴリズムを使用できる場合は、@Ari のバリアントを使用できます。しかし、常に正しい答えが得られるとは限りません。サンプル: 13、12、5、5、5、5、5

正しい答えを与える最良の解決策は、疑似多項式の複雑さ O(n * s) の動的計画法を使用して作成できます。ここで、n - すべての数のカウント、s - それらの合計です。

P - 数値の配列を取得しましょう。次に、正確な解決策は次のとおりです。

bool hasSolution(long n, long *P, long sum)
{
   long A[SIZE][SIZE] = {{0}};
   for (long i = 1; i <= n; i++)
       for (long j= 1; j <= sum / 2; j++)
          if (j-P[i]>=0) 
             A[i][j] = MAX (A[i-1][j] , A[i-1][j-P[i - 1]] + P[i - 1])
          else
             A[i][j] = A[i-1][j];

   bool hasSolution = (A[n][sum / 2] == sum / 2);
   return hasSolution;
}
于 2012-09-18T10:14:26.927 に答える
1

私はそれが単純なナップザックの問題だと思います

1) すべての数字を合計して、S としましょう。

2) すべての数字を重みとして使用し、サイズ S>>1 の袋に収まるようにします。

于 2012-09-18T06:59:24.830 に答える