生成一个范围内的所有子集款项的速度比O（（K + N）* 2 ^（N / 2））？ [英] Generate all subset sums within a range faster than O((k+N) * 2^(N/2))?

问题描述

有没有一种方法来生成所有的子集款项小号<子> 1 ，S ₂ ，...，S <子> K 落在在区间[A，B]为O快（（K + N）* 2 ^{N / 2} ），其中k总和的数目也有在[A， B]？需要注意的是k的唯一已知后，我们所列举之内的所有子集款项[A，B]。

Is there a way to generate all of the subset sums s₁, s₂, ..., s_k that fall in a range [A,B] faster than O((k+N)*2^N/2), where k is the number of sums there are in [A,B]? Note that k is only known after we have enumerated all subset sums within [A,B].

我目前使用的是修改维茨 - 萨尼算法。例如，我先调用它的最小金额大于或等于A，让我来说也<子> 1 。然后，我再次调用它的下一个最小和更大的超过新<子> 1 ，让我来说也 ₂ 。重复此，直到我们找到一个和S <子> K + 1 大于B.有很多计算的每一次迭代之间重复，即使没有重建的最初两年2 ^{N / 2} 列表，所以有没有办法做的更好？

I'm currently using a modified Horowitz-Sahni algorithm. For example, I first call it to for the smallest sum greater than or equal to A, giving me s₁. Then I call it again for the next smallest sum greater than s₁, giving me s₂. Repeat this until we find a sum s_k+1 greater than B. There is a lot of computation repeated between each iteration, even without rebuilding the initial two 2^N/2 lists, so is there a way to do better?

在我的问题，N约为15，并且数字的大小是由数百万的数量级上，所以我没有考虑动态规划路线。

In my problem, N is about 15, and the magnitude of the numbers is on the order of millions, so I haven't considered the dynamic programming route.

推荐答案

检查维基百科的子集之和。据我所知，这是目前最快的算法，它运行在O（2 ^（N / 2））的时间。

Check the subset sum on Wikipedia. As far as I know, it's the fastest known algorithm, which operates in O(2^(N/2)) time.

编辑： 如果你正在寻找，而不是仅仅0多个可能的款项，你可以保存高端阵列，并通过他们只是想迭代一次（这大概是一个O（2 ^（N / 2）操作），并保存重新计算它们。所有可能子集的值不与目标变化。

If you're looking for multiple possible sums, instead of just 0, you can save the end arrays and just iterate through them again (which is roughly an O(2^(n/2) operation) and save re-computing them. The value of all the possible subsets is doesn't change with the target.

再次编辑： 我不能完全确定你想要什么。我们是否运行ķ搜索一个的独立值的每个，或寻找具有在特定范围内为K宽值的任何子集？或者是你想用第一次近似第二？

Edit again: I'm not wholly sure what you want. Are we running K searches for one independent value each, or looking for any subset that has a value in a specific range that is K wide? Or are you trying to approximate the second by using the first?

编辑回应： 是的，你得到了很多重复的工作，即使没有重建列表。但是，如果你不重建名单，这不是O（K * N * 2 ^（N / 2））。构建列表为O（N * 2 ^（N / 2））。

Edit in response: Yes, you do get a lot of duplicate work even without rebuilding the list. But if you don't rebuild the list, that's not O(k * N * 2^(N/2)). Building the list is O(N * 2^(N/2)).

如果您知道A和B，现在，你可以开始迭代，然后根本就不是当你找到正确的答案（绑定底部）停止，但继续下去，直到它超出范围。这应该是大致相同的解决之子只是一个解决方案，只涉及+ K多个op，当你完成，你可以沟名单。

If you know A and B right now, you could begin iteration, and then simply not stop when you find the right answer (the bottom bound), but keep going until it goes out of range. That should be roughly the same as solving subset sum for just one solution, involving only +k more ops, and when you're done, you can ditch the list.

更多编辑： 你有一系列的款项，从A到B首先，你解决子集和问题A.然后，只需保持迭代和存储结果，直到找到在该点停止的解决方案B，。现在你有在一次运行A和B之间的每一笔，它只会花费你在K值中的一个子集和解决问题的能力以及K业务范围内的A到B，这是线性的，很好，速度很快。

More edit: You have a range of sums, from A to B. First, you solve subset sum problem for A. Then, you just keep iterating and storing the results, until you find the solution for B, at which point you stop. Now you have every sum between A and B in a single run, and it will only cost you one subset sum problem solve plus K operations for K values in the range A to B, which is linear and nice and fast.

 s = *i + *j; if s > B then ++i; else if s < A then ++j; else { print s; ... what_goes_here? ... }

没有，没有，没有。我现在把你的问题的根源（我误解的东西），但它仍然不是复杂的，你有什么样的最初。如果您要查找的范围内的所有组合，而不是一个，你只需要遍历两个列表中的所有组合，这是不是太糟糕了。

No, no, no. I get the source of your confusion now (I misread something), but it's still not as complex as what you had originally. If you want to find ALL combinations within the range, instead of one, you will just have to iterate over all combinations of both lists, which isn't too bad.

请原谅我使用的汽车的。的C ++ 0x的编译器。

Excuse my use of auto. C++0x compiler.

std::vector<int> sums;
std::vector<int> firstlist;
std::vector<int> secondlist;
// Fill in first/secondlist.
std::sort(firstlist.begin(), firstlist.end());
std::sort(secondlist.begin(), secondlist.end());
auto firstit = firstlist.begin();
auto secondit = secondlist.begin();
// Since we want all in a range, rather than just the first, we need to check all combinations. Horowitz/Sahni is only designed to find one.
for(; firstit != firstlist.end(); firstit++) {
    for(; secondit = secondlist.end(); secondit++) {
        int sum = *firstit + *secondit;
        if (sum > A && sum < B)
            sums.push_back(sum);
    }
}

这仍然不是很大。但是，如果事先知道可以优化N是非常大的，例如，映射或hashmapping款项到迭代器，使得任何给定的firstit可以找到任何合适的合作伙伴在secondit，减少了运行时间。

It's still not great. But it could be optimized if you know in advance that N is very large, for example, mapping or hashmapping sums to iterators, so that any given firstit can find any suitable partners in secondit, reducing the running time.

这篇关于生成一个范围内的所有子集款项的速度比O（（K + N）* 2 ^（N / 2））？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！