给定一组数字:
156, 434, 600
如何找到超过 500 的最大组数?它允许您甚至只包含一个元素来创建一个组。但不允许在组间重复使用一个元素。所以,在上面的例子中,答案是:
2 // {156, 434}, {600}
我希望当我得到另一组具有不同大小的数字时,我希望制定一个通用算法可以应用它。
- 156、434、600
- 642、324、174、100、452
- 174、100、455、900、1200、341
但我不知道应该从哪里开始。所以,请帮我想出一个好主意。
最佳答案
一种方法可能是对最佳解决方案的 bin 数量进行二分搜索,每次对多子集求和问题(例如 https://www.researchgate.net/publication/262408639_The_Multiple_Subset_Sum_Problem 1)使用多项式时间近似方案。
<子>1。多子集和问题; Alberto Caprara、Hans Kellerer 和 Ulrich Pferschy; SIAM 优化杂志 卷。 11:问题。 2:页面。 308-319 (发行日期:2000年)
关于algorithm - 找到满足特定条件的最大集合数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/48021805/