Public Pastes
SHARE
TWEET

subset sum answer

a guest Aug 16th, 2017 2,444 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. def closest (Listi,S,r):
  3.     List = Listi
  4.     if r in List:
  5.         List.remove (r)
  6.     l = []
  7.     L = []
  8.     answer = 0
  9.     dic = {}
  10.     if S in List:
  11.         return S
  12.     else:
  13.         for each in List:
  14.             if S > each:
  15.                 l.append ((S)- (each))
  16.                 dic[(S) - (each)] = each
  17.         if not len(l) == 0:
  18.             answer = (dic[min(l)])
  19.             return (answer)
  20.         else:
  21.             return 'nope'
  22.  
  23. def partition(I):
  24.     try:
  25.         orgi = []
  26.         orgi.extend (I)
  27.         b = sum(I)/2
  28.         i = I
  29.         i.sort ()
  30.         i.reverse ()
  31.         c = 0
  32.         try:
  33.             for each in I:
  34.                 try:
  35.                     i = I
  36.                     stop = 0
  37.                     B = each
  38.                     while len(i) >= 1 and stop == 0:
  39.                         if B == b:
  40.                             stop = 1
  41.                             return ('yes')
  42.                         c = closest(i,b - B,each)
  43.                         if c == 'nope':
  44.                             stop = 1
  45.                         else:
  46.                             if c == b - B and len(i) > 1:
  47.                                 return ('yes')
  48.                             B += c
  49.                             i.remove (c)
  50.                 except Exception as e:
  51.                     f = 0
  52.         except Exception as e:
  53.             b = sum(orgi)/2
  54.             i = orgi
  55.             i.sort ()
  56.             c = 0
  57.             for each in orgi:
  58.                 i = orgi
  59.                 stop = 0
  60.                 B = each
  61.                 while len(i) >= 1 and stop == 0:
  62.                     if B == b :
  63.                         stop = 1
  64.                         return ('yes')
  65.                     c = closest(i,b - B,each)
  66.                     if c == 'nope':
  67.                         stop = 1
  68.                     else:
  69.                         if c == b - B and len(i) > 1:
  70.                             return ('yes')
  71.                         B += c
  72.                         i.remove (c)
  73.                          
  74.     except Exception as e:
  75.         return ('none')
  76.  
  77. def SubsetSum(ListI):
  78.     List = ListI
  79.     s = sum(List)
  80.     NList = []
  81.     S = 0
  82.     List2 = []
  83.     List.append(-s)
  84.     #List.append(S+s)
  85.     for each in List:
  86.         NList.append (abs(each))
  87.     if partition(List) == 'yes':
  88.         return ('yes')
  89.     else:
  90.         return ('no')
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top