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

Question

工作中的一位 friend 向我介绍了子集和问题的一个有趣变体:

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

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

Answer 1

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

bool found[a][k]

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

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

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

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