这是变种的子集和问题更容易解决？ [英] Is this variant of the subset sum problem easier to solve?

问题描述

我有相关的子集和问题一个问题，我想知道如果差异使它更简单，即解在一段合理的时间。

I have a problem related to the subset sum problem and am wondering if the differences make it easier, i.e. solvable in a reasonable amount of time.

给定值V，一套尺寸L，和一个数字序列[1，N] S，多少尺寸L为S总和子集，以比V少？

Given a value V, a set size L, and a sequence of numbers [1,N] S, how many size L subsets of S sum to less than V?

这是在三个方面不同于子集和问题：

This is different than the subset sum problem in three ways:

1. 我不在乎有多少子集少大于给定值，而不是有多少等于
2. 在该子集的大小是固定的。
3. 我在乎的多少设置总和小于V，而不仅仅是是否有存在。

1. I care how many subsets are less than a given value, not how many are equal.
2. The subset sizes are fixed.
3. I care how many sets sum to less than V, not just whether any exist.

有没有合理有效的算法来解决这个问题？

Is there any reasonably efficient algorithm to solve this?

编辑： 显然，这可以在O完成（N选L）使用的组合生成算法。什么我真正感兴趣的是聪明的黑客来显著加快它过去那种。

Obviously, this can be done in O(N choose L) using a combination generating algorithm. What I'm really interested in is clever hacks to significantly speed it up past that.

推荐答案

（的决定版）你的问题仍是NP完全问题。我们的想法是，如果我们能够解决问题，那么（对于每个子集大小，说）我们可以问套多少总结到小于V和多少总和小于V-1，并且在这两个数的差异将告诉我们，无论是子集的总和正好v - 输出这样我们就可以解决这个子集和问题。 [这不是一个完整的证明，因为它是一个图灵减少，不是的很多1减轻。]

(The decision version of) your problem is still NP-complete. The idea is that if we could solve your problem, then (for each subset size, say) we could ask how many sets sum to less than V and how many sum to less than V-1, and the difference of those two numbers would tell us whether are subsets that sum to exactly V -- thus we could solve the subset sum problem. [This is not a complete proof, because it's a Turing reduction, not a many one reduction.]

不过，有一个简单的动态规划的解决方案，在运行时间为O（NLV）。 [究其原因，这并不证明P = NP是使V可能是指数在输入尺寸：有n位，你可以重新present值高达2 ^N 。但假设你的V不是指数，这是没有问题的。]

However, there is a simple dynamic programming solution that runs in time O(nLV). [The reason this does not prove that P=NP is that V could be exponential in the input size: with n bits, you can represent values upto 2ⁿ. But assuming that your V is not exponential, this is not a problem.]

让NUM [V] [k]的[I]表示的S的总和诉第i个元素的大小-K亚群的数量可以计算出他们作为（每个I）：

Let num[v][k][i] denote the number of size-k subsets of the first i elements of S that sum to v. You can calculate them as (for each i):

    num[0][0][i] = 1
    for v = 1 to V:
        for k = 1 to L:
            num[v][k][i] = num[v][k][i-1] + num[v-S[i]][k-1][i-1]

其中，S [i]为您的序列中的第i个元素。 （任何一组大小为k求和到v要么不使用S [I]中，所以它在num计数的[V] [k]的[I-1]，或它使用S [i]于这意味着其余该子集具有k-1个元素，只使用第i-1号的序列中，并款项VS [I]）最后，计数NUM [V] [L]。[| S |]为各V少比V ;这就是你的答案。

where S[i] is the ith element in your sequence. (Any set of size k that sums to v either doesn't use S[i], so it's counted in num[v][k][i-1], or it uses S[i] which means that the rest of the subset has k-1 elements, uses only the first i-1 numbers in the sequence, and sums to v-S[i].) Finally, count num[v][L][|S|] for each v less than V; that's your answer.

此外，您还可以省略，如果你认真去做了第三标（运行循环向下的每个I等）;我只包括它的清晰度。

Also, you can omit the third subscript if you do it carefully (run your loop downwards for each i, etc.); I only included it for clarity.

这篇关于这是变种的子集和问题更容易解决？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！