子集和算法子集、算法

2023-09-10 22:29:34 作者:朩冇魚芄朩冇粗緬

我工作的这个问题:

该子集和问题,需要输入一个集 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.