我有多组数据,比如
第 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(最佳组合)
我希望这可能有点复杂。但我可能会得到更好的解决方案。
谢谢
最佳答案
是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)
关于php - 需要从多组列表中获得最佳总和组合的算法(逻辑),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8906341/