这是另一个动态规划问题，关于3-Partition（Vazirani第6章）
考虑以下3-Partition问题。给定整数a1 ... an， 我们想要确定是否可能将{1 ... n}分成三个不相交的子集I，J，K， 使得
sum(I) = sum(J) = sum(K) = 1/3 * sum(ALL)
例如，对于输入（1；2；3；4；4；5；8），答案是肯定的，因为存在分区（1;8），（4;5），（2;3;4）。 另一方面，对于输入（2;2;3;5），答案是否定的。设计并分析一个运行时间多项式为n和(Sum a_i)的3-Partition动态规划算法。
我该如何解决这个问题？我知道2-partition，但还是无法解决它
将2元素集合的解法推广到3元素集合的情况很容易。
在原始版本中，你创建了一个布尔数组sums，其中sums[i]表示是否可以用集合中的数字达到和i。然后，一旦数组创建完成，只需查看sums[TOTAL/2]是否为true。
由于你已经知道了旧版本，我只会描述它们之间的区别。
在3分区的情况下，保留一个布尔数组sums，其中sums[i][j]表示第一组可以有和i，第二组可以有和j。然后，一旦数组创建完成，只需查看sums[TOTAL/3][TOTAL/3]是否为true。
如果原始复杂度为O(TOTAL*n)，那么这里是O(TOTAL^2*n)。
严格意义上来说，它可能不是多项式，但原始版本也不是严格的多项式 :)
i，第二个子集的和为 j（显然，第三个子集的和为 TOTAL - i - j）。这有帮助吗？ - Nikita Rybak我认为通过简化，可以得出以下结论：
将2分问题简化为3分问题：
设S为原始集合，A为其总和，令S'=union({A/2},S)。 因此，在集合S'上执行3分操作会得到三个集合X、Y、Z。 在这三个集合中，必有一个是{A/2}，假设该集合是Z，则X和Y就构成了一个2分问题。 集合S的3分证明是S'的3分证明，因此2分问题降解为3分问题。
sum(ALL)/3必须是一个整数。任何解决方案都必须满足SUM(J) + SUM(K) = SUM(I) + sum(ALL)/3。这代表了对concat(ALL, {sum(ALL)/3})的2分问题的解决方案。sum(ALL)/3 - 从该分区中删除该数字，您就找到了I。对于另一个分区，请再次运行2分，以将J从K中分离出来；毕竟，J和K本身的总和必须相等。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的解决方案在概念上类似但比此解决方案更有效，因为它不跟踪第三个集合的总和：这是不必要的，因为您可以轻松计算它。就像我在另一个类似的问题中所回答的那样，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];
}
以下是基于之前答案的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);
}
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;
}
假设您想将集合$X = {x_1, ..., x_n}$划分为$k$个分区。创建一个 $ n \times k $ 表格。假设成本$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 )
你真的想要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顺序的深度优先搜索来查找所有可能的解决方案或快速找到解决方案。