python编程,把一个整数list分成两个list,要求两个(list里整数总和)之差值最小

如题所述

#!/usr/bin/env python
#-*- encoding: utf-8 -*-
from itertools import compress, imap
def fun(lst):
min_number = 100000000
length = len(lst)
total = 2**length
record = None
f = lambda x:compress(lst, imap(int,bin(x)[2:].rjust(length,'0')))
for n in xrange(total):
plus = f(n)
minus = f(total-n-1)
tmp = abs(sum(plus) - sum(minus))
if tmp < min_number:
record = n
min_number = tmp
plus = list(f(record))
minus = list(f(total-record-1))
return (plus, minus, min_number)
def main():
print '(分组1, 分组2, 差值)'
print fun([1,2,3,1,4,10,7,5,23])
main()


拿了个list来穷举试了一下,Python 2.7.3测试通过。

温馨提示:内容为网友见解,仅供参考
第1个回答  2013-04-11

用了greedy algorithm,即每一步选最优解(假设无负数):

def slist(aList):
aList.sort()
aList.reverse()
a=[]
b=[]
for i in aList:
if sum(a)>sum(b):
b.append(i)
else:
a.append(i)
return a,b,sum(a)-sum(b)
print slist([1,2,3,1,4,10,7,5,23])

第2个回答  2017-12-04
#参考其中一个评论的代码,在他基础上修改优化了下,执行方式 python XXX.py list
#!/usr/bin/env pythons
#-*- encoding: utf-8 -*-
from itertools import compress, imap
import sys
def division(lst):
    min_number = sum(lst)
    length = len(lst)
    total = 2**length
    record = None
    f = lambda x:compress(lst,imap(int,bin(x)[2:].rjust(length,'0')))
    #a=bin(7)[2:]>>'111'    a.rjust(8,'0')>>右对齐 '00000111'
    #imap(int,str)  把str转成列表,且列表元素为整型
    for n in xrange(total):
        plus = f(n)
        minus = f(total-n-1)
        tmp = abs(sum(plus) - sum(minus))
        if tmp < min_number:
            record = n
            min_number = tmp
    plus = list(f(record))
    minus = list(f(total-record-1))
    return (plus, minus, min_number)
def main():
    arg=list(sys.argv[1].strip('[]').split(','))
    arglist=list(imap(int,arg))
    print '(list1, list2, diffrence)'
    print division(arglist)
if __name__=='__main__':
    main()

相似回答