这是另一个动态规划问题(Vazirani ch6)
Consider the following 3-PARTITION problem. Given integers a1...an, we want to determine whether it is possible to partition of {1...n} into three disjoint subsets I, J, K such that
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 there is the partition (1; 8), (4; 5), (2; 3; 4). On the other hand, for input (2; 2; 3; 5) the answer is no. Devise and analyze a dynamic programming algorithm for 3-PARTITION that runs in time poly- nomial in n and (Sum a_i)
我该如何解决这个问题？我知道 2-partition 但还是无法解决
最佳答案
很容易将 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)。
它可能不是严格意义上的多项式，但原始版本也不是严格的多项式:)
关于algorithm - 3-PARTITION问题，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4803668/