子集合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，但它没有帮助。

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

由于它看起来像所有的数字是正面的，你可以使用dynamic编程来解决这个问题：

开始将一个布尔数组possible的大小K + 1与第一个值为真，其余假。 第i个值将表示i的子集总和是否可能实现。 对于你的集合中的每个数字n，循环遍历possible数组，如果第i个值为真，那么也将第i + n个值设置为真。

最后，如果possible的第k个值是真的，则可以形成k的子集和。 在O（NK）时间解决问题。

维基百科的页面上的子集和问题有一个详细的解释这个algorithm适用于整数集合不保证是积极的。

我build议阅读Wiki的algorithm。 该algorithm存在，见O(P*n)解的伪多项式时间dynamic规划解 ，该解不是多项式时间，是（p，n）中的多项式，但在n + log P中不是多项式input），并且因为P可以像2 ^ n那样非常大，所以解P * n =（2 ^ n）* n一般不是一个多项式时间解，但是当p由n的多项式函数界定时是多项式时间algorithm。

这个问题是NPC，但是它有一个Pseudo polynomial timealgorithm，属于weakly NP-Complete问题，也存在Strongly NP-Complete问题，也就是说，除非有它们，否则你不能find任何pseudo polynomial timealgorithmP = NP，这个问题不在这个范围内，所以不知何故很简单。

我尽可能简单地说过这一点，但这不是一个强烈NP完全或弱NP完全问题的确切定义。

详情请参阅Garey and Johnson第4章。

这个问题被观看36000+次，但我没有看到足够的答案，详细解释了algorithm的逻辑。 所以我觉得我试图这样做。

假设：

为了简单起见，我首先假设input集合X只包含正整数，而k是正整数。 但是，我们可以调整algorithm来处理负整数，如果k是负值，则可以调整。

逻辑：

这个algorithm或真正的DP问题的关键是要解决这个问题，并从一个基本案例开始。 那么我们可以使用我们知道的一些知识来构build基础案例：

  1. 我们知道如果集合X是空的，那么我们就不可能求和任何k值。
  2. 如果一个集合X包含k那么它有一个子集和k 。
  3. 我们知道如果x1一个子集是x1的一个子集，那么X将会有一个子集k1即x1 。
  4. 我们有一个集合X = {x1, x1, x3, ......., xn, xn+1} 。 我们知道，如果x1 = {x1, x1, x3, ......., xn}有一个子集和k - k1 x1 = {x1, x1, x3, ......., xn}那么它有一个子集和k - k1 。

举例说明1,2,3,4：

  1. 这很容易。 如果你有一个空集{}。 你不能有一个子集，因此你不能有任何子集的总和。

  2. 集合X = {4}的子集和为4，因为它自己是集合的一部分

  3. 假设你有一个集合x1 = {1,3,5} ，它是集合X = {1,3,5,2,8}一个子集。 如果x1的子集和为k1 = 8那么这意味着X也有一个子集和为8，因为x1是X一个子集

  4. 说你有一个集合X = {1,3,5,2,19} ，我们想知道它是否有一个子集总和为20.它确实有一种方法可以知道这是否是x1 = {1,3,5,2}可以和（ x1 = {1,3,5,2} ）= 1。由于x1的子集和为1，所以当我们将19加到集合x1时，我们可以取这个新的数字1 + 19 = 20来创build我们所需的总和20。

dynamic构build一个matrix酷！ 现在让我们利用上述三个逻辑从基础案例开始build设。 我们要build立一个matrixm 。 我们定义：

  • matrixm有i+1行和k + 1列。

  • matrix的每个单元格的值true或false 。

  • m [i] [s]返回true或者false来表示这个问题的答案：“使用数组中的第一个i项，我们可以finds的子集和？” m[i][s] false的没有

（注意维基百科的答案或大部分人build立了一个函数m（i，s），但是我认为matrix是理解dynamic规划的一个简单方法，当我们在集合或者数组中只有正数的时候，函数路由更好，因为你不必处理索引超出范围，匹配索引的数组和总和matrix…..）

让我们用一个例子来构buildmatrix： 

 X = {1,3,5,2,8} k = 9

我们将逐行build立matrix。 我们最终想知道单元格m [n] [k]包含true或者false 。

第一行：逻辑1.告诉我们matrix的第一行应该全是false 。 

  0 1 2 3 4 5 6 7 8 9 _ _ _ _ _ _ _ _ _ _ 0| FFFFFFFFFF 1| 2| 3| 4| 5|

第二行及以上：然后对于第二行或以上，我们可以使用逻辑2,3,4来帮助我们填充matrix。

  • 逻辑2告诉我们m[i][s] = (X[i-1] == s) rememebr m [i]指的是X中的第i项X [i-1]
  • 逻辑3告诉我们， m[i][s] = (m[i-1][s])这是看上面的cell直接。
  • 逻辑4告诉我们， m[i][s] = (m[i-1][s - X[i-1]])看着X [i-1]单元的上面和左边的行。

