常和组合的数量
假设您有 n 个整数列表 L1,L2,...,Ln 和一个整数 S。
我正在寻找一种方法来有效地计算索引 j1,j2,...,jn 的组合，使得 L1[j1]+L2[j2]+...+Ln[ jn] = S。
例如，L1=[0,1,1,2]、L2=[0,1]、L3=[0,1,2,3,3] 和 S =4。 那么可能的组合是
0+1+3
0+1+3
1+0+3
1+0+3
1+1+2
1+0+3
1+0+3
1+1+2
2+0+2
2+1+1
，即我正在寻找的答案是10。
Suppose you are given n lists of integers L1,L2,...,Ln and an integer S.
I am looking for a way to efficiently count the combinations of indexes j1,j2,...,jn such that L1[j1]+L2[j2]+...+Ln[jn] = S.
As an example, take L1=[0,1,1,2], L2=[0,1], L3=[0,1,2,3,3] and S=4.
Then the possible combinations are
0+1+3
0+1+3
1+0+3
1+0+3
1+1+2
1+0+3
1+0+3
1+1+2
2+0+2
2+1+1
i.e. the answer I am looking for is 10.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
这个问题是NP完全问题。您可以
1) 暴力破解
，或者，如果您有一些额外的属性（例如，涉及的总和很小），您也可以考虑
2) 使用动态规划获得伪多项式算法。
This problem is NP complete. You can
1) Brute force it
or, if you have some extra properties (the total sums involved are small, for example) you can also consider
2) Use dynamic programming to get a pseudopolinomial algorithm.
可以用DP来解决。复杂度：O(nS)。
You can solve it with DP. Complexity: O(nS).