algorithm - 子集和问题的有趣变化

Question

一个工作的朋友向我介绍了子集和问题的一个有趣的变体：

给定一个大小为 n 的正整数集合 S，以及整数 a 和 K，是否存在一个（集合 S 的）子集 R，它恰好包含 a 个元素，其和等于 K？

他声称这可以用时间复杂度 O(nka) 来完成，我无法想出一个动态规划算法来实现这个运行时间。可以做到吗？

score 3 · Accepted Answer

如果 k 和 a 足够小就可以做到，这样我们就可以声明一个数组

bool found[a][k]

您将遍历 S 中的每个值并遍历找到的数组中的每个状态以获得新状态。

比如说，对于 a=1 和 k = 7 的索引，并且 S 的当前值为 7，

如果 found[1][7] 为真，那么您也可以确定 found[2][14] 也为真。

当迭代结束时，您需要做的就是检查 [a][k] 是否为真。

score 3 · Accepted Answer

令 S = {s1,\ldots,sn}

如果有可能在 s1,\ldots,sj 中找到总和为 K 的元素，则令 P(j,K,a) 为真。

那么 P(j,K,a) = P(j-1, K-sj, a-1) OR P(j, K, a)（要么需要 sj，要么不需要）。

然后，该算法包括用 a+1 填充维度为 k+1 的 n 维 3-D 表。每个条目都需要固定的时间来填充，因此时间（和空间）复杂度为 O(nKa)

2 回答 2