Split an array into two sets with the smallest difference

收藏到CSDN网摘


这是ACM的一个经典题目,将一个数组分成2部分,保证2部分数据和之差最小.网上有各种分析,据说动态规划(dynamic programming, DP)是最好的解决办法.
下面的分析是用0-1背包法来解决,思路是:
总数据A求和S后,问题转化为:用A中的数据填充容量为S/2的背包,得到最大价值V.那么原问题2部分元素的和的差就是: |(S-V)-V|,由于0-1背包问题时背包容量是S/2,所以可知S-V肯定不小于V,因此最后的差值是:S-2V.

代码如下:

def checkio(data):
    sd = sum(data)      # all sum
    std = sorted(data)  # sort items
    sm = chk(sd/2,std)  # find the biggest value
    return sd-sm-sm     # find the max_half-min_half

# 0-1 Knapsack solution
def chk(v,s):           # value, item
    if len(s)==1:       # only 1 item
        if s[0]<=v:
            return s[0]
        else:
            return 0
    elif v<s[0]:        # cannot put into bag
        return 0
    else:               # some can be put into bag
        pv = []
        for i in range(len(s)):
            if s[i]<=v:
                cv = max(s[i]+chk(v-s[i],s[:i]+s[i+1:]),chk(v,s[:i]+s[i+1:]))
                pv.append(cv)
        if not pv:
            return 0
        else:
            return max(pv)

#These "asserts" using only for self-checking and not necessary for auto-testing
if __name__ == '__main__':
    assert checkio([10, 10]) == 0, "1st example"
    assert checkio([10]) == 10, "2nd example"
    assert checkio([5, 8, 13, 27, 14]) == 3, "3rd example"
    assert checkio([5, 5, 6, 5]) == 1, "4th example"
    assert checkio([12, 30, 30, 32, 42, 49]) == 9, "5th example"
    assert checkio([1, 1, 1, 3]) == 0, "6th example"