problema de suma de subconjuntos

El problema de la suma de subconjuntos ( SSP ) es un problema de decisión en ciencias de la computación . En su formulación más general, existe un multiconjunto $S$ de números enteros y una suma objetivo $T$ y la cuestión es decidir si algún subconjunto de los enteros suma exactamente $T$ . ^{[ 1 ]} Se sabe que el problema es NP-completo . Además, algunas variantes restringidas del mismo también son NP-completas, por ejemplo: ^{[ 1 ]}

La variante en la que todas las entradas son positivas.
La variante en la que las entradas pueden ser positivas o negativas, y $T=0$ . Por ejemplo, dado el conjunto $\{-7,-3,-2,9000,5,8\}$ , la respuesta es sí porque el subconjunto $\{-3,-2,5\}$ la suma es cero.
La variante en la que todas las entradas son positivas y la suma objetivo es exactamente la mitad de la suma de todas las entradas, es decir, $T={\frac {1}{2}}(a_{1}+\dots +a_{n})$ Este caso especial de SSP se conoce como el problema de partición .

El problema SSP también puede considerarse un problema de optimización : encontrar un subconjunto cuya suma sea como máximo T y, sujeto a ello, lo más cercano posible a T. Es un problema NP-difícil, pero existen varios algoritmos que pueden resolverlo con bastante rapidez en la práctica.

El problema de la suma de subconjuntos múltiples (SSP, por sus siglas en inglés) es un caso especial del problema de la mochila y del problema de la suma de subconjuntos múltiples .

Dificultad computacional

La complejidad temporal de SSP depende de dos parámetros:

n - el número de números enteros de entrada. Si n es un número fijo pequeño, entonces es práctico realizar una búsqueda exhaustiva de la solución.
L : la precisión del problema, expresada como el número de valores binarios necesarios para plantearlo. Si L es un número fijo pequeño, existen algoritmos de programación dinámica que pueden resolverlo con exactitud.

A medida que n y L crecen, SSP es NP-difícil. La complejidad de los mejores algoritmos conocidos es exponencial en el menor de los dos parámetros n y L. El problema es NP-difícil incluso cuando todos los enteros de entrada son positivos (y la suma objetivo T es parte de la entrada). Esto se puede demostrar mediante una reducción directa de 3SAT . ^{[ 2 ]} También se puede demostrar mediante una reducción de la correspondencia tridimensional (3DM): ^{[ 3 ]}

Se nos da una instancia de 3DM, donde los conjuntos de vértices son W, X, Y. Cada conjunto tiene n vértices. Hay m aristas, donde cada arista contiene exactamente un vértice de cada uno de W, X, Y. Denotemos L := techo(log ₂ ( m +1)), de modo que L sea mayor que el número de bits necesarios para representar el número de aristas.
Construimos una instancia de SSP con m enteros positivos .s. Los enteros se describen mediante su representación binaria. Cada entero de entrada puede representarse con 3 nL bits, divididos en 3 n zonas de L bits. Cada zona corresponde a un vértice.
Para cada arista (w,x,y) en la instancia 3DM, hay un entero en la instancia SSP, en el que exactamente tres bits son "1": los bits menos significativos en las zonas de los vértices w, x e y. Por ejemplo, si n =10 y L=3, y W=(0,...,9), X=(10,...,19), Y=(20,...,29), entonces la arista (0, 10, 20) está representada por el número (2 ⁰ +2 ³⁰ +2 ⁶⁰ ).
La suma objetivo T en la instancia SSP se establece en un entero con "1" en el bit menos significativo de cada zona, es decir, (2 ⁰ +2 ¹ +...+2 ^3n-1 ).
Si la instancia 3DM tiene una coincidencia perfecta , entonces la suma de los enteros correspondientes en la instancia SSP produce exactamente T.
Por el contrario, si la instancia SSP tiene un subconjunto con una suma exactamente T, entonces, dado que las zonas son suficientemente grandes como para que no haya "transportes" de una zona a la siguiente, la suma debe corresponder a una coincidencia perfecta en la instancia 3DM.

