把一个list分成二个list,使其差最小
本帖最后由 liu510817387 于 2013-07-03 10:19:31 编辑 这是在checkio.com上的一道题，初学python,就采用最笨的方法
list拆分成二个差最小的list
例如：[5,10,5,10,1] => sum([5,10,1]) - sum([5,10]) = 1
def checkio(data):
dataLen = len(data)
'''data.sort()'''
if dataLen==1:
return data[0]
listDiff = []
for i in range(dataLen-1,-1,-1):
leftList = [data[i]]
rightList = data[:]
del rightList[i]
for y in range(dataLen-2,-1,-1):
if rightList[y]:
addItem = rightList[y]
leftSum = sum(leftList)
rightSum = sum(rightList)
if leftSum+2*addItem<=rightSum:
leftList.append(addItem)
del rightList[y]
leftSum = sum(leftList)
rightSum = sum(rightList)
listDiff.append(abs(leftSum-rightSum))
listDiff.sort()
result = listDiff[0]
#replace this for solution
return result
[解决办法]
2楼的算法在a=[12, 30, 30, 32, 42, 49]时的结果(13)有误,应该是9
下面是我用01背包解决的代码,思路是:
总数据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)==0 or v<s[0]: # no item or the smallest cannot be 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)
