splitsum.py

# given a knapsack of size n, a list of items costs C and weights W
# this function returns a list of items which fits in the knapsack of 
# maximum cost
#
# algorithm runs in O(nm) where m = len(C) = len(W)
def knapsack(n, C, W):
    # m is number of items in list
    m = len(C)
    
    # create two dimensional array
    K = [[0 for j in range(m + 1)] for i in range(n + 1)]
    
    # fill out the two dimensional array
    # need to do W[j - 1] to get jth item because python indices start at 0
    for i in range(1, n + 1):
        for j in range(1, m + 1):
            # check that W[j - 1] <= i to see if there is room in the knapsack for item j
            # then compare the case were we take item j with the case where we don't
            if W[j - 1] <= i and C[j - 1] + K[i - W[j - 1]][j - 1] > K[i][j - 1]:
                K[i][j] = C[j - 1] + K[i - W[j - 1]][j - 1]
            else:
                K[i][j] = K[i][j - 1]
    
    # backtrack to find out which items we actually took
    R = []
    i = n
    j = m
    while j > 0:
        # assuming we have all positive cost items, taking item j causes cost to change
        # so we only need to check that the total value in knapsack changes
        if K[i][j] != K[i][j - 1]:
            i = i - W[j - 1]
            R.append(j - 1)
        j = j - 1
    R.reverse()
    
    return R
 
# takes a list S where N = sum(S) and attempts to
# split it into two sublists with sum N / 2.
#
# uses knapsack to solve in O(N * len(S))
def splitsum(S):
    # use knapsack to solve problem
    I = knapsack(sum(S) / 2, S, S)
    
    # turn indices into two sublists of original list
    R1 = [S[i] for i in I]
    R2 = [S[i] for i in set(range(len(S))).difference(I)]
    
    # return the sublists only if they have equal sums
    if sum(R1) == sum(R2):
    	return (R1, R2)
    else:
        return None
 
if __name__ == '__main__':
    S = [1, 3, 2, 5, 7, 6]
    print(S)
    print("Split the numbers into two sets with equal sums")
    print(splitsum(S))
    print("")
    
    T = [1, 3, 2, 5, 7, 9]
    print(T)
    print("List has odd sum, so cannot be split")
    print(splitsum(T))
    print("")
    
    U = [13, 3, 5, 9]
    print(U)
    print("List has even sum, but still cannot be split")
    print(splitsum(U))
    print("")