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

Question

I have multi group of data like

Group1 2,3,5,10,15
Group2 4,6,23,15,12
Group3 23,34,12,1,5

i need best sum (example sum(g1+g2+g3)<=25) from those 3 group like

1st (g1) 5 + (g2) 15 + (g3) + 5 = 25 (best combination)

Now, for next set of combination, no need to use above values from each corresponding group

Group1 2,3,5,10,15
Group2 4,6,23,15,12
Group3 23,34,12,1,5

2nd (g1) 2 + (g2) 23 = 25 (best combination)

Group1 2,3,5,10,15
Group2 4,6,23,15,12
Group3 23,34,12,1,5

3rd (g1) 15 + (g2) 6 + (g3) + 1 = 22 (best combination)

I hope this might be bit complex . But i might get better solution for this problem.

Thanks

Answer 1

Subset sum problem has a pseudo-polynomial dynamic programming approach. We can map it to this variation problem with complexity O(S*N) and O(S) space, where S is the maximum sum (25 in your example), and N is the total no of elements across all groups.

This complexity doesn't depend on total no of groups, hence better suited if O(N^G) brute force solution will not converge for high values of G>=10. But note that this algo will not work for S>=biginteger.

In short, the DP recursive solution is as follows:

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   

Once we find out if dataset is solvable, we can backtrack the solution.

Python program below:

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)

Output:

~$ python2 subsetsum.py
[5, 15, 5]
[2, 23]
[12, 12]

Answer 2

It is NP-Hard problem.

There is a reduction from sub-set sum
Subset Sum Problem: given a multiset S and a a number k: return true if and only if there is a subset S' of S, which sums up to exactly k.

Reduction:
Given an instance of subset sum problem at the form of (S,k), create an instance of this problem at the form (G1,G2,...,Gn,k) Where Gi is a singleton group with the element i from S, and k is the number we are seeking.

Proof:
Subset sum -> This problem: assume there is a subset S'={si_1,si_2,...,si_m} such that si_1 + si_2 + ... + si_m = k, then by choosing the one element from each group: Gi_1, Gi_2, ... , Gi_m, they sum up to k, since each Gi include only the element si.
This problem -> Subset sum: Same idea here, given there is a set of singleton groups that sums up to k, we can find out which elements in S we need to get the desired subset sum in S.

Conclusion:
This problem is NP-Hard, and there is no known polynomial solution for it. Since what you are seeking is the optimization problem for an NP-Hard problem, your optimization problem is also NP-Hard. Thus, your best shot to get an optimal solution will probably be an exponential solution, such as brute-force: just check out all possibilities, and return the best match.

Note:

• It seems from example 2 you do not need to chose an element from each group, but to chose at most one element from each group, if it is not the case - this problem is still NP-Hard, but the reduction will be a bit harder.
• all the links in my answers to wikipedia are here for future readers, since wikipedia is off-line today. If you are interested, you can search these terms on google and see the cached pages.

EDIT: exponential solution example [pseudo code]:

Note it was not tested, but the idea behind it should work: just check all possibilities for the first group, and recursively findBest() with one group less, so at the end- you exhaust all possible solutions, and return the best out of them.

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)