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

Question

我有多组数据，比如

第 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,5,10,15
第 2 组 4,6,23,15,12
第 3 组 23,34,12,1,5

第二 (g1) 2 + (g2) 23 = 25(最佳组合)

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

第三 (g1) 15 + (g2) 6 + (g3) + 1 = 22(最佳组合)

我希望这可能有点复杂。但我可能会得到更好的解决方案。

谢谢

Answer 1

是NP-Hard问题。

从sub-set sum开始减少
子集求和问题:给定一个多重集S和一个数字k:当且仅当存在子集时返回真S 的 >S'，其总和恰好为 k。

减少:
给定(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-Hard的，没有已知的多项式解。由于您正在寻找的是 NP-Hard 问题的优化问题，因此您的优化问题也是 NP-Hard 问题。因此，获得最佳解决方案的最佳机会可能是指数解决方案，例如蛮力:只需检查所有可能性，然后返回最佳匹配。

注意:

• 从示例 2 来看，您似乎不需要从每个元素中选择一个元素组，但如果不是，则从每个组中最多选择一个元素情况 - 这个问题仍然是 NP-Hard，但减少了用力一点。
• 我对维基百科的回答中的所有链接都在这里供 future 的读者使用，因为维基百科今天已下线。如果您有兴趣，可以在 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)