列表中放有若干的货物，数值代表其重量。例如：[23,5,66,8]，表示有四个货物，分别重量为23，5，66，8。这时的问题是需要将这些货物尽可能按照相等的重量分成两份，这个例子中，分成的两份为[23,5,8]与[66]。
该问题等价于0-1背包问题，代码如下：
def checkio(data):
n = len(data)
if n < 2:
return data[0]
else:
sum = 0
for i in range(n):
sum = sum + data[i]
target = int(sum/2)
dp = [[False for i in range(target+1)] for i in range(n+1)]
for i in range(n+1):
dp[i][0] = True
for i in range(1, target+1):
dp[0][i] = False
for i in range(1, n+1):
for j in range(0, target+1):
if j>=data[i-1]:
dp[i][j] = dp[i-1][j-data[i-1]] or dp[i-1][j]
else:
dp[i][j] = dp[i-1][j]
for j in range(target, 0, -1):
if dp[n][j]:
return sum - 2*j
#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"
其他人的代码：
- 代码1
from itertools import combination
def checkio(data):
indexes = set(range(len(data)))
min_dif = sum(data)
for i in range(1, len(data)):
for c1 in combinations(indexes, i):
c2 = {i for i in indexes if i not in c1}
a = sum(data[i] for i in c1)
b = sum(data[i] for i in c2)
min_dif = min(min_dif, abs(a-b))
return min_dif
- 代码2
def rec(used, left, right, rods):
if (left > 0 or right > 0) and len(used) == len(rods):
yield abs(left - right)
return
for ind, k in enumerate(rods):
if (ind, k) not in used:
if left < right:
left += k
used.add((ind, k))
yield from rec(used, left, right, rods)
used.discard((ind, k))
left -= k
elif right <= left:
right += k
used.add((ind, k))
yield from rec(used, left, right, rods)
used.discard((ind, k))
right -= k
- 代码3
from itertools import combinations
def checkio(data):
h = sum(data)/2
t = h
for r in range(1,len(data)):
for c in combinations(data, r):
t = min(t, abs(sum(c)-h))
return t*2
