子集和有特殊条件 [英] Subset sum with special conditions

问题描述

（之前你有一个链接到另一个SO问题答复或关闭此为重复的，请阅读问题认真，这是不是这个问题的标准变异不同，我搜索了很久，所以我pretty的肯定没有像这样在这里的问题）

(Before you reply with a link to another SO question or close this as a duplicate please read the question carefully. This is different than the standard variant of this problem and I've searched for a long time so I'm pretty sure there isn't a question like this here)

我需要找到，如果在最小的小号这是第X部分的集[I] 是> = T 的总和（一些目标值，小于全套的总和）。

I need to find if the smallest possible S that is the sum of some subset of X[i] that is >= T (some target value, smaller than the sum of the full set).

该集不是很大（约40元），但仍然过大指数回溯的解决方案。

The set isn't very large (about 40 elements), but still too big for exponential backtracking solution.

在号，总和是巨大（约10 ^ 15），因此动态规划是不行的（可能状态的数量大，因此在记忆化表将很快耗尽内存）

The numbers and the sum are huge (about 10^15), so dynamic programming won't work (The number of possible states is large so the memoization table would soon run out of memory).

有关同样的原因由Pisinger线性时间算法将无法正常工作（这是O（NR）其中r是上限的总和，这是过大在这种情况下）。

For the same reason the linear time algorithm by Pisinger won't work (it's O(nr) where r is the upper bound on the sum, which is too big in this case).

有一些确定的算法，这将有助于我在大的款项，但几号这种情况下？我不想诉诸一些近似算法。

Is there some deterministic algorithm that will help me in this case of large sum but few numbers? I don't want to resort to some approximation algorithm.

推荐答案

由于提到的条件，相信凭借的分行及放大器;结合是你最好的拍摄得到确切的解决方案。

Given the mentioned conditions, I believe a backtracking solution with branch & bound is your best shot to get the exact solution.

我们的想法是要检查所有的子集，但你可以在算法的运行过程中修剪树的计算对于一些可能的子集。

The idea is to check all subsets, but you can trim the calculation tree for some possible subsets during the run of the algorithm.

例如，假设您正在寻找 S = 10 ^ 8 ，你已经找到了溶胶= 10 ^ 8 + 10的解决方案^ 7 ，现在，你正在检查的是一些超集所有子集 X ，你发现， SUM（ X）= 10 ^ 9 。有没有必要继续检查包含 X 任何子集，就可以直接跳过他们 - 他们不会让你的最佳

For example, assume you are looking for S = 10^8, and you already found a solution of sol=10^8 + 10^7, Now, you are checking all subsets that are supersets of some X, and you find out that sum(X) = 10^9. There is no need to keep checking any subsets that contain X, you can simply skip them - they will not get you optimal.

我也想尝试并行化的解决方案，分支定界是很容易并行化通常，只需要在一段时间同步一次新的最佳解决方案。

I'd also try to parallelize the solution, branch and bound is easily parallelized usually, just need to synchronize the new best solution once in a while.

这篇关于子集和有特殊条件的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！