1

我找到了 3-partition 问题的解决方案，即给定 n 个数字，您确定是否可以形成三个（不相交）子集，使得所有子集都相等（即每个子集的总和等于 n数字/3）。

一个类似的问题是：3-PARTITION 问题。但是，我正在寻找以下代码的解释。

简单地说，我不知道发生了什么。我不知道 T 是什么，i 或 j 是什么，k 是什么，或者为什么我们 k 和 j 从 N 开始并且正在递减，什么 "T[j + C[i]][k] = true; T[j][k + C[i]] = true" 意味着，或者我们为什么要返回 T[N/3]？

bool T[10240][10000];
bool partition( vector< int > C ) {
    // compute the total sum
    int n = C.size();
    int N = 0;

    for( int i = 0; i < n; i++ ) N += C[i];
    // initialize the table
    T[0][0] = true;
        memset(T, 0, 10000^2);

    // process the numbers one by one
    for( int i = 0; i < n; i++ ) {
                for (int j = N; j >= 0; --j) {
                        for (int k = N; k >= 0; --k) {
                                if (T[j][k]) {
                                        T[j + C[i]][k] = true;
                                        T[j][k + C[i]] = true;
                                }
                        }
                }
        }
    return T[N / 3];
}
4

2 回答 2

4

首先，返回值应该是T[N / 3][N / 3]。

T[i][j] 表示是否有可能得到总和为 i 的第一个分区和总和为 j 的第二个分区。显然，由于所有 n 个数之和为 N。所以 T[i][j] 为真意味着数组可以分为三个部分，总和分别为 i、j 和 Nij。

最初，T[0][0] 为真，其他均为假，这意味着一开始只能将数字分为三个部分：0、0 和 N。 i 的 for 循环迭代所有 n数字，并且每次都可以将数字 C[i] 分组到第一个分区或第二个分区。这就是为什么设置 T[j+C[i]][k] 和 T[j][k+C[i]] 为真。

变量 j 和 k 之所以从 N 开始递减，是为了避免对单个数字进行多次计数。这样考虑：例如，如果 j 从 0 开始到 N，则 T[j][k], T[j+C[i]][k], T[j+C[i]*2] [k], ... , T[j+C[i]*x][k] 都将设置为 true，这是不正确的。您可以简单地选择一个小案例来尝试自己模拟该过程。

于 2013-03-26T08:58:36.380 回答
1

正确的 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];
}
于 2020-05-03T07:00:40.350 回答