3-PARTITION问题

Question

这是另一个动态编程问题(Vazirani ch6)

考虑以下3-PARTITION问题.给定整数a1 ... an,我们想确定是否有可能将{1 ... n}分割为三个不相交的子集I,J,K,使得

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-PARTITION的动态规划算法,该算法在n和(sum a_i)中以时间多项式运行

我怎么解决这个问题？我知道2分区但仍然无法解决它

Answer 1

对于3组案例,很容易推广2组解决方案.

在原始版本中,您创建一个boolean数组,sums用于sums[i]指示是否i可以使用集合中的数字来达到和.然后,一旦创建数组,你只要看看sums[TOTAL/2]是true或不是.

既然你说你已经知道旧版本了,我只会描述它们之间的区别.

在3分区的情况下,你保留boolean数组sums,其中sums[i][j]告诉第一组是否可以有sum i和second-sum j.然后,一旦创建数组,你只要看看sums[TOTAL/3][TOTAL/3]是true或不是.

如果原始的复杂性O(TOTAL*n),这就是它O(TOTAL^2*n).
它可能不是最严格意义上的多项式,但原始版本也不是严格多项式的:)

Answer 2

我认为通过减少它是这样的:

将2分区减少到3分区:

设S为原始集合,A为其总和,则让S'= union({A/2},S).因此,在集合S'上执行3分区产生三组X,Y,Z.在X,Y,Z中,其中一个必须是{A/2},比如它设置为Z,那么X和Y是一个2分区.S'上3分区的见证者是S上2分区的见证人,因此2分区缩减为3分区.