También se sabe que las siguientes variantes son NP-difíciles:

Los enteros de entrada pueden ser tanto positivos como negativos, y la suma objetivo T = 0. Esto se puede demostrar por reducción a partir de la variante con enteros positivos. Denotemos esa variante como SubsetSumPositive y la variante actual como SubsetSumZero. Dada una instancia ( S , T ) de SubsetSumPositive, construyamos una instancia de SubsetSumZero agregando un solo elemento con valor −T . Dada una solución para la instancia SubsetSumPositive, agregar −T produce una solución para la instancia SubsetSumZero. Recíprocamente, dada una solución para la instancia SubsetSumZero, debe contener −T (ya que todos los enteros en S son positivos ) , por lo que para obtener una suma de cero, también debe contener un subconjunto de S con una suma de + T , que es una solución de la instancia SubsetSumPositive .
Los enteros de entrada son positivos y T = suma( S )/2. Esto también se puede demostrar por reducción a partir de la variante general; véase el problema de partición .

El problema de conteo análogo #SSP, que pide enumerar el número de subconjuntos que suman el objetivo, es #P-completo . ^{[ 4 ]}

Algoritmos de tiempo exponencial

Hay varias formas de resolver SSP en tiempo exponencial en n . ^{[ 5 ]}

Inclusión-exclusión

El algoritmo más ingenuo sería recorrer todos los subconjuntos de n números y, para cada uno de ellos, comprobar si la suma del subconjunto es igual al número correcto. El tiempo de ejecución es de orden $O(2^{n}\cdot n)$ , puesto que hay $2^{n}$ subconjuntos y, para comprobar cada subconjunto, necesitamos sumar como máximo n elementos.

El algoritmo se puede implementar mediante una búsqueda en profundidad de un árbol binario : cada nivel del árbol corresponde a un número de entrada; la rama izquierda corresponde a excluir el número del conjunto, y la rama derecha corresponde a incluir el número (de ahí el nombre de Inclusión-Exclusión). La memoria requerida es $O(n)$ . El tiempo de ejecución se puede mejorar mediante varias heurísticas: ^{[ 5 ]}

Procese los números de entrada en orden descendente.
Si los números enteros incluidos en un nodo determinado superan la suma del mejor subconjunto encontrado hasta el momento, el nodo se elimina.
Si la suma de los números enteros incluidos en un nodo determinado, más todos los demás números enteros, es menor que la suma del mejor subconjunto encontrado hasta el momento, el nodo se elimina.

Horowitz y Sahni

En 1974, Horowitz y Sahni ^{[ 6 ]} publicaron un algoritmo de tiempo exponencial más rápido, que se ejecuta en tiempo $O(2^{n/2})$ pero requiere mucho más espacio. $O(2^{n/2})$ . El algoritmo divide arbitrariamente los n elementos en dos conjuntos de $n/2$ cada uno. Para cada uno de estos dos conjuntos, almacena una lista de las sumas de todos $2^{n/2}$ posibles subconjuntos de sus elementos. Cada una de estas dos listas se ordena a continuación. Incluso utilizando el algoritmo de ordenación por comparación más rápido , Mergesort para este paso tardaría tiempo $O(2^{n/2}n)$ . Sin embargo, dada una lista ordenada de sumas para $k$ elementos, la lista se puede ampliar a dos listas ordenadas con la introducción de un ( $k+1$ )-ésimo elemento, y estas dos listas ordenadas se pueden fusionar en el tiempo $O(2^{k})$ Por lo tanto, cada lista se puede generar en forma ordenada en el tiempo $O(2^{n/2})$ . Dadas las dos listas ordenadas, el algoritmo puede comprobar si un elemento del primer array y un elemento del segundo array suman T en tiempo $O(2^{n/2})$ Para ello, el algoritmo recorre el primer arreglo en orden descendente (comenzando por el elemento más grande) y el segundo arreglo en orden ascendente (comenzando por el elemento más pequeño). Siempre que la suma del elemento actual del primer arreglo y el elemento actual del segundo arreglo sea mayor que T , el algoritmo pasa al siguiente elemento del primer arreglo. Si es menor que T , el algoritmo pasa al siguiente elemento del segundo arreglo. Si se encuentran dos elementos cuya suma sea T , el algoritmo se detiene. (El subproblema de la suma de dos elementos se conoce como suma de dos. ^{[ 7 ]} )

