Untitled

Need algorithm (logic) for best sum combination from multi group list

findBest(groups, k):

  if (k < 0): return infinity //stop condition 1

  if (group is empty) return k //stop condition 2

  group <- groups.getFirst()

  min <- infinity

  best <- []

  for each element in group:

     (solValue,minResult) <- findBest(groups-group, k - element) //recursively check for solution, with decreasing number of groups, and modify k

     if (solValue < min):

        min <- solValue

        best <- minResult

        best.append((group,element)) //append the element we added to the solution

  //it is also possible to take no element from this group:

  (solValue,minResult) <- findBest(groups-grou, k - element)

  if (solValue < min):

     min <- solValue

     best <- minResult

  return (minResult,solValue)

       

Sol(grp_i, S) = True      if(grp_i==1 && grp_i dataset has element S) // base case

              = True      if(Sol(grp_i-1, S)==True OR

                             there exists element 'e' in grp_i dataset

                             such that Sol(grp_i-1, S-e)==True)

              = False     otherwise

       

def bestsum(data, maxsum):

  res = [0]*(maxsum+1)

  res[0] = []  # base case

  for group in data:

    new_res = list(res) # copy res

    for ele in group:

      for i in range(maxsum-ele+1):

        if res[i] != 0:

          new_res[i+ele] = list(res[i])

          new_res[i+ele].append(ele)

    res = new_res

  for i in range(maxsum, 0, -1):

    if res[i] != 0:

      return res[i]

      break

  return []

 

print bestsum( [[2,3,5,10,15], [4,6,23,15,12], [23,34,12,1,5]], 25)

print bestsum( [[2,3,10,15],   [4,6,23,12],    [23,34,12,1]],   25)

print bestsum( [[3,10,15],     [4,6,12],       [23,34,12,1]],   25)

       

~$ python2 subsetsum.py

[5, 15, 5]

[2, 23]

[12, 12]