Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Dynamic Programming solution in Speedy category for Loading Cargo by z_kro
def checkio(data):
s = sum(data)
dp = [True] + [False for _ in range(s)]
for i in data:
for j in range(s,-1,-1):
if j >= i and dp[j-i]: dp[j] = True
for i in range((s+1)//2,s+1):
if dp[i]: return abs(s-i*2)
return -1
#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"
Feb. 28, 2014
Comments: