algorithm - 两个子集之和之间的最小差

Question

各位，

遇到了一个问题...发现这很有趣...我正在对其进行一些修改，只是打气。

Given a set of integers (range 0-500), find the minimum difference between the sum of two subsets that can be formed by splitting them almost equally. (say count of integers is n, if n is even, each set must have n/2 elements and if n is odd, one set has (n-1)/2 elements and other has (n+1)/2 elements)

sample imput : 1 2 3 4 5 6

minimal difference = 1 (subsets being 1 4 6 and 2 3 5 )

sample input 2 : [ 1 1 1 1 2 2 2 2 ]

minimal difference = 0 (subsets being 1 1 2 2 and 1 1 2 2 )

是否有针对此问题的 DP 方法。

谢谢大家...

拉杰...

Answer 1

这个问题看起来很像“平衡分区”。

您可以使用 DP 方法构建求解平衡分区的伪多项式时间算法。见问题 7 http://people.csail.mit.edu/bdean/6.046/dp/

听起来您可以采用类似的方法。