Schroeppel y Shamir

En 1981, Schroeppel y Shamir presentaron un algoritmo ^{[ 8 ]} basado en Horowitz y Sanhi, que requiere un tiempo de ejecución similar: $O(2^{n/2}\cdot (n/4))$ , mucho menos espacio - $O(2^{n/4})$ En lugar de generar y almacenar todos los subconjuntos de n /2 elementos por adelantado, particionan los elementos en 4 conjuntos de n /4 elementos cada uno, y generan subconjuntos de pares de n /2 elementos dinámicamente usando un montón mínimo , lo que produce las complejidades de tiempo y espacio anteriores ya que esto se puede hacer en $O(k^{2}\log(k))$ y espacio $O(k)$ dadas 4 listas de longitud k.

Debido a los requisitos de espacio, el algoritmo HS es práctico para hasta aproximadamente 50 enteros, y el algoritmo SS es práctico para hasta 100 enteros. ^{[ 5 ]}

Howgrave-Graham y Joux

En 2010, Howgrave-Graham y Joux ^{[ 9 ]} presentaron un algoritmo probabilístico que se ejecuta más rápido que todos los anteriores, en tiempo $O(2^{0.337n})$ utilizando el espacio $O(2^{0.256n})$ . Resuelve únicamente el problema de decisión, no puede probar que no existe solución para una suma dada y no devuelve la suma del subconjunto más cercana a T.

Las técnicas de Howgrave-Graham y Joux se extendieron posteriormente ^{[ 10 ]} llevando la complejidad temporal a $O(2^{0.291n})$ . Una generalización más reciente ^{[ 11 ]} redujo la complejidad temporal a $O(2^{0.283n})$ .

Soluciones de programación dinámica en tiempo pseudopolinomial

El problema SSP se puede resolver en tiempo pseudopolinomial utilizando programación dinámica . Supongamos que tenemos la siguiente secuencia de elementos en una instancia:

x_{1},\ldots ,x_{N}

Definimos un estado como un par ( i , s ) de enteros. Este estado representa el hecho de que

"hay un subconjunto no vacío de

x_{1},\ldots ,x_{i}

lo cual suma

s

."

Cada estado ( i , s ) tiene dos estados siguientes:

( i +1, s ), lo que implica que $x_{i+1}$ no está incluido en el subconjunto;
( i +1, s + $x_{i+1}$ ), lo que implica que $x_{i+1}$ está incluido en el subconjunto.

Partiendo del estado inicial (0, 0), es posible utilizar cualquier algoritmo de búsqueda en grafos (por ejemplo, BFS ) para buscar el estado ( N , T ). Si se encuentra el estado, entonces mediante retroceso podemos encontrar un subconjunto con una suma exactamente igual a T.

El tiempo de ejecución de este algoritmo es como máximo lineal en el número de estados. El número de estados es como máximo N veces el número de sumas posibles diferentes. Sea $A$ la suma de los valores negativos y $B$ la suma de los valores positivos; el número de sumas posibles diferentes es como máximo B - A , por lo que el tiempo de ejecución total es $O(N\cdot (BA))$ . Por ejemplo, si todos los valores de entrada son positivos y están acotados por alguna constante C , entonces B es como máximo NC , por lo que el tiempo requerido es $O(N^{2}C)$ .

Esta solución no se considera de tiempo polinomial en la teoría de la complejidad porque $BA$ No es polinómico en el tamaño del problema, que es el número de bits utilizados para representarlo. Este algoritmo es polinómico en los valores de $A$ y $B$ , que son exponenciales en su número de bits. Sin embargo, la suma de subconjuntos codificada en unario pertenece a P, ya que el tamaño de la codificación es lineal en BA. Por lo tanto, la suma de subconjuntos es solo débilmente NP-completa.

