需要从多组列表中获得最佳和组合的算法(逻辑）

这是一个NP难题。

子集和有减少
子集和问题：给定一个多集S和一个数k：当且仅当存在S的子集S'，其总和恰好为k时，返回true。

减少：
给定(S,k)形式的子集和问题的一个实例，创建(G1,G2,...,Gn,k)形式的这个问题的实例，其中Gi是一个单例群，元素i来自S，k是我们正在寻找的数字。

证明：
子集和->这个问题：假设有一个子集S'={si_1,si_2,...,si_m}使得si_1 + si_2 + ... + si_m = k，那么通过从每组中选择一个元素：Gi_1, Gi_2, ... , Gi_m，它们加起来就是k，因为每个Gi只包括元素si。
这个问题->子集和：这里的想法是一样的，假设有一组单例群的总和达到k，我们可以找出S中的哪些元素需要在S中获得所需的子集和。

结论：
这个问题是NP难的，并且没有已知的多项式解。由于你所寻求的是NP难问题的优化问题，所以你的优化问题也是NP难的。因此，获得最佳解决方案的最佳方法可能是指数解决方案，例如暴力：只需检查所有可能性，然后返回最佳匹配。

注意：

• 从示例2中可以看出，您不需要从每个元素中选择一个元素组，但如果不是，则从每个组中最多选择一个元素这种情况-这个问题仍然是NP难的，但归约将是更难一点
• 我对维基百科的回答中的所有链接都是为未来的读者准备的，因为维基百科今天已经离线了。如果你感兴趣，你可以在谷歌上搜索这些术语，并查看缓存的页面

编辑：指数解决方案示例[伪代码]：

请注意，它没有经过测试，但它背后的想法应该是可行的：只需检查第一组的所有可能性，并在少一组的情况下递归地findBest()，所以在最后，您耗尽了所有可能的解决方案，并从中返回最佳解决方案。

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)

子集和问题采用伪多项式动态规划方法。我们可以将其映射到具有复杂度O(S*N)和O(S)空间的这个变体问题，其中S是最大和（在您的示例中为25），N是所有组中元素的总数。

这种复杂性不取决于组的总数，因此如果O(N^G)暴力解决方案不会收敛于G>=10的高值，则更适合。但请注意，此算法将不适用于S>=biginteger。

简而言之，DP递归解决方案如下：

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   

一旦我们发现数据集是否是可解的，我们就可以回溯解决方案。

下面的Python程序：

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]