需要用于从多组列表

最好总和组合算法（逻辑）我有多组数据的等需要用于从多组列表

组别1 2,3,5,10,15
第2组4,6,23,15,12
组3 23,34,12,1,5

我需要从那些3基等最好总和（例如总和（G1 + G2 + G3）< = 25）

第一（G1）5 +（ g2）15 +（g3）+ 5 = 25（最佳组合）

现在，对于下一组组合的，没有必要用上述的值从每个相应的组

组别1 2,3，，10,15
Group2的4,6,23，15 ，12
第3组23,34,12,1，

第二（G1）2 +（G2）23 = 25（最佳组合）

组别1 2 ，3，，10,15
第2组4,6，，，12
第3组23,34,12,1，

第三（G1）15 +（G2 ）6 +（g3）+ 1 = 22（最佳组合）

我希望这可能有点复杂。但我可能会为这个问题找到更好的解决方案。

谢谢

来源

2012-01-18 bala

什么是最好的？最大的总和不超过目标？ – 2012-01-18 07:00:10

看起来是一个很好的动态规划任务... – J0HN 2012-01-18 07:20:55

这是NP-Hard的问题。

有来自sub-set sum
子集和问题减少：给定一个多重S和一些k：当且仅当有一个子集的SS'，它总结了准确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-Hard问题的优化问题，你的优化问题也是NP-Hard。因此，获得最佳解决方案的最佳方案可能是一种指数解决方案，如暴力破解：只需查看所有可能性，然后返回最佳匹配。

注：

似乎从例如2你不需要从每个组选择了一个元素，但最多一个元素，从每个组选择，如果不是的情况下 - 这个问题仍然是NP-Hard，但减少的难度会更大。
我在维基百科答案中的所有链接都在这里供将来的读者阅读，因为今天维基百科是脱机的。如果您有兴趣，可以在google上搜索这些条款并查看缓存的页面。

编辑：指数解例如[伪代码]：

注意它并没有进行测试，但它背后的想法应该是公正的检查第一组的所有可能性，并与一个递归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)

来源

2012-01-18 07:21:30 amit

蛮力解决方案的复杂性是'O（n^g）'，其中g =组的总数，n =一组中的元素总数 – 2012-01-18 08:15:30

@RajendranT：实际上它是'O（（n + 1）^ g）'。[我们也检查没有元素被选中]。我想不出一个更好的解决方案，但是如果存在一个问题，那么在我向这个问题展示相同的约简的情况下，我们可以更好地解决子集总和，然后是'O（2^n'）[或者小o表示：o（ 2^n）'] – amit 2012-01-18 08:31:40

谢谢阿米特。任何一个可以在php或c/C++中转换上述算法 – bala 2012-01-19 10:18:10

子集和问题有一个伪多项式动态规划方法。我们可以将其映射到此变体问题，其复杂度为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]

来源

2012-01-20 07:05:47

需要用于从多组列表

回答

相关问题