3-分区问题

Question

这是另一个动态规划问题（Vazirani ch6）

考虑以下 3-PARTITION 问题。给定整数 a1...an，我们 想确定是否是 可以将 {1...n} 划分为 三个不相交的子集 I, J, K 这样 那个

总和(I) = 总和(J) = 总和(K) = 1/3*总和(全部)

例如，对于输入 (1; 2; 3; 4; 4; 5； 8）答案是肯定的，因为有 是分区 (1; 8), (4; 5), (2; 3； 4）。另一方面，对于输入 (2; 2; 3; 5) 答案是否定的。设计 并分析动态规划 运行于 3-PARTITION 的算法 n 和 (Sum a_i) 的时间多项式

我该如何解决这个问题？我知道2分区，但还是无法解决

Answer 1

很容易将 2 组解决方案推广到 3 组情况。

在原始版本中，您创建布尔 sums 数组，其中 sums[i] 告诉 sum i 是否可以通过集合中的数字达到，或者不是。然后，一旦创建了数组，您只需查看 sums[TOTAL/2] 是否为 true 即可。

既然你说你已经知道旧版本，我只会描述它们之间的区别。

在 3 分区的情况下，您保留布尔 sums 数组，其中 sums[i][j] 告诉第一组是否可以有总和 i第二个 - sum j。然后，一旦创建了数组，您只需查看 sums[TOTAL/3][TOTAL/3] 是否为 true 。

如果原始复杂度为 O(TOTAL*n)，则此处为 O(TOTAL^2*n)。
从最严格的意义上来说，它可能不是多项式，但原始版本也不是严格的多项式:)

Answer 2

我认为通过归约，它是这样的：

将2分区减少到3分区：

设S为原始集合，A为其总和，然后令S'=union({A/2},S)。
因此，对集合 S' 执行 3 分区会产生三个集合 X、Y、Z。
X、Y、Z中，其中之一必须是{A/2}，假设它是集合Z，则X和Y是2分区。
S' 上 3 分区的见证人就是 S 上 2 分区的见证人，因此 2 分区减少为 3 分区。

Answer 3

如果这个问题是可以解决的；那么 sum(ALL)/3 必须是一个整数。任何解都必须具有 SUM(J) + SUM(K) = SUM(I) + sum(ALL)/3。这代表了 concat(ALL, {sum(ALL)/3})​​ 上的 2 分区问题的解决方案。

您说您有一个 2 分区实现：用它来解决那个问题。然后（至少）两个分区之一将包含数字 sum(ALL)/3 - 从该分区中删除该数字，您就找到了 I。对于另一个分区，再次运行 2-partition，将 J 与 K 分开；毕竟，J 和 K 本身的总和必须相等。

编辑：这个解决方案可能是不正确的 - 连接集的 2 分区将有多个解决方案（I、J、K 至少各有一个） - 但是，如果还有其他解，那么“另一边”可能不是由 I、J、K 中的两个并集组成，并且可能根本不可分割。我担心你需要真正思考:-)。

尝试 2： 迭代多重集，维护以下映射：R(i,j,k) :: Boolean 表示以下事实：到当前迭代为止，数字允许分为三个多重集，其总和为 i、j、k。即，对于任何 R(i,j,k) 和下一个状态 R' 中的下一个数字 n，它保持 R '(i+n,j,k) 和 R'(i,j+n,k) 和 R'(i,j,k+n)代码>.请注意，复杂性（根据练习大小）取决于输入数字的大小；这是一个伪多项式时间算法。 Nikita 的解决方案在概念上类似，但比该解决方案更有效，因为它不跟踪第三组的总和：这是不必要的，因为您可以轻松计算它。

Answer 4

正如我在另一个类似问题中回答过的那样，C++ 实现看起来像这样：

int partition3(vector<int> &A)
{
  int sum = accumulate(A.begin(), A.end(), 0);
  if (sum % 3 != 0)
  {
    return false;
  }
  int size = A.size();

  vector<vector<int>> dp(sum + 1, vector<int>(sum + 1, 0));
  dp[0][0] = true;

  // process the numbers one by one
  for (int i = 0; i < size; i++)
  {
    for (int j = sum; j >= 0; --j)
    {
      for (int k = sum; k >= 0; --k)
      {
        if (dp[j][k])
        {
          dp[j + A[i]][k] = true;
          dp[j][k + A[i]] = true;
        }
      }
    }
  }
  return dp[sum / 3][sum / 3];
}

Answer 5

