3分区问题 [英] 3-PARTITION problem

问题描述

下面是另一个动态编程的问题（瓦齐拉尼CH6 ）

here is another dynamic programming question (Vazirani ch6)

考虑以下3分区   问题。鉴于整数a ...的，我们   想以确定它是否是   可能{1 ... N}分割成   3不相交的子集I，J，K等   这

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

和（Ⅰ）=总和（J）=总和（K）= 1/3 *之和（ALL）   

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）的答案是否定的。设计   和分析动态规划   算法3分区运行在   时间多项式在n和（总和A_I）

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分区，但仍然解决不了它

How can I solve this problem? I know 2-partition but still can't solve it

推荐答案

可以很容易地概括为3套的情况下2套解决方案。

It's easy to generalize 2-sets solution for 3-sets case.

在原始版本中，将创建布尔数组金额，其中款项[I] 通知是否总和我可以从一组，或不是数字达到。然后，一旦数组被创建，你只要看看款项[TOTAL / 2] 是真与否。

In original version, you create array of boolean sums where sums[i] tells whether sum i can be reached with numbers from the set, or not. Then, once array is created, you just see if sums[TOTAL/2] is true or not.

既然你说你知道老版已经，我将描述他们之间唯一的区别。

Since you said you know old version already, I'll describe only difference between them.

在3分区的情况下，你把布尔数组金额，其中款项[I] [J] 告诉第一组是否可以有一笔我和第二 - 总和Ĵ。然后，一旦数组被创建，你只要看看款项[TOTAL / 3] [TOTAL / 3] 是真或不

In 3-partition case, you keep array of boolean sums, where sums[i][j] tells whether first set can have sum i and second - sum j. Then, once array is created, you just see if sums[TOTAL/3][TOTAL/3] is true or not.

如果原来的复杂性是 O（TOTAL * N），这里的 0（TOTAL ^ 2 * N） 。照片 它可能不是多项式在这个词的严格意义上，但随后原版本不是严格多项式太：）

If original complexity is O(TOTAL*n), here it's O(TOTAL^2*n).
It may not be polynomial in the strictest sense of the word, but then original version isn't strictly polynomial too :)

这篇关于3分区问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！