algorithm - 3-PARTITION问题

Question

这是另一个动态规划问题(Vazirani ch6)

Consider the following 3-PARTITIONproblem. Given integers a1...an, wewant to determine whether it ispossible to partition of {1...n} intothree disjoint subsets I, J, K suchthat

sum(I) = sum(J) = sum(K) = 1/3*sum(ALL)

For example, for input (1; 2; 3; 4; 4;5; 8) the answer is yes, because thereis the partition (1; 8), (4; 5), (2;3; 4). On the other hand, for input(2; 2; 3; 5) the answer is no. Deviseand analyze a dynamic programmingalgorithm for 3-PARTITION that runs intime poly- nomial in n and (Sum a_i)

我该如何解决这个问题？我知道 2-partition 但还是无法解决

Answer 1

很容易将 2 组解决方案推广到 3 组情况。

在原始版本中，您创建了 bool 值 sums 数组，其中 sums[i] 告诉 i 是否可以用来自设置，或不设置。然后，创建数组后，您只需查看 sums[TOTAL/2] 是否为 true。

既然你说你已经知道旧版本，那我就只描述它们之间的区别。

在 3 分区情况下，您保留 bool 数组 sums，其中 sums[i][j] 告诉第一组是否可以有总和 i 和第二个 - sum j。然后，创建数组后，您只需查看 sums[TOTAL/3][TOTAL/3] 是否为 true。

如果原来的复杂度是O(TOTAL*n)，这里是O(TOTAL^2*n)。
它可能不是严格意义上的多项式，但原始版本也不是严格的多项式:)