Algoritmo de sum de subconjuntos

Estoy trabajando en este problema:

El problema de sum de subconjuntos toma como entrada un conjunto X = {x1, x2 ,…, xn} de n enteros y otro entero K El problema es comprobar si existe un subconjunto X' de X cuyos elementos sumn K y encuentra el subconjunto si hay alguno. Por ejemplo, si X = {5, 3, 11, 8, 2} y K = 16 entonces la respuesta es YES ya que el subconjunto X' = {5, 11} tiene una sum de 16 . Implemente un algoritmo para la Suma del subconjunto cuyo tiempo de ejecución sea al menos O(nK) .

Observe la complejidad O(nK) . Creo que la progtwigción dinámica puede ayudar.

He encontrado un algoritmo de tiempo exponencial, pero no ayuda.

¿Alguien puede ayudarme a resolver este problema?

    Como parece que todos sus números son positivos, puede resolver esto usando progtwigción dinámica:

    Comenzará una matriz booleana possible de tamaño K + 1 con el primer valor verdadero, el rest falso. El i-ésimo valor representará si es posible lograr una sum de subconjuntos de i. Para cada número n en su conjunto, recorra la possible matriz y si el valor i-ésimo es verdadero, establezca el valor de i + n en verdadero también.

    Al final, si el valor k en possible es verdadero, entonces puede formar una sum de subconjuntos de k. Problema resuelto en el tiempo O (NK).

    La página de Wikipedia sobre el problema de sum de subconjuntos tiene una explicación detallada de este algoritmo aplicado a conjuntos de enteros que no se garantiza que sean positivos.

    Esta pregunta se ve más de 36000 veces, pero no veo una respuesta suficiente que explique el algoritmo en detalle con la lógica. Así que pensé en hacer un bash de hacerlo.

    Suposición:

    En aras de la simplicidad, primero hice la suposición de que el conjunto de entrada X contiene solo enteros positivos k es positivo. Sin embargo, podemos ajustar el algoritmo para manejar enteros negativos y el caso si k es negativo.

    Lógica:

    La clave de este algoritmo o realmente cualquier problema de DP es romper el problema y comenzar simplemente desde un caso base. entonces podemos construir sobre el caso base usando algún conocimiento que sepamos:

    1. sabemos que si el conjunto X está vacío, entonces no hay forma de que podamos sumr cualquier valor de k .
    2. Si un conjunto X contiene k entonces tiene una sum de subconjuntos a k .
    3. sabemos que si un subconjunto del conjunto x1 que es un subconjunto de X sum a k1 entonces X tendrá un subconjunto que sub a k1 es decir x1 .
    4. tenemos un conjunto X = {x1, x1, x3, ......., xn, xn+1} . Sabemos que tiene una sum de subconjuntos a k1 si x1 = {x1, x1, x3, ......., xn} tiene una sum de subconjuntos en k - k1 .

    Ejemplo para ilustrar 1,2,3,4:

    1. es fácil. si tienes un conjunto vacío {}. no puede tener un subconjunto, por lo tanto, no puede tener ninguna sum de subconjuntos.
    2. Un conjunto X = {4} tiene una sum de subconjuntos a 4 porque 4 es uno de los conjuntos

    3. Supongamos que tiene un conjunto x1 = {1,3,5} que es un subconjunto del conjunto X = {1,3,5,2,8} . si x1 tiene una sum de subconjuntos en k1 = 8 , eso significa que X también tiene una sum de subconjuntos en 8 porque x1 es un subconjunto de X

    4. Digamos que tiene un conjunto X = {1,3,5,2,19} y queremos saber si tiene un subconjunto sum 20. Lo hace y una forma de saber si eso es x1 = {1,3,5,2} puede sumr a (20 – 19) = 1. Dado que x1 tiene un subconjunto sum a 1, entonces cuando agreguemos 19 al conjunto x1 podemos tomar ese nuevo número 1 + 19 = 20 para crear nuestra sum deseada 20.

    Desarrollar dinámicamente una matriz Cool! ahora usemos las tres lógicas anteriores y comencemos a construir desde el caso base. Vamos a construir una matriz m . Definimos:

    • la matriz m tiene i+1 filas y k + 1 columnas.

    • Cada celda de la matriz tiene un valor true o false .

    • m [i] [s] devuelve verdadero o falso para indicar la respuesta a esta pregunta: “usando los primeros i elementos en la matriz ¿podemos encontrar una sum de subconjuntos en s ?” m[i][s] devuelve true para sí y false por no

    (tenga en cuenta que la respuesta de Wikipedia o la mayoría de las personas crean una función m (i, s) pero creo que la matriz es una manera fácil de entender la progtwigción dinámica. Funciona bien cuando solo tenemos números positivos en el conjunto o conjunto. la ruta de función es mejor porque no tiene que tratar con índice fuera de rango, coincide con el índice de la matriz y sum a la matriz …)

    Vamos a construir la matriz usando un ejemplo:

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

    Vamos a construir la matriz fila por fila. En última instancia, queremos saber si la celda m [n] [k] contiene true o false .

    Primera fila: lógica 1. nos dijo que la primera fila de la matriz debería ser false .

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

    Segunda fila y superior: Luego, para la segunda fila o superior, podemos usar la lógica 2,3,4 para ayudarnos a poblar la matriz.

    • la lógica 2 nos dice que m[i][s] = (X[i-1] == s) rememebr m [i] se refiere al i-ésimo ítem en X que es X [i-1]
    • La lógica 3 nos dice que m[i][s] = (m[i-1][s]) esto está mirando la dirección de la celda de arriba.
    • La lógica 4 nos dice que m[i][s] = (m[i-1][s - X[i-1]]) está mirando la fila arriba y a la izquierda de las celdas X [i-1].

    Si alguno de estos es true , m[i][s] es true contrario es false . entonces podemos reescribir 2,3,4 en m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]])

    Use estas lógicas anteriores para poblar la matriz m . En nuestro ejemplo, se ve así.

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

    Ahora usa la matriz para responder a tu pregunta:

    mira m[5][9] que es la pregunta original. usando los primeros 5 ítems (que son todos los ítems) ¿podemos encontrar una sum de subconjuntos en 9 (k)? y la respuesta es indicada por esa celda que es true

    Aquí está el Código:

     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 bounds: -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 bounds. (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)); } } 

    Para construir la matriz m toma O ((n + 1) (k + 1)) que es O (nk). parece que debería ser un polinomio, ¡pero no lo es! En realidad es un pseudo polinomio. Lea sobre esto aquí

    De nuevo, esto solo funciona si la entrada solo contiene números positivos. Usted puede modificarlo fácilmente para trabajar con números negativos aunque. La matriz todavía tendría n + 1 filas pero B - A + 1 columnas. Donde B es el límite superior y A es el límite inferior (+1 para incluir cero). La matriz todavía sería Usted tendría que compensar s con el límite inferior.

    Es bastante difícil explicar el problema de DP sobre el texto de principio a fin. Pero espero que esto ayude a aquellos que intentan entender este problema.

    Sugeriría leer el algoritmo de Wiki . El algoritmo existe allí, vea la solución de progtwigción dinámica de tiempo Pseudo-polinomial para la solución O(P*n) . La solución no es tiempo polinomial, es polinomial en (p, n) pero no es polinomial en n + log P (tamaño de entrada) y porque P puede ser muy grande como 2 ^ n, la solución P * n = (2 ^ n) * n no es una solución de tiempo polinomial en general, pero cuando p está limitada por alguna función polinómica de n es el tiempo polinomial algoritmo.

    Este problema es NPC, pero hay un algoritmo de Pseudo polynomial time para él, y pertenece a weakly NP-Complete . También hay Strongly NP-Complete , lo que significa que no puedes encontrar ningún algoritmo de pseudo polynomial time para ellos a menos que P = NP, y este problema no está en esta gama de problemas, así que de alguna manera es fácil.

    Dije que esto es lo más simple posible, pero no es una definición exacta de un problema Completamente NP-Completo o Débilmente NP-Completo.

    Para detalles ver Garey y Johnson capítulo 4.

    No existe un algoritmo conocido para la sum de subconjuntos que se ejecute en menos de O (2 ^ (n / 2)), en el caso general.

     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) ; } 

    La solución DP con matriz unidimensional (orden de procesamiento de matriz DP importa aquí).

     bool subsetsum_dp(vector& 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; } 

    deje que M sea la sum de todos los elementos. Tenga en cuenta que 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]]; 

    Entonces simplemente prueba para m [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)); } 

    Considera el i-ésimo elemento. O contribuirá para la sum del subconjunto o no. si contribuye para la sum, entonces el “valor de sum” se reduce en el valor igual al elemento i-ésimo. Si no contribuye, entonces necesitamos buscar el “valor de sum” en los elementos restantes.

    Las respuestas anteriores son geniales, pero en realidad no brindan la descripción más amplia de cómo algo así podría funcionar para números positivos y negativos.

    Dado un conjunto ordenado de enteros, defina dos variables X e Y de manera que

    X = sum de elementos negativos

    Y = sum de elementos positivos

    y opere en su conjunto inicial como si estuviera recurriendo a través de un árbol binario mediante la aplicación de estas reglas en este orden

    1. Si el elemento de la derecha es igual a la sum que está tratando de verificar, devuelve verdadero
    2. Recurse a la izquierda si al hacerlo no sale del conjunto vacío, suelte el elemento más a la derecha de su matriz ordenada
    3. Si queda un elemento en tu conjunto y no es la sum, devuelve falso
    4. En lugar de recurrir a la derecha, verifique la sum de todos los elementos en la matriz q, si X < = B <= Y luego devuelve verdadero, si no es falso
    5. Si el subárbol izquierdo o la ‘recursividad’ derecha devuelve verdadero, entonces devuelva verdadero al padre

    Las respuestas anteriores son más detalladas y precisas, pero para una visión muy amplia de cómo debería funcionar, dibuje un árbol binario. ¿Qué sugiere la longitud de esto sobre el tiempo de ejecución?