子集和问题的有趣变化
工作中的一个朋友向我提出了子集和问题的一个有趣的变体：
给定一组大小为 n 的正整数集合 S 以及整数 a 和 K，是否存在一个子集 R（集合 S 的）包含 <恰好有一个元素，其总和等于 K？
他声称这可以以时间复杂度 O(nka) 完成，我无法想出实现这个运行时间的动态规划算法。能做到吗？
An interesting variation of the subset sum problem was presented to me by a friend from work:
Given a set S of positive integers, of size n, and integers a and K, is there a subset R (of the set S) that contains exactly a elements, whose sum is equal to K?
He claims that this can be done with time complexity O(nka), I was unable to come up with a dynamic programming algorithm that achieved this running time. Can it be done?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果 k 和 a 足够小，那么我们就可以声明一个数组。
您将迭代 S 中的每个值，并迭代 found 数组中的每个状态以获得新状态。
比如说，对于索引 a=1 和 k = 7，并且 S 的当前值为 7，
如果found[1][7] 为真，那么您也可以确定found[2][14] 也是真的。
当迭代结束时，您所需要做的就是检查 [a][k] 是否为真。
It can be done if k and a are small enough, so that we can declare an array
You would iterate over each value in S and iterate over every state in the found array to obtain a new state.
Say, for the indexes of a=1 and k = 7, and the current value from S being 7,
if found[1][7] is true, then you can also be sure that found[2][14] is also true.
When the iteration ends, all you need to do is check that [a][k] is true or not.
设 S = {s1,\ldots,sn}
设 P(j,K,a) 为真，当且仅当可以在 s1,\ldots,sj 中找到总和为 K 的元素。
则 P(j,K, a) = P(j-1, K-sj, a-1) OR P(j, K, a) （sj 要么需要，要么不需要）。
该算法包括用 K+1 和 a+1 填充维度为 n 的 3-D 表。每个条目需要恒定的时间来填充，因此时间（和空间）复杂度为 O(nKa)
Let S = {s1,\ldots,sn}
Let P(j,K,a) be true iff it is possible to find a elements in s1,\ldots,sj that sum up to K.
Then P(j,K,a) = P(j-1, K-sj, a-1) OR P(j, K, a) (either sj is needed or it is not needed).
The algorithm then consists of filling out 3-D table of dimension n by K+1 by a+1. Each entry takes constant time to fill, hence the time (and space) complexity is O(nKa)