（在您回复另一个问题的链接或将其作为重复项关闭之前，请仔细阅读该问题。这与该问题的标准变体不同，我已经搜索了很长时间，所以我很确定没有这里没有这样的问题）
我需要找到是否最小可能的S这是一些的总和X[i] 的子集那是>= T（某个目标值，小于全套的总和）。
该集合不是很大（大约 40 个元素），但对于指数回溯解决方案来说仍然太大。
The 数字和总和是巨大的（大约10^15），所以动态编程不起作用（可能的状态数量很大，所以记忆表很快就会耗尽内存）。
出于同样的原因，Pisinger 的线性时间算法不起作用（它是 O(nr)，其中 r 是总和的上限，在这种情况下太大）。
在这种总和很大但数字很少的情况下，是否有一些确定性算法可以帮助我？我不想诉诸某种近似算法。
鉴于上述条件，我相信回溯解决方案分支定界 http://en.wikipedia.org/wiki/Branch_and_bound是您获得精确解决方案的最佳机会。
这个想法是检查所有子集，但您可以在算法运行期间修剪计算树以获取一些可能的子集。
例如，假设您正在寻找S = 10^8，并且您已经找到了解决方案sol=10^8 + 10^7，现在，您正在检查某些子集的超集X，你会发现sum(X) = 10^9。无需继续检查包含以下内容的任何子集X，你可以简单地跳过它们 - 它们不会让你达到最佳状态。
我还尝试并行化解决方案，分支定界通常很容易并行化，只需要偶尔同步新的最佳解决方案。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