En el caso de que cada $x_{i}$ es positivo y está acotado por una constante fija $C$ , en 1999, Pisinger encontró un algoritmo de tiempo lineal con complejidad temporal $O(NC)$ (tenga en cuenta que esto es para la versión del problema donde la suma objetivo no es necesariamente cero, ya que de lo contrario el problema sería trivial). ^{[ 12 ]} En 2015, Koiliaris y Xu encontraron un determinista ${\tilde {O}}(T{\sqrt {N}})$ algoritmo para el problema de la suma de subconjuntos donde $T$ es la suma que necesitamos encontrar. ^{[ 13 ]} En 2017, Bringmann encontró un algoritmo aleatorio ${\tilde {O}}(T+N)$ algoritmo de tiempo. ^{[ 14 ]}

En 2014, Curtis y Sanches encontraron una recursión simple altamente escalable en máquinas SIMD que tenía $O(N(m-x_{\min })/p)$ tiempo y $O(N+m-x_{\min })$ espacio, donde $p$ es el número de elementos de procesamiento, $m=\min(s,\sum x_{i}-s)$ y $x_{\min }$ es el entero más bajo. ^{[ 15 ]} Esta es la mejor complejidad paralela teórica conocida hasta ahora.

Curtis y Sanches analizan una comparación de los resultados prácticos y la solución de instancias difíciles del SSP. ^{[ 16 ]}

Algoritmos de aproximación en tiempo polinomial

Supongamos que todas las entradas son positivas. Un algoritmo de aproximación al SSP tiene como objetivo encontrar un subconjunto de S con una suma de como máximo T y al menos r veces la suma óptima, donde r es un número en (0,1) llamado razón de aproximación .

Aproximación simple de 1/2

El siguiente algoritmo muy simple tiene una relación de aproximación de 1/2: ^{[ 17 ]}

Ordene las entradas por valor descendente;
Coloca el siguiente valor de entrada más grande en el subconjunto, siempre y cuando quepa allí.

Cuando este algoritmo finaliza, o bien todas las entradas están en el subconjunto (lo cual es obviamente óptimo), o bien hay una entrada que no encaja. La primera entrada que no encaja es menor que todas las entradas anteriores que están en el subconjunto y la suma de las entradas en el subconjunto es mayor que T /2; de lo contrario, la entrada también es menor que T/2 y encajaría en el conjunto. Dicha suma mayor que T/2 es obviamente mayor que OPT/2.

Esquema de aproximación de tiempo totalmente polinomial

El siguiente algoritmo alcanza, para cada $\epsilon >0$ , una relación de aproximación de $(1-\epsilon )$ Su tiempo de ejecución es polinomial en $n$ y $1/\epsilon$ . Recordemos que n es el número de entradas y T es el límite superior de la suma del subconjunto.

Inicializa una lista L para que contenga un elemento 0. para cada i desde 1 hasta n hacer sea U _i una lista que contenga todos los elementos y en L , y todas las sumas x _i + y para todos los y en L . Ordenar U _i en orden ascendente dejar L vacío Sea y el elemento más pequeño de U _i, agregue y a L para cada elemento z de U _i en orden creciente, haga // Recorte la lista eliminando números cercanos entre sí // y descarte los elementos mayores que la suma objetivo T. Si y + ε T / n < z ≤ T, entonces y = z , agregue z a L.Devuelve el elemento más grande en L.

Tenga en cuenta que sin el paso de recorte (el bucle interno "for each"), la lista L contendría las sumas de todos $2^{n}$ subconjuntos de entradas. El paso de recorte hace dos cosas:

Garantiza que todas las sumas restantes en L sean inferiores a T , por lo que son soluciones factibles al problema de la suma de subconjuntos.
Garantiza que la lista L sea "dispersa", es decir, que la diferencia entre cada dos sumas parciales consecutivas sea al menos $\epsilon T/n$ .

Estas propiedades juntas garantizan que la lista $L$ no contiene más de $n/\epsilon$ elementos; por lo tanto, el tiempo de ejecución es polinomial en $n/\epsilon$ .

