这种子集和问题的变体更容易解决吗？

我有一个与子集求和问题有关的问题,我想知道差异是否更容易,即在合理的时间内可解决.

给定一个值V,一个集合大小L和一个数字序列[1,N] S,S总和的多少个L子集总和小于V？

这与子集求和问题有三种不同:

我关心有多少子集小于给定值,而不是有多少子集相等.

子集大小是固定的.

我关心有多少集合总和小于V,而不仅仅是否存在.

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

编辑:显然,这可以使用组合生成算法在O(N选择L)中完成.我真正感兴趣的是聪明的黑客,以显着加快它的速度.

(您的问题的决定版本)仍然是NP完整的.我们的想法是,如果我们可以解决你的问题,那么(对于每个子集大小,比方说),我们可以询问有多少集合总和小于V以及多少总和小于V-1,并且这两个数字的差异将是告诉我们是否是精确到V的子集 - 因此我们可以解决子集和问题.[这不是一个完整的证明,因为它是图灵减少,而不是很多减少.]

但是,有一个简单的动态编程解决方案,它在时间O(nLV)内运行.[这不能证明P = NP的原因是V在输入大小中可能是指数的:使用n位,您可以表示高达2 ^n的值.但假设您的V不是指数,这不是问题.]

令num [v] [k] [i]表示S的前i个元素的大小k子集的数量,它们总和为v.您可以将它们计算为(对于每个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个元素.(任何与v相加的大小为k的集合都不使用S [i],因此它在num [v] [k] [i-1]中计数,或者它使用S [i],这意味着其余的子集具有k-1个元素,仅使用序列中的第一个i-1个数,并求和为vS [i].)最后,对于每个小于V的v计数num [v] [L] [| S |] ; 那是你的答案.

此外,如果您仔细地执行此操作,则可以省略第三个下标(为每个i向下运行循环等); 为清楚起见,我只包括它.