这是另一个动态编程问题（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-partition 但仍然无法解决它
很容易将 2 套解决方案推广到 3 套案例。
在原始版本中，您创建布尔数组sumswheresums[i]告诉 sum 是否i可以用集合中的数字达到。然后，一旦创建了数组，您只需查看是否sums[TOTAL/2]存在true。
既然您说您已经知道旧版本，我将仅描述它们之间的区别。
在 3 分区的情况下，您保留 boolean 数组sums，其中sums[i][j]告诉第一个集合是否可以有 sumi和第二个 sum j。然后，一旦创建了数组，您只需查看是否sums[TOTAL/3][TOTAL/3]存在true。
如果原始复杂度是O(TOTAL*n)，这里是O(TOTAL^2*n)。
它可能不是最严格意义上的多项式，但是原始版本也不是严格的多项式:)
我认为通过减少它是这样的：
将 2 分区减少为 3 分区：
令 S 为原始集合，A 为其总和，则令 S'=union({A/2},S)。因此，对集合 S' 进行 3-partition 会产生三个集合 X、Y、Z。在 X、Y、Z 中，其中一个必须是 {A/2}，假设它是集合 Z，那么 X 和 Y 是2分区。S' 上 3 分区的见证人是 S 上 2 分区的见证人，因此 2 分区简化为 3 分区。
如果这个问题是可以解决的；那么sum(ALL)/3必须是整数。任何解决方案都必须有SUM(J) + SUM(K) = SUM(I) + sum(ALL)/3. 这代表了 2 分区问题的解决方案concat(ALL, {sum(ALL)/3})。
你说你有一个 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)和下一个数字它都持有和和 。请注意，复杂性（根据 excersize）取决于输入数字的大小；这是一个伪多项式时间算法。Nikita 的解决方案在概念上相似但比此解决方案更有效，因为它不跟踪第三组的总和：这是不必要的，因为您可以简单地计算它。nR'R'(i+n,j,k)R'(i,j+n,k)R'(i,j,k+n)
正如我在另一个类似的问题中回答的那样，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];
}
假设您要对集合$X = {x_1, ..., x_n}$进行$k$分区。创建一个 $ n \times k $ 表。假设成本是$j$ 个分区$M[i,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 )
创建一个三维数组，其中size是元素的数量，part等于所有元素的总和除以 3。所以 array[seq][sum1][sum2] 的每个单元格告诉你可以使用 max 创建 sum1 和 sum2给定数组 A[] 中的 seq 元素与否。所以计算数组的所有值，结果将在单元格数组中[使用所有元素][所有元素的总和 / 3][所有元素的总和 / 3]，如果你可以创建两个集合而不交叉等于 sum/3，那么将是第三组。
检查逻辑：将A[seq]元素排除到第三个和（未存储），如果两个和相同，则检查没有元素的单元格；或包含到 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;
}
您真的想要 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-partition 的扩展有点复杂。Korf 扩展是在 KK 中使用深度优先搜索来找到所有可能的解决方案或快速找到解决方案。