Cuando el algoritmo finaliza, si la suma óptima está en $L$ , se devuelve y hemos terminado. De lo contrario, debe haberse eliminado en un paso de recorte anterior. Cada paso de recorte introduce un error aditivo de como máximo $\epsilon T/n$ , por lo que $n$ pasos juntos introducen un error de como máximo $\epsilon T$ Por lo tanto, la solución devuelta es al menos ${\text{OPT}}-\epsilon T$ lo cual es al menos $(1-\epsilon ){\text{OPT}}$ .

El algoritmo anterior proporciona una solución exacta al SSP en el caso de que los números de entrada sean pequeños (y no negativos). Si cualquier suma de los números se puede especificar con como máximo $P$ bits, entonces resolver el problema aproximadamente con $\epsilon =2^{-P}$ es equivalente a resolverlo exactamente. Entonces, el algoritmo de tiempo polinomial para la suma aproximada de subconjuntos se convierte en un algoritmo exacto con tiempo de ejecución polinomial en $n$ y $2^{P}$ (es decir, exponencial en $P$ ).

Kellerer, Mansini, Pferschy y Speranza ^{[ 18 ]} y Kellerer, Pferschy y Pisinger ^{[ 19 ]} presentan otros FPTAS para la suma de subconjuntos.

Véase también

Problema de la mochila : problema de optimización combinatoria , una generalización del SSP en la que cada elemento de entrada tiene un valor y un peso. El objetivo es maximizar el valor sujeto a un límite en el peso total .
Problema de suma de subconjuntos múltiples : problema de optimización matemática Páginas que muestran descripciones breves de destinos de redirección : una generalización del SSP en la que se deben elegir varios subconjuntos.
3SUM – Problema en la teoría de la complejidad computacional
Criptosistema de mochila Merkle-Hellman : una forma de criptografía de clave pública.

Referencias

