我遇到了与 子集和问题 相关的问题,想知道这三个不同点是否能使它更容易解决,即在合理的时间内解决。
给定一个值V、一个集合大小L和一个序列[1,N]S,有多少个S的大小为L的子集的和小于V?
这与子集和问题不同的三个方面是:
- 我关心有多少子集小于给定的值,而不是有多少个相等。
- 子集大小是固定的。
- 我关心有多少个子集的和小于V,而不仅仅是是否存在任何子集的和小于V。
是否有任何合理有效的算法来解决这个问题?
编辑: 显然,可以使用组合生成算法在O(N choose L)中完成。我真正感兴趣的是聪明的技巧,以显著加快它的速度。