两个子集之和的最小差异

Question

伙计们,

遇到了一个问题......发现这个问题...我正在修改它只是一点点.

给定一组整数(范围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)

是否有DP方法来解决这个问题.

多谢你们...

拉吉...

Answer 1

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

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

听起来你可能有类似的方法.

Answer 2

    from random import uniform
    l=[int(uniform(0, 500)) for x in xrange(15)]
    l.sort()
    a=[]
    b=[]
    a.append(l.pop())
    while l:
        if len(a) > len(b):
            b.append(l.pop())
        elif len(b) > len(a):
            a.append(l.pop())
        elif sum(a) > sum(b):
            b.append(l.pop())
        else:
            a.append(l.pop())

    print a, b
    print sum(a), sum(b)
    print len(a), len(b)

下一步，我将尝试从相反的列表中找到一对数字，其差异为总和差异的一半（或接近该数字）并交换它们。