2

我有一组数字。我正在使用 66 组，但它可以是任何大小的组，可以分成两个相等的组（例如，每个组 33 个）

这些数字不是连续的，也不是相互关联的。可以有重复。

我需要一个数学算法来确定是否有任何方法可以在两组之间分配数字，以便一组 33 中的一些等于另一组 33 中的一些。

前任。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

该算法将为您提供差异最小的两组。

于 2012-09-18T07:06:28.723 回答
1

我想这是一个直接的背包问题

1）总结所有数字让我们说S。

2) 使用所有数字作为权重，尝试放入大小为 S>>1 的麻袋

于 2012-09-18T06:59:24.830 回答
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 回答