如果其中任何一个是true那么m[i][s]是true否则是false 。 所以我们可以把2,3,4重写成m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]])

使用上面的这些逻辑来填充matrixm 。 在我们的例子中，它看起来像这样。 

  0 1 2 3 4 5 6 7 8 9 _ _ _ _ _ _ _ _ _ _ 0| FFFFFFFFFF 1| FTFFFFFFFF 2| FTFTTFFFFF 3| FTFTTTTFTT 4| FTTTTTTTTT 5| FTTTTTTTTT

现在使用matrix来回答你的问题：

看这是原来的问题m[5][9] 。 使用前5项（这是所有的项目），我们可以find一个子集和9（k）？ 答案由那个单元表示

代码如下： 

 import java.util.*; public class SubSetSum { public static boolean subSetSum(int[] a, int k){ if(a == null){ return false; } //n items in the list int n = a.length; //create matrix m boolean[][] m = new boolean[n + 1][k + 1]; //n + 1 to include 0, k + 1 to include 0 //set first row of matrix to false. This also prevent array index out of bounce: -1 for(int s = 0; s <= k; s++){ m[0][s] = false; } //populate matrix m for(int i = 1; i <= n; i++){ for(int s = 0; s <= k; s++){ if(s - a[i-1] >= 0){ //when it goes left we don't want it to go out of bouce. (logic 4) m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]]); } else { m[i][s] = (m[i-1][s] || a[i-1] == s); } } } //print matrix print(m); return m[n][k]; } private static void print(boolean[][] m){ for(int i = 0; i < m.length; i++){ for(int j = 0; j < m[i].length; j++){ if(m[i][j]){ System.out.print("T"); } else { System.out.print("F"); } } System.out.print("\n"); } } public static void main(String[] args){ int[] array = {1,3,5,2,8}; int k = 9; System.out.println(subSetSum(array,k)); } }

构造matrixm取O（n + 1）（k + 1），即O（nk）。 它似乎应该是多项式，但它不是！ 这实际上是伪多项式。 在这里阅读

再次，这只有在input只包含正数时才有效。 你可以很容易地调整它与负数tho工作。 matrix仍然有n + 1行，但B - A + 1列。 其中B是上限， A是下限（+1包括零）。matrix仍然是你必须抵消s与下限。

从头到尾对文本的DP问题进行解释是相当困难的。 但我希望这能帮助那些试图理解这个问题的人。

在一般情况下，没有已知的运算小于O（2 ^（n / 2））的子集和的algorithm。 

 void subsetSum (int arr[], int size, int target) { int i, j ; int **table ; table = (int **) malloc (sizeof(int*) * (size+1)) ; for ( i = 0 ; i <= size ; i ++ ) { table[i] = (int *) malloc (sizeof(int) * (target+1)) ; table[i][0] = 1 ; } for ( j = 1 ; j <= target ; j ++ ) table[0][j] = 0 ; for ( i = 1 ; i <= size ; i ++ ) { for ( j = 1 ; j <= target ; j ++ ) table[i][j] = table[i-1][j] || (arr[i-1] <= j && table[i-1][j-arr[i-1]] ) ; } if ( table[size][target] == 1 ) printf ( "\ntarget sum found\n" ) ; else printf ( "\nTarget sum do not found!\n" ) ; free (table) ; }

一维数组的DP解决scheme（DP数组处理顺序在这里很重要）。 

 bool subsetsum_dp(vector<int>& v, int sum) { int n = v.size(); const int MAX_ELEMENT = 100; const int MAX_ELEMENT_VALUE = 1000; static int dp[MAX_ELEMENT*MAX_ELEMENT_VALUE + 1]; memset(dp, 0, sizeof(dp)); dp[0] = 1; for (int i = 0; i < n; i++) { for (int j = MAX_ELEMENT*MAX_ELEMENT_VALUE; j >= 0; j--) { if (j - v[i] < 0) continue; if (dp[j - v[i]]) dp[j] = 1; } } return dp[sum] ? true : false; }

让M是所有元素的总和。 请注意，K <= M 

 let m be a Boolean array [0...M] set all elements of m to be False m[0]=1 for all numbers in the set let a[i] be the ith number for j = M to a[i] m[j] = m[j] | m[ja[i]];

然后简单地testingm [k] 

 boolean hasSubset(int arr[],int remSum,int lastElem){ if(remSum==0) return true; else if(remSum!=0 && lastElem<0) return false; if(arr[lastElem]>remSum) return hasSubset(arr, remSum, lastElem-1); else return (hasSubset(arr, remSum, lastElem-1) ||hasSubset(arr, remSum-arr[lastElem], lastElem-1)); }

考虑第i个元素。 要么它将贡献的子集合或不会。 如果它贡献了总和，那么“总和值”减less等于第i个元素的值。 如果它没有贡献，那么我们需要在其余元素中search“总和值”。

Interesting Posts