测试集合中的 k 个元素之和是否达到某个数字
有没有办法确定集合中的 k 个元素在多项式时间内加起来是否达到某个数字？
Is there a way to determine if k elements of a set add up to a certain number in polynomial time?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
数字有多大？
这是众所周知的 NP 完全子集和问题的变体。然而，如果子集可以采用的可能值集合按多项式增长，动态规划技术将使其成为多项式。对于一般整数来说，这是不正确的。但从有限范围内挑选数字的情况经常令人惊讶地发生。
How big is the number?
This is a variation on the subset sum problem, which is well-known and NP-complete. However dynamic programming techniques will make it polynomial if the set of possible values that the subsets can take grows polynomially. Which with general integers, isn't true. But with numbers picked from a restricted range happens surprisingly often.