Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 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)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement