子集和算法

Question

我正在研究这个问题：该子集和问题需要输入一个组X = {x1, x2 ,…, xn}的n整数和另一个整数K。问题是，以检查是否存在一个子集X'的X，它的元素之和为K，并发现该子集，如果有任何。例如，如果X = {5, 3, 11, 8, 2}和K = 16则答案是YES因为子集X' = {5, 11}的总和为16。为运行时间至少为的子集和实现一个算法O(nK)。注意复杂性O(nK)。我认为动态编程可能会有所帮助。我发现了指数时间算法，但没有帮助。有人可以帮我解决这个问题吗？

Answer 1

我建议阅读Wiki的算法。该算法存在于此，有关该解决方案，请参阅伪多项式时间动态规划解决O(P*n)方案，该解决方案不是多项式时间，在（p，n）中是多项式，但在n + log P（输入大小）中不是多项式，并且因为P可以像2 ^ n这样的非常大，解P * n =（2 ^ n）* n通常不是多项式时间解，但是当p受n的某些多项式函数限制时，就是多项式时间算法。

这个问题是NPC，但是有一个Pseudo polynomial time算法，属于weakly NP-Complete问题，也有Strongly NP-Complete问题，这意味着pseudo polynomial time除非P = NP，否则找不到任何算法，并且这个问题不在此问题范围内，所以以某种方式很容易。

我说的是尽可能简单，但这不是完全NP完全或完全NP完全问题的确切定义。