假设您想要将 $X = {x_1, ..., x_n}$ 集合划分为 $k$ 分区。
创建一个$n\timesk$表。假设成本 $M[i,j]$ 是 $j$ 分区中 $i$ 元素的最大总和。只需递归地使用以下最优标准来填充它：

M[n,k] = min_{i\leq n}  max ( M[i, k-1], \sum_{j=i+1}^{n} x_i ) 

Using these initial values for the table: 

M[i,1] = \sum_{j=1}^{i} x_i  and  M[1,j] = x_j  

The running time is $O(kn^2)$ (polynomial )

Answer 6

创建一个三维数组，其中 size 是元素数量，part 等于所有元素的总和除以 3。因此 array[seq][ 的每个单元格sum1][sum2] 告诉您是否可以使用给定数组 A[] 中的 max seq 元素创建 sum1 和 sum2。因此，计算数组的所有值，结果将在元胞数组中[使用所有元素][所有元素的总和/ 3][所有元素的总和/ 3]，如果您可以创建两个集合而不交叉等于sum/3，则有将进行第三组。

检查逻辑：排除A[seq]元素到第三个和（不存储），检查没有元素的单元格是否有相同的两个和； OR 包含到 sum1 - 如果可以得到两个没有 seq 元素的集合，其中 sum1 小于元素 seq A[seq] 的值，并且 sum2 不变；或者像以前一样包括到 sum2 检查。

int partition3(vector<int> &A)
{
    int part=0;
    for (int a : A)
        part += a;
    if (part%3)
        return 0;
    int size = A.size()+1;
    part = part/3+1;
    bool array[size][part][part];
    //sequence from 0 integers inside to all inside
    for(int seq=0; seq<size; seq++)
        for(int sum1=0; sum1<part; sum1++)
            for(int sum2=0;sum2<part; sum2++) {
                bool curRes;
                if (seq==0)
                    if (sum1 == 0 && sum2 == 0)
                        curRes = true;
                    else
                        curRes= false;
                else {
                    int curInSeq = seq-1;
                    bool excludeFrom = array[seq-1][sum1][sum2];
                    bool includeToSum1 = (sum1>=A[curInSeq]
                                          && array[seq-1][sum1-A[curInSeq]][sum2]);
                    bool includeToSum2 = (sum2>=A[curInSeq]
                                          && array[seq-1][sum1][sum2-A[curInSeq]]);
                    curRes = excludeFrom || includeToSum1 || includeToSum2;
                }
                array[seq][sum1][sum2] = curRes;
            }
    int result = array[size-1][part-1][part-1];
    return result;
}

Answer 7

C++ 中的另一个示例（基于之前的答案）：

bool partition3(vector<int> const &A) {
  int sum = 0;
  for (int i = 0; i < A.size(); i++) {
    sum += A[i];
  }

  if (sum % 3 != 0) {
    return false;
  }

  vector<vector<vector<int>>> E(A.size() + 1, vector<vector<int>>(sum / 3 + 1, vector<int>(sum / 3 + 1, 0)));

  for (int i = 1; i <= A.size(); i++) {
    for (int j = 0; j <= sum / 3; j++) {
      for (int k = 0; k <= sum / 3; k++) {
        E[i][j][k] = E[i - 1][j][k];
        if (A[i - 1] <= k) {
          E[i][j][k] = max(E[i][j][k], E[i - 1][j][k - A[i - 1]] + A[i - 1]);
        }

        if (A[i - 1] <= j) {
          E[i][j][k] = max(E[i][j][k], E[i - 1][j - A[i - 1]][k] + A[i - 1]);
        }
      }
    }
  }
  
  return (E.back().back().back() / 2 == sum / 3);
}

Answer 8

你真的想要 Korf 的完整 Karmarkar-Karp 算法 (http:// /ac.els-cdn.com/S0004370298000861/1-s2.0-S0004370298000861-main.pdf，http://ijcai.org/papers09/Papers/IJCAI09-096.pdf）。给出了三分区的概括。考虑到问题的复杂性，该算法的速度快得惊人，但需要一些实现。

KK的本质思想是保证大小相似的大块出现在不同的分区中。一组对块进行分组，然后可以将其视为大小等于可以正常放置的大小差异的较小块：通过递归执行此操作，最终会得到易于放置的小块。然后对块组进行两种着色，以确保处理相反的放置。扩展到 3 分区有点复杂。 Korf扩展是使用KK顺序的深度优先搜索来找到所有可能的解决方案或快速找到解决方案。