3-PARTITION问题
这是另一个动态编程问题（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）的时间多项式运行
我怎么解决这个问题？我知道2分区，但仍然无法解决
回答：
对于3套案例，可以很容易地概括2套解决方案。
在原始版本中，您将创建一个布尔数组，sums在其中sums[i]告诉是否i可以使用集合中的数字达到和。然后，一旦创建数组，你只要看看sums[TOTAL/2]是true或不是。
既然您说您已经知道旧版本，那么我将仅介绍它们之间的区别。
在三分区情况下，您保留boolean数组sums，其中sums[i][j]告诉第一组是否可以具有sum i和second-sum
j。然后，一旦创建数组，你只要看看sums[TOTAL/3][TOTAL/3]是true或不是。
如果原始复杂度为O(TOTAL*n)，则为O(TOTAL^2*n)。
从严格意义上讲，它可能不是多项式，但是原始版本也不是严格的多项式:)
以上是 3-PARTITION问题 的全部内容， 来源链接： utcz.com/qa/433316.html
