我工作的这个问题:
该子集和问题,需要输入一个集 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.
维基百科上的子集和问题有这种算法应用到整数集的详细说明页面,但不保证正面的。
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.