algorithm - problema - Algoritmo de suma de subconjuntos
problema de la suma de subconjuntos (9)
Estoy trabajando en este problema:
El problema de suma de subconjuntos toma como entrada un conjunto
X = {x1, x2 ,…, xn}denenteros y otro enteroKEl problema es comprobar si existe un subconjuntoX''deXcuyos elementos sumanKy encuentra el subconjunto si hay alguno. Por ejemplo, siX = {5, 3, 11, 8, 2}yK = 16entonces la respuesta esYESya que el subconjuntoX'' = {5, 11}tiene una suma de16. Implemente un algoritmo para la Suma del subconjunto cuyo tiempo de ejecución sea al menosO(nK).
Observe la complejidad O(nK) . Creo que la programació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 programación dinámica:
Comenzará una matriz booleana possible de tamaño K + 1 con el primer valor verdadero, el resto falso. El i-ésimo valor representará si es posible lograr una suma 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 suma de subconjuntos de k. Problema resuelto en el tiempo O (NK).
La página de Wikipedia sobre el problema de suma 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 intento 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:
- sabemos que si el conjunto
Xestá vacío, entonces no hay forma de que podamos sumar cualquier valor dek. - Si un conjunto
Xcontienekentonces tiene una suma de subconjuntos ak. - sabemos que si un subconjunto del conjunto
x1que es un subconjunto deXsuma ak1entoncesXtendrá un subconjunto que sub ak1es decirx1. - tenemos un conjunto
X = {x1, x1, x3, ......., xn, xn+1}. Sabemos que tiene una suma de subconjuntos ak1six1 = {x1, x1, x3, ......., xn}tiene una suma de subconjuntos enk - k1.
Ejemplo para ilustrar 1,2,3,4:
- es fácil. si tienes un conjunto vacío {}. no puede tener un subconjunto, por lo tanto, no puede tener ninguna suma de subconjuntos.
Un conjunto
X = {4}tiene una suma de subconjuntos a 4 porque 4 es uno de los conjuntosSupongamos que tiene un conjunto
x1 = {1,3,5}que es un subconjunto del conjuntoX = {1,3,5,2,8}. six1tiene una suma de subconjuntos enk1 = 8, eso significa queXtambién tiene una suma de subconjuntos en 8 porquex1es un subconjunto deX- Digamos que tiene un conjunto
X = {1,3,5,2,19}y queremos saber si tiene un subconjunto suma 20. Lo hace y una forma de saber si eso esx1 = {1,3,5,2}puede sumar a (20 - 19) = 1. Dado que x1 tiene un subconjunto suma a 1, entonces cuando agreguemos 19 al conjunto x1 podemos tomar ese nuevo número 1 + 19 = 20 para crear nuestra suma 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
mtienei+1filas yk + 1columnas.Cada celda de la matriz tiene un valor
trueofalse.m [i] [s] devuelve verdadero o falso para indicar la respuesta a esta pregunta: "usando los primeros
ielementos en la matriz ¿podemos encontrar una suma de subconjuntos ens?"m[i][s]devuelvetruepara sí yfalsepor 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 programació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 suma 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| F F F F F F F F F F
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| F F F F F F F F F F
1| F T F F F F F F F F
2| F T F T T F F F F F
3| F T F T T T T F T T
4| F T T T T T T T T T
5| F T T T T T T T T T
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 suma 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 here
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.
La solución DP con matriz unidimensional (orden de procesamiento de matriz DP importa aquí).
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;
}
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 = suma de elementos negativos
Y = suma 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
- Si el elemento de la derecha es igual a la suma que está tratando de verificar, devuelve verdadero
- 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
- Si queda un elemento en tu conjunto y no es la suma, devuelve falso
- En lugar de recurrir a la derecha, verifique la suma de todos los elementos en la matriz q, si X <= B <= Y luego devuelve verdadero, si no es falso
- 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?
No existe un algoritmo conocido para la suma de subconjuntos que se ejecute en menos de O (2 ^ (n / 2)), en el caso general.
Sugeriría leer el algoritmo de Wiki . El algoritmo existe allí, vea la solución de programació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.
deje que M sea la suma 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[j-a[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 suma del subconjunto o no. si contribuye para la suma, entonces el "valor de suma" se reduce en el valor igual al elemento i-ésimo. Si no contribuye, entonces necesitamos buscar el "valor de suma" en los elementos restantes.
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) ;
}