这是另一个动态编程问题（Vazirani ch6）
考虑以下3-PARTITION问题。给定整数a1 … an，我们要确定是否有可能将{1 … n}划分为三个不相交的子集I，J，K，从而 sum（I）= sum（J）= sum（K）= 1/3 * sum（全部） 例如，对于输入（1; 2; 3; 4; 4; 5; 8），答案是肯定的，因为存在分区（1; 8），（4; 5），（2; 3; 4）。另一方面，对于输入（2; 2; 3; 5），答案为否。设计并分析一种针对3-PARTITION的动态编程算法，该算法以n和（Sum a_i）的时间多项式运行
考虑以下3-PARTITION问题。给定整数a1 … an，我们要确定是否有可能将{1 … n}划分为三个不相交的子集I，J，K，从而
sum（I）= sum（J）= sum（K）= 1/3 * sum（全部）
例如，对于输入（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分区，但仍然无法解决
对于3套案例，可以很容易地概括2套解决方案。
在原始版本中，您将创建一个布尔数组，sums在其中sums[i]告诉是否i可以使用集合中的数字达到和。然后，一旦创建数组，你只要看看sums[TOTAL/2]是true或不是。
sums
sums[i]
i
sums[TOTAL/2]
true
既然您说您已经知道旧版本，那么我将仅介绍它们之间的区别。
在三分区情况下，您保留boolean数组sums，其中sums[i][j]告诉第一组是否可以具有sum i和second-sum j。然后，一旦创建数组，你只要看看sums[TOTAL/3][TOTAL/3]是true或不是。
sums[i][j]
j
sums[TOTAL/3][TOTAL/3]
如果原始复杂度为O(TOTAL*n)，则为O(TOTAL^2*n)。 从严格意义上讲，它可能不是多项式，但是原始版本也不是严格的多项式:)
O(TOTAL*n)
O(TOTAL^2*n)
