两个子集之和最小差异 [英] minimum difference between sum of two subsets

问题描述

伙计们，

遇到了一个问题......发现这个野趣......我改变一点点只是涂PEP起来。

  

给定一组整数（范围0-500）的，发现了可以通过将它们几乎同样地形成两个子集之和之间的最小差异。 （比如说整数计数是n，当n为偶数，每一组必须具有n / 2个元件，如果n是奇数，一组具有第（n-1）/ 2个元素和其他具有第（n + 1）/ 2个元素）

     

采样开关输入：1 2 3 4 5 6

     

最小差异= 1（亚群是1 4 6和2 3 5）

     

样品输入2：[1 1 1 1 2 2 2 2]

     

最小差异= 0（子集是1 1 2 2 1 1 2 2）<​​/ P>

有DP方法这个问题。

感谢球员...

拉​​吉...

解决方案

这个问题看起来几乎像平衡分区。

您可以使用一个DP的方法来建立一个伪多项式时间算法，解决了平衡的分区。参见问题7在<一个href="http://people.csail.mit.edu/bdean/6.046/dp/">http://people.csail.mit.edu/bdean/6.046/dp/

这听起来像你可以有一个类似的方法。

Folks,

came across a problem... found this intersting... am modifying it a little bit just tu pep it up.

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 )

is there DP approach for this problem.

Thanks guys...

raj...

解决方案

This problem looks almost like the "balanced partition".

You can use a DP approach to build a pseudo-polynomial time algorithm that solves the balanced partition. See problem 7 at http://people.csail.mit.edu/bdean/6.046/dp/

It sounds like you could have a similar approach.

这篇关于两个子集之和最小差异的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！