^ Kleinberg , Jon; Tardos, Éva (2006). Diseño de algoritmos (2ª ed.). pag. 491 . ISBN 0-321-37291-3.
↑ Goodrich, Michael. "Más problemas NP-completos y NP-difíciles" (PDF) . Archivado (PDF) del original el 9 de octubre de 2022.
↑ Garey, Michael R.; Johnson , David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . Serie de libros en ciencias matemáticas (1.ª ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. MR 0519066 . OCLC 247570676 . , Sección 3.1 y problema SP1 en el Apéndice A.3.1.
↑ Filmus, Yuval (30 de enero de 2016). Respuesta a: "¿ Existe un algoritmo rápido y conocido para contar todos los subconjuntos cuya suma sea inferior a un número determinado? ". Theoretical Computer Science Stack Exchange . Cabe señalar que la cita de Filmus en apoyo de la afirmación (Faliszewski, Piotr; Hemaspaandra, Lane (2009). "The complexity of power-index comparison". Theoretical Computer Science . Elsevier. 410 : 101-107. DOI 10.1016/j.tcs.2008.09.034 ) no prueba la afirmación, sino que remite a los lectores a otra cita ( Papadimitriou, Christos (1994). Computational Complexity . Addison-Wesley: Reading, MA. Capítulo9. ISBN 0-201-53082-1 — a través de Internet Archive ), lo cual tampoco prueba explícitamente la afirmación. Sin embargo, la prueba de Papadimitriou de que SSP es NP-completo mediante la reducción de 3SAT se generaliza a una reducción de #3SAT a #SSP.
1 2 3 Korf, Richard E. ; Schreiber, Ethan L.; Moffitt, Michael D. (2014). "Partición numérica multidireccional secuencial óptima" (PDF) . Archivado (PDF) del original el 09-10-2022.
↑ Horowitz, Ellis; Sahni, Sartaj (1974). "Computing partitions with applications to the knapsack problem" (PDF) . Journal of the Association for Computing Machinery . 21 ( 2): 277– 292. doi : 10.1145/321812.321823 . hdl : 1813/5989 . MR 0354006. S2CID 16866858. Archivado (PDF) del original el 09-10-2022.
↑ "El problema de las dos sumas" (PDF) . Archivado (PDF) del original el 9 de octubre de 2022.
↑ Schroeppel, Richard; Shamir, Adi (1981-08-01). "Un algoritmo $T$ $=$ $O$ $(2$ $n$ $/2$ $)$ , $S$ $=$ $O$ $(2$ $n$ $/4$ $)$ para ciertos problemas NP-completos" . SIAM Journal on Computing . 10 (3): 456– 464. doi : 10.1137/0210033 . ISSN 0097-5397 .
↑ Howgrave-Graham, Nick; Joux, Antoine (2010). «Nuevos algoritmos genéricos para problemas de mochila difíciles». En Gilbert, Henri (ed.). Avances en criptología – EUROCRYPT 2010. Lecture Notes in Computer Science. Vol. 6110. Berlín, Heidelberg: Springer. pp. 235–256 . doi : 10.1007/978-3-642-13190-5_12 . ISBN 978-3-642-13190-5.
^ Becker, Anja; Coron, Jean-Sébastien; Joux, Antoine (2011). "Algoritmos genéricos mejorados para mochilas duras". En Patterson, Kenneth (ed.). Avances en Criptología – EUROCRYPT 2011 . Apuntes de conferencias sobre informática. vol. 6632. Berlín, Heidelberg: Springer. págs. 364– 385. doi : 10.1007/978-3-642-20465-4_21 . ISBN 978-3-642-20465-4.
↑ Bonnetain, Xavier; Bricout, Rémi; Schrottenloher, André; Shen, Yixin (2020). «Algoritmos clásicos y cuánticos mejorados para la suma de subconjuntos». En Moriai, Shiho; Wang, Huaxiong (eds.). Avances en criptología - ASIACRYPT 2020. Lecture Notes in Computer Science. Vol. 12492. Berlín, Heidelberg: Springer. pp. 633–666 . doi : 10.1007/978-3-030-64834-3_22 . ISBN 978-3-030-64833-6.
↑ Pisinger, David (1999). "Algoritmos de tiempo lineal para problemas de mochila con pesos acotados". Journal of Algorithms . 33 (1): 1– 14. doi : 10.1006/jagm.1999.1034 . MR 1712690 .
↑ Koiliaris, Konstantinos; Xu, Chao (8 de julio de 2015). "Un algoritmo de tiempo pseudopolinomial más rápido para la suma de subconjuntos". arXiv : 1507.02318 [ cs.DS ].
↑ Bringmann, Karl (2017). "Un algoritmo de tiempo pseudopolinomial casi lineal para la suma de subconjuntos". En Klein, Philip N. (ed.). Actas del Vigésimo Octavo Simposio Anual ACM-SIAM sobre Algoritmos Discretos (SODA 2017) . SIAM. págs. 1073–1084 . arXiv : 1610.04712 . doi : 10.1137/1.9781611974782.69 . ISBN 978-1-61197-478-2.
↑ Curtis, VV; Sanches, CAA (enero de 2016). "Una solución eficiente al problema de la suma de subconjuntos en GPU: Una solución eficiente al problema de la suma de subconjuntos en GPU". Concurrency and Computation: Practice and Experience . 28 (1): 95– 113. doi : 10.1002/cpe.3636 . S2CID 20927927 .
↑ Curtis, VV; Sanches, CAA (julio de 2017). "Un algoritmo de espacio reducido para el problema de suma de subconjuntos en GPU". Computers & Operations Research . 83 : 120–124 . doi : 10.1016/j.cor.2017.02.006 .
↑ Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000-02-01). "El problema de la suma de subconjuntos múltiples" . SIAM Journal on Optimization . 11 (2): 308– 319. doi : 10.1137/S1052623498348481 . ISSN 1052-6234 .
↑ Kellerer, Hans; Mansini, Renata; Pferschy, Ulrich; Speranza, Maria Grazia (2003-03-01). "Un esquema de aproximación totalmente polinomial eficiente para el problema de la suma de subconjuntos". Journal of Computer and System Sciences . 66 (2): 349– 370. doi : 10.1016/S0022-0000(03)00006-0 . ISSN 0022-0000 .
↑ Hans Kellerer; Ulrich Pferschy; David Pisinger (2004). Problemas con la mochila . Saltador. pag. 97.ISBN 9783540402862.

