Tag: 子集和

子集合algorithm

我正在处理这个问题： 子集和问题以input为n整数的集合X = {x1, x2 ,…, xn}和另一个整数K 问题是检查是否存在X'的子集X' ，其元素总和为K ，如果有的话find子集。 例如，如果X = {5, 3, 11, 8, 2}且K = 16那么答案是YES因为子集X' = {5, 11}具有16的和。 实现运行时间至less为O(nK)的algorithm。 注意复杂度O(nK) 。 我认为dynamic编程可能会有帮助。 我发现了一个指数时间algorithm，但它没有帮助。 有人可以帮我解决这个问题吗？