相关疑难解决方法(0)

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

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

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

1. 我关心有多少子集小于给定值,而不是有多少子集相等.
2. 子集大小是固定的.
3. 我关心有多少集合总和小于V,而不仅仅是否存在.

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

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