Lecturas adicionales

Cormen, Thomas H.; Leiserson , Charles E .; Rivest, Ronald L .; Stein, Clifford (2001) [1990]. "35.5: El problema de la suma de subconjuntos". Introducción a los algoritmos (2.ª ed.). MIT Press y McGraw-Hill. ISBN 0-262-03293-7.
Michael R. Garey y David S. Johnson (1979). Computadoras e intratabilidad: una guía a la teoría de la NP-completitud . WH Freeman. ISBN 0-7167-1045-5.A3.2: SP13, pág. 223.
Lagarias, JC; Odlyzko, AM (1985-01-01). "Resolución de problemas de suma de subconjuntos de baja densidad" . Journal of the ACM . 32 (1): 229– 246. doi : 10.1145/2455.2461 . ISSN 0004-5411 . S2CID 885632 .
Martello, Silvano; Toth, Paolo (1990). "Problema de suma de subconjuntos 4" . Problemas de la mochila: algoritmos e interpretaciones informáticas . Wiley-Interscience. pp. 105–136 . ISBN 0-471-92420-2. MR 1086874 .

[kleinberg2006p491-1] Kleinberg , Jon; Tardos, Éva (2006). Diseño de algoritmos (2ª ed.). pag. 491 . ISBN 0-321-37291-3.

[2] Goodrich, Michael. "Más problemas NP-completos y NP-difíciles" (PDF) . Archivado (PDF) del original el 9 de octubre de 2022.

[garey79-3] Garey, Michael R.; Johnson , David S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness . Serie de libros en ciencias matemáticas (1.ª ed.). Nueva York: WH Freeman and Company . ISBN 9780716710455. MR 0519066 . OCLC 247570676 . , Sección 3.1 y problema SP1 en el Apéndice A.3.1.

[4] Filmus, Yuval (30 de enero de 2016). Respuesta a: "¿ Existe un algoritmo rápido y conocido para contar todos los subconjuntos cuya suma sea inferior a un número determinado? ". Theoretical Computer Science Stack Exchange . Cabe señalar que la cita de Filmus en apoyo de la afirmación (Faliszewski, Piotr; Hemaspaandra, Lane (2009). "The complexity of power-index comparison". Theoretical Computer Science . Elsevier. 410 : 101-107. DOI 10.1016/j.tcs.2008.09.034 ) no prueba la afirmación, sino que remite a los lectores a otra cita ( Papadimitriou, Christos (1994). Computational Complexity . Addison-Wesley: Reading, MA. Capítulo9. ISBN 0-201-53082-1 — a través de Internet Archive ), lo cual tampoco prueba explícitamente la afirmación. Sin embargo, la prueba de Papadimitriou de que SSP es NP-completo mediante la reducción de 3SAT se generaliza a una reducción de #3SAT a #SSP.

[:0-5] 1 2 3 Korf, Richard E. ; Schreiber, Ethan L.; Moffitt, Michael D. (2014). "Partición numérica multidireccional secuencial óptima" (PDF) . Archivado (PDF) del original el 09-10-2022.

[6] Horowitz, Ellis; Sahni, Sartaj (1974). "Computing partitions with applications to the knapsack problem" (PDF) . Journal of the Association for Computing Machinery . 21 ( 2): 277– 292. doi : 10.1145/321812.321823 . hdl : 1813/5989 . MR 0354006. S2CID 16866858. Archivado (PDF) del original el 09-10-2022.

[7] "El problema de las dos sumas" (PDF) . Archivado (PDF) del original el 9 de octubre de 2022.

[8] Schroeppel, Richard; Shamir, Adi (1981-08-01). "Un algoritmo $T$ $=$ $O$ $(2$ $n$ $/2$ $)$ , $S$ $=$ $O$ $(2$ $n$ $/4$ $)$ para ciertos problemas NP-completos" . SIAM Journal on Computing . 10 (3): 456– 464. doi : 10.1137/0210033 . ISSN 0097-5397 .

[9] Howgrave-Graham, Nick; Joux, Antoine (2010). «Nuevos algoritmos genéricos para problemas de mochila difíciles». En Gilbert, Henri (ed.). Avances en criptología – EUROCRYPT 2010. Lecture Notes in Computer Science. Vol. 6110. Berlín, Heidelberg: Springer. pp. 235–256 . doi : 10.1007/978-3-642-13190-5_12 . ISBN 978-3-642-13190-5.

[10] Becker, Anja; Coron, Jean-Sébastien; Joux, Antoine (2011). "Algoritmos genéricos mejorados para mochilas duras". En Patterson, Kenneth (ed.). Avances en Criptología – EUROCRYPT 2011 . Apuntes de conferencias sobre informática. vol. 6632. Berlín, Heidelberg: Springer. págs. 364– 385. doi : 10.1007/978-3-642-20465-4_21 . ISBN 978-3-642-20465-4.

[11] Bonnetain, Xavier; Bricout, Rémi; Schrottenloher, André; Shen, Yixin (2020). «Algoritmos clásicos y cuánticos mejorados para la suma de subconjuntos». En Moriai, Shiho; Wang, Huaxiong (eds.). Avances en criptología - ASIACRYPT 2020. Lecture Notes in Computer Science. Vol. 12492. Berlín, Heidelberg: Springer. pp. 633–666 . doi : 10.1007/978-3-030-64834-3_22 . ISBN 978-3-030-64833-6.

[Pisinger09-12] Pisinger, David (1999). "Algoritmos de tiempo lineal para problemas de mochila con pesos acotados". Journal of Algorithms . 33 (1): 1– 14. doi : 10.1006/jagm.1999.1034 . MR 1712690 .

[13] Koiliaris, Konstantinos; Xu, Chao (8 de julio de 2015). "Un algoritmo de tiempo pseudopolinomial más rápido para la suma de subconjuntos". arXiv : 1507.02318 [ cs.DS ].

[14] Bringmann, Karl (2017). "Un algoritmo de tiempo pseudopolinomial casi lineal para la suma de subconjuntos". En Klein, Philip N. (ed.). Actas del Vigésimo Octavo Simposio Anual ACM-SIAM sobre Algoritmos Discretos (SODA 2017) . SIAM. págs. 1073–1084 . arXiv : 1610.04712 . doi : 10.1137/1.9781611974782.69 . ISBN 978-1-61197-478-2.

[15] Curtis, VV; Sanches, CAA (enero de 2016). "Una solución eficiente al problema de la suma de subconjuntos en GPU: Una solución eficiente al problema de la suma de subconjuntos en GPU". Concurrency and Computation: Practice and Experience . 28 (1): 95– 113. doi : 10.1002/cpe.3636 . S2CID 20927927 .

[16] Curtis, VV; Sanches, CAA (julio de 2017). "Un algoritmo de espacio reducido para el problema de suma de subconjuntos en GPU". Computers & Operations Research . 83 : 120–124 . doi : 10.1016/j.cor.2017.02.006 .

[:1-17] Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000-02-01). "El problema de la suma de subconjuntos múltiples" . SIAM Journal on Optimization . 11 (2): 308– 319. doi : 10.1137/S1052623498348481 . ISSN 1052-6234 .

[18] Kellerer, Hans; Mansini, Renata; Pferschy, Ulrich; Speranza, Maria Grazia (2003-03-01). "Un esquema de aproximación totalmente polinomial eficiente para el problema de la suma de subconjuntos". Journal of Computer and System Sciences . 66 (2): 349– 370. doi : 10.1016/S0022-0000(03)00006-0 . ISSN 0022-0000 .

[knapsack-19] Hans Kellerer; Ulrich Pferschy; David Pisinger (2004). Problemas con la mochila . Saltador. pag. 97.ISBN 9783540402862.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 18 ]

[ 19 ]