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.
Supuesto:
En aras de la simplicidad principio me hizo la suposición de que el conjunto de entrada X contiene sólo números enteros positivos y k es positivo. Sin embargo, podemos ajustar el algoritmo para manejar enteros negativos y el caso si k es negativo.
Lógica:
La clave para este algoritmo o realmente ningún problema DP se aBREAK minimizar el problema y empezar simplemente de un caso base. entonces podemos construir sobre el caso base usar algún conocimiento que sabemos:
- sabemos que si el conjunto
X está vacía, entonces no hay manera de que podamos sumar a cualquier valor de k.
- Si un conjunto
X contiene k, entonces tiene un subconjunto de suma de k.
- sabemos que si un subconjunto de conjunto
x1 que es un subconjunto de X suma a continuación k1X tendrá un subconjunto de ese sub k1 a saber x1.
- tenemos un conjunto
X = {x1, x1, x3, ......., xn, xn+1}. Sabemos que tiene una suma de subconjuntos de k1 si x1 = {x1, x1, x3, ......., xn} tiene un subconjunto de suma de k - 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 en sí es parte del conjunto
decir que tiene un conjunto x1 = {1,3,5} que es un subconjunto del conjunto X = {1,3,5,2,8}.Si x1 tiene una suma de subconjuntos a k1 = 8 entonces eso significa X también tiene una suma de subconjuntos a 8 porque x1 es un subconjunto de X
- decir que tiene un conjunto
X = {1,3,5,2,19} y queremos saber qué tiene una suma de subconjuntos a 20. Sí, y una forma de saber si eso es x1 = {1,3,5,2} puede sumar (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.
construir dinámicamente una matriz ¡Genial! ahora usemos las tres lógicas anteriores y comencemos a construir desde el caso base. Vamos a construir una matriz m. Definimos:
matriz m tiene i+1 filas y columnas k + 1.
Cada celda de la matriz tiene el valor true o false.
m [i] [s] devuelve verdadero o falso para indicar la respuesta a esta pregunta: "? Usando los primeros i elementos de la matriz podemos encontrar una suma de subconjuntos a s" m[i][s] vuelve true para sí y false sin
(tenga en cuenta la respuesta Wikipedia o la mayoría de las personas a construir una función m (i, s), pero pensé que la matriz es una manera fácil de entender la programación dinámica. funciona bien cuando sólo tenemos positivo números en el conjunto o matriz. Sin embargo, la ruta de función es mejor porque no tiene que tratar con índice fuera de rango, índice de coincidencia de la matriz y suma a la matriz .....)
Vamos a construir la matriz mediante un ejemplo:
X = {1,3,5,2,8}
k = 9
Vamos a construir la matriz fila por fila. En última instancia, deseamos saber que la celda m [n] [k] contiene true o false.
Primera Fila: Lógica 1. Nos dijo que la primera fila de la matriz debe ser todos 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 arriba: Luego de la segunda fila o por encima, podemos usar la lógica 2,3,4 para ayudarnos a poblar la matriz.
- lógica 2 nos dice que
m[i][s] = (X[i-1] == s) rememebr m [i] se refiere al elemento i-ésimo en X que es X [i-1]
- lógica 3 nos dice que
m[i][s] = (m[i-1][s]) este está mirando a la célula direclty de encima .
- lógica 4 nos dice que
m[i][s] = (m[i-1][s - X[i-1]]) esto está mirando la fila arriba y a la izquierda de las celdas X [i-1].
Si cualquiera de ellos es true continuación m[i][s] es true lo contrario false. para que podamos reescribir 2,3,4 en m[i][s] = (m[i-1][s] || a[i-1] == s || m[i-1][s - a[i-1]])
Utilice estas lógicas para llenar 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 su pregunta:
vistazo a 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 se indica por esa célula 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 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));
}
}
Para construir la matriz de 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 al respecto 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 aún 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.
Probablemente este no sea el caso general. Ver mi respuesta – marcog
-1: hay uno que se ejecuta en la complejidad que el OP quiere, por lo que su respuesta realmente no es útil y también irrelevante. – IVlad
@ivlad Un poco duro, ya que @DeadMG es técnicamente correcto. OP no declaró que el conjunto de enteros siempre es positivo, lo que asume mi respuesta. – marcog