from pulp import (
    LpVariable, LpProblem, LpMinimize, value
)
from random import randint

# Make a memoization function
def memoize(f):
    class memocache(dict):
        def __missing__(self, keys):
            ret = self[keys] = f(*keys)
            return ret
        def __getitem__(self, *keys):
            return dict.__getitem__(self, keys)
    return memocache().__getitem__

# Make a function to discard unwanted integers
def cap_ints(ints, n):
    if max(ints) < n:
        return ints
    else:
        ints_above = [i for i in ints if i > n]
        smallest_above = min(ints_above)
        return [i for i in ints if i <= smallest_above]

def find_sum_dp(ints, n):
    # If n is in the list return n, or if the sum of ints is less than n
    # return null
    if n in ints:
        return [n], n
    elif sum(ints) < n:
        return None, None
    # Only search for values up to the smallest value above n
    c = cap_ints(ints, n)
    # Define the value function as a recurrent relation
    @memoize
    def V(n, i):
        # If we've reached the end, don't do anything further
        if i == 0 or n <= 0:
            return 0.0, []
        else:
            # Calculate 2 cases: we use the current number, or we don't.
            # a0 = don't take this integer, a1 = take this integer
            # Get the results for the previous integer for each action
            Va0_p, Sa0_p = V(n, i-1)
            Va1_p, Sa1_p = V(n - c[i-1], i-1)
            # Use for this integer's result
            Va0, Sa0 = Va0_p, Sa0_p
            Va1 = Va1_p + c[i-1] # Since we've taken this integer
            Sa1 = Sa1_p + [c[i-1]] # Likewise
            # We want the smallest value that exceeds or equals n.
            # Since we assume our final state exceeds or equals n, at least Va1
            # must exceed or equal n by this assumption.
            if Va0 >= n and Va0 <= Va1:
                return Va0, Sa0
            else:
                return Va1, Sa1

    sumsoln, soln = V(n, len(c))
    return soln, sumsoln

def find_sum_lp(ints, n):
    # If n is in the list return n, or if the sum of ints is less than n return
    # null
    if n in ints:
        return [n], n
    elif sum(ints) < n:
        return None, None
    # Only search for values up to the smallest value above n
    c = cap_ints(ints, n)
    L = len(c)
    # Define the variables
    variables = [
        LpVariable("x"+str(i), 0, 1, cat='Binary') for i in xrange(L)
    ]
    # Define the problem
    P = LpProblem("minsum", LpMinimize)
    # Add constraint
    P += sum(c[i]*variables[i] for i in range(L)) >= n
    # Add objective function
    P += sum(c[i]*variables[i] for i in range(L))
    # Solve!
    P.solve()
    # Get the list of integers that are summed
    soln = [
        c[i] for i, xi in enumerate(variables)
        if value(xi) == 1.0
    ]
    # Return the list of integers, and the sum
    return soln, sum(soln)

def random_integers(lbound, ubound, length):
    # Generate length random integers between lbound and ubound
    return [randint(lbound, ubound) for i in xrange(length)]

if __name__ == '__main__':
    ints = random_integers(1, 1000, 30)
    n = 1000
    print ints
    print find_sum_lp(ints, n)
    print find_sum_dp(ints, n)