[ create a new paste ] login | about

Link: http://codepad.org/DPGyc3rI    [ raw code | output | fork ]

Python, pasted on May 18:
import random

def solve(data):
    random.shuffle(data)
    maxsum = 2000
    s_old = [False] * maxsum  # marks for all possible sums
    s_old[0] = True  # seed array with zero sum for zero elements
    for n in data:
        s_new = [False] * maxsum
        for i in range(maxsum):   # mark new possible sums
            if s_old[i]:
                s = abs(i + n)
                if s < maxsum:
                    s_new[s] = True
                s = abs(i - n)
                if s < maxsum:
                    s_new[s] = True
        s_old = s_new
    for i in range(maxsum):
        if s_old[i]:
            return i
    raise AssertionError('my bad')

A = 100
B = 97
C = 90
D = 85
print solve([A] * B + [B] * A)
print solve([A] * B + [B] * A + [C] * D + [D] * C)


Output:
1
2
0
0


Create a new paste based on this one


Comments: