子集和算法 [英] Subset Sum algorithm

问题描述

我工作的这个问题：

该子集和问题，需要输入一个集 X = {X1，X2，...，XN} 的 N 整数和另一个整数 K 。问题是，以检查是否存在一个子集的X' X 的元素之和为氏/ code>，发现子集，如果有任何。例如，如果 X = {5,3，11，8，2} 和 K = 16 那么答案是是自集 X'= {5,11} 为一笔16 。实现一个算法的子集和它的运行时间至少为 O（NK）。

The Subset Sum problem takes as input a set X = {x1, x2 ,…, xn} of n integers and another integer K. The problem is to check if there exists a subset X' of X whose elements sum to K and finds the subset if there's any. For example, if X = {5, 3, 11, 8, 2} and K = 16 then the answer is YES since the subset X' = {5, 11} has a sum of 16. Implement an algorithm for Subset Sum whose run time is at least O(nK).

的通知复杂 O（NK）。我认为，动态规划可能会有帮助。

Notice complexity O(nK). I think dynamic programming may help.

我发现了一个指数时间的算法，但它并不能帮助。

I have found an exponential time algorithm, but it doesn't help.

有人可以帮助我解决这个问题？

Can someone help me solve this problem?

推荐答案

因为它看起来像所有的数字都为正，就可以解决这个使用动态规划：

Since it looks like all your numbers are positive, you can solve this using dynamic programming:

Start将一个布尔数组的可能尺寸K + 1与第值为true，其余假的。第i个值将重新present i的一个子集之和是否能够实现。对于每个数n在您所设定的，通过可能数组，如果第i个值为true，则设置第i + n个值循环也是如此。

Start will a boolean array possible of size K+1 with the first value true, the rest false. The ith value will represent whether a subset sum of i is possible to achieve. For each number n in your set, loop through the possible array and if the ith value is true, then set the i+nth value to true as well.

最后，如果第k值可能是真实的，那么你就可以形成k的一个子集之和。问题为O解决（NK）的时间。

At the end, if the kth value in possible is true, then you can form a subset sum of k. Problem solved in O(NK) time.

<一个href="http://en.wikipedia.org/wiki/Subset_sum_problem#Pseudo-polynomial_time_dynamic_programming_solution"相对=nofollow>维基百科上的子集和问题有这种算法应用到整数集的详细说明页面，但不保证正面的。

Wikipedia's page on the subset sum problem has a detailed explanation of this algorithm applied to sets of integers not guaranteed to be positive.

这篇关于子集和算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！