El problema de la mochila

El problema de la mochila (también problema de la mochila ) es un problema de optimización combinatoria NP-completo . Obtuvo su nombre del objetivo final: poner tantas cosas valiosas como sea posible en una mochila, siempre que la capacidad de la mochila sea limitada. Se pueden encontrar diversas variaciones del problema de la mochila en economía , matemáticas aplicadas , criptografía y logística .

En general, el problema se puede formular de la siguiente manera: de un conjunto dado de artículos con las propiedades "costo" y "peso", se requiere seleccionar un subconjunto con el costo total máximo, observando la restricción sobre el peso total.

El planteamiento clásico del problema

Deje que haya un conjunto de objetos, cada uno de los cuales tiene dos parámetros: masa y valor. También hay una mochila con cierta capacidad de carga. La tarea es construir una mochila con el valor máximo de los artículos dentro, respetando el límite de la mochila en la masa total.

Matemáticamente, el problema se formula de la siguiente manera: hay carga. Para cada carga, se determina su masa y valor . El límite del peso total de los artículos en una mochila lo establece la capacidad de carga . Necesario $norte$ $i$ $w_{i}>0$ $v_{i}>0$ $i=1,2,...,n$ $W$

maximizar

{\ estilo de visualización \ suma _ {i = 1} ^ {n} v_ {i} x_ {i}}

con restricciones y [1] .

\sum _{i=1}^{n}w_{i}x_{i}\leq W

x_{i}\in\{0,1\}

Variantes del problema de la mochila

El planteamiento del problema permite un gran número de generalizaciones, según las condiciones impuestas a la mochila, los objetos o su elección. Las variedades más populares son las siguientes:

Mochila 0-1 ( ing. 0-1 Problema de mochila ) [2] : no más de una copia de cada artículo.
Problema de mochila acotado [3] : no más de un número dado de instancias de cada elemento.
Problema de mochila ilimitado [3] : un número arbitrario de instancias de cada elemento.
Problema de mochila de opción múltiple [ 4] : los elementos se dividen en grupos, y solo se debe seleccionar un elemento de cada grupo.
Problema de mochila múltiple [5] : Hay varias mochilas, cada una con su propio peso máximo. Cada artículo se puede poner en cualquier mochila o dejar.
Problema de mochila multidimensional : en lugar de peso, se dan varios recursos diferentes (por ejemplo, peso, volumen y tiempo de apilamiento). Cada elemento gasta una cantidad determinada de cada recurso. Es necesario elegir un subconjunto de artículos para que el costo total de cada recurso no exceda el máximo para este recurso, y al mismo tiempo el valor total de los artículos sea máximo [4] .
Problema cuadrático de la mochila : el valor total viene dado por una forma cuadrática definida no negativa [6] .

Problema de mochila no lineal

Una de las variantes más generales del problema de la mochila es la no lineal . Se puede formular de la siguiente manera:

Deje que el vector determine el número de instancias de cada artículo en la mochila. Entonces el problema es encontrar el mínimo de la función ${\displaystyle x=(x_{1},..,x_{n})\en \mathbb {R} ^{n))$

${\ estilo de visualización \ min _ {x \ en S} \ f (x)}$ ,

con una restricción dada:

${\ Displaystyle g (x) \ leq b}$ .

Se supone que las funciones son continuas y derivables en . es una constante entera , el conjunto no está vacío [7] . $f(x),g(x):\mathbb {R} ^{n}\rightarrow \mathbb {R}$ $\mathbb{R} ^{n}$ ${\ estilo de visualización b}$ ${\ estilo de visualización S}$

En el caso de funciones lineales , el problema se reduce a una de las formulaciones clásicas, dependiendo del conjunto : ${\ estilo de visualización f (x), g (x)}$ ${\ estilo de visualización S}$

${\displaystyle S=\{0,1\}^{n))$ - mochila 0-1
$S=\mathbb {N_{0}} ^{n}$ - mochila ilimitada
$S=\{(x_{1},..,x_{n})\in \mathbb {N_{0}} ^{n}:x_{i}\leq c_{i}\}$ - mochila limitada

La libertad en la elección de funciones permite resolver una clase más amplia de tareas, incluida la organización de las instalaciones de producción. ${\ estilo de visualización f (x), g (x)}$ , la distribución óptima de muestras en una muestra regionalizada , o la solución del problema cuadrático de la mochila [7] .

Métodos exactos de solución

Como se mencionó anteriormente, el problema de la mochila pertenece a la clase de NP-completo , y hasta el momento no se ha encontrado ningún algoritmo polinomial que lo resuelva en un tiempo razonable. Por tanto, a la hora de resolver el problema de la mochila, es necesario elegir entre algoritmos exactos, que no son aplicables a mochilas "grandes", y aproximados, que funcionan rápidamente, pero no garantizan la solución óptima del problema.

Enumeración completa

Al igual que con otros problemas discretos, el problema de la mochila se puede resolver enumerando exhaustivamente todas las soluciones posibles.

De acuerdo con la condición del problema, hay artículos que se pueden poner en una mochila y debe determinar el costo máximo de la carga, cuyo peso no exceda . $norte$ $W$

Para cada artículo, hay 2 opciones: el artículo se coloca en la mochila o el artículo no se coloca en la mochila. Luego, la enumeración de todas las opciones posibles tiene complejidad temporal , lo que permite que se use solo para una pequeña cantidad de elementos [8] . Con un aumento en el número de objetos, el problema se vuelve irresoluble por este método en un tiempo aceptable. ${\ estilo de visualización O (2 ^ {N})}$

La figura muestra un árbol de iteraciones para tres elementos. Cada hoja corresponde a algún subconjunto de elementos. Después de compilar el árbol, es necesario encontrar una hoja con el valor máximo entre aquellas cuyo peso no exceda [9] . $W$

Método de rama y límite

El método de ramificación y límite es una variación del método de fuerza bruta con la diferencia de que, a sabiendas, se excluyen las ramas no óptimas del árbol de fuerza bruta. Al igual que el método de fuerza bruta, te permite encontrar la solución óptima y, por lo tanto, pertenece a los algoritmos exactos.

El algoritmo original, propuesto por Peter Kolesar en 1967, propone ordenar los artículos por su costo unitario (la relación entre el valor y el peso) y construir un árbol de fuerza bruta . Su mejora radica en que en el proceso de construcción de un árbol para cada nodo se estima una cota superior sobre el valor de la solución, y la construcción del árbol continúa sólo para el nodo con la estimación máxima [10] . Cuando el límite superior máximo está en una hoja del árbol, el algoritmo termina su trabajo.

La capacidad de ramificar y enlazar para reducir el número de iteraciones depende en gran medida de los datos de entrada. Es recomendable usarlo solo si los valores específicos de los artículos difieren significativamente [11] .

Métodos de programación dinámica

El problema de la mochila ilimitada

Con una restricción adicional sobre los pesos de los artículos, el problema de la mochila se puede resolver en tiempo pseudopolinomio utilizando métodos de programación dinámica .

Sea el peso de cada artículo un número entero positivo. Entonces, para resolver el problema, es necesario calcular las soluciones óptimas para todos , donde es la capacidad de carga dada. Definamos como el valor máximo de artículos que se pueden colocar en una mochila con una capacidad de carga de . $Wisconsin}$ $w\in \mathbb {Z} :0\leq w\leq W$ $W$ ${\ estilo de visualización m [w]}$ $w$

Porque puedes escribir fórmulas recursivas : ${\ estilo de visualización m [w]}$

${\ estilo de visualización m [0] = 0}$
$m[w]=\max _{w_{i}\leq w}(v_{i}+m[w-w_{i}])$ [12] ,

donde son el valor y el peso del elemento -th, respectivamente, y el máximo del conjunto vacío debe considerarse igual a cero. $v_{i},w_{i}$ $i$

De hecho, la última ecuación es la ecuación funcional de R. Bellman o la ecuación funcional de programación dinámica. En este caso, para resolverlo basta con calcular todos los valores de , desde y hasta [12] . Si además almacenamos en cada paso un conjunto de elementos que alcanza el valor máximo, entonces el algoritmo también proporcionará el conjunto óptimo de elementos. ${\ estilo de visualización m [w]}$ ${\ estilo de visualización 0}$ $W$

Dado que en cada paso es necesario encontrar el máximo de elementos, el algoritmo tiene una complejidad computacional de . Debido a que puede depender exponencialmente del tamaño de la entrada, el algoritmo es pseudopolinomio . Por lo tanto, la eficiencia de este algoritmo está determinada por el valor de . El algoritmo da excelentes resultados para , pero no muy buenos para [13] . $norte$ ${\ estilo de visualización O (nW)}$ $W$ $W$ ${\ estilo de visualización W \ leq 1000}$ $W\geq 10\000\000$

Problema de mochila 0-1

La solución del problema de la mochila 0-1 se acerca a la solución del problema anterior, pero hay que tener en cuenta que cada artículo está en una sola copia. Sea el valor máximo de artículos obtenidos de los primeros disponibles, con un peso total no superior a . ${\ estilo de visualización m [i, w]}$ $i$ $w$

Relaciones recurrentes :

${\ estilo de visualización m [0, w] = 0}$
$m[i,\,w]=m[i-1,\,w]$ , si ${\ estilo de visualización w_ {i}> w}$
$m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})$ , si $w_{i}\leq w$

Calculando , puedes encontrar la solución exacta. Si la matriz cabe en la memoria de la máquina, entonces este algoritmo es probablemente uno de los más eficientes [12] . ${\ estilo de visualización m [n, W]}$ ${\ estilo de visualización m [i, w]}$

// Aporte: // Valores de los elementos (cargados en la matriz v) // Pesos de los elementos (cargados en la matriz w) // Número de elementos (n) // Capacidad de carga (W) para j de 0 a W hacer : metro [ 0 , j ] := 0 para i de 1 a n hacer : para j de 0 a W hacer : si w [ i ] > j entonces : metro [ yo , j ] := metro [ yo -1 , j ] más : metro [ yo , j ] := max ( metro [ yo -1 , j ], metro [ yo -1 , j - w [ yo ]] + v [ yo ])

La solución se puede ilustrar mediante programación dinámica de la siguiente manera: en un plano bidimensional, el número de objetos se representa a lo largo del eje y su peso se representa a lo largo del eje. En el primer paso, se construyen dos líneas a partir del origen de coordenadas: una horizontal, correspondiente al hecho de que no se tomó el primer objeto, y una inclinada, correspondiente al primer objeto tomado. Sus proyecciones sobre el eje son iguales al peso del objeto. En el segundo paso, se vuelven a construir 2 líneas, horizontales (no se tomó el segundo objeto) u oblicuas (se tomó el segundo objeto). Pongamos la longitud de los arcos horizontales a cero, y la longitud de los arcos oblicuos al valor del objeto [14] . Así, cualquier solución al problema corresponde a algún camino en el árbol construido . El problema se reduce a encontrar un camino de máxima longitud [14] . Vamos a la capacidad de la mochila . $X$ $Y$ $Y$ ${\ estilo de visualización W = 14}$

Número de artículo	Valor	El peso
una	3	5
2	5	diez
3	cuatro	6
cuatro	2	5

Se puede ver en la figura que el valor total para la solución óptima es 7, ya que este es el valor máximo en el árbol construido.

Programación dinámica sobre valores de artículos

Las relaciones de recurrencia se pueden escribir no solo con respecto al peso de los objetos, sino también con respecto al valor. Para ello, denotamos el peso mínimo de los artículos por el valor total , que se puede obtener de los primeros artículos. Si no se puede obtener el peso requerido, márquelo como . ${\ estilo de visualización y [i, V]}$ $V$ $i$ ${\ estilo de visualización y [i, V] = W + 1}$

Después de eso, resolvemos la ecuación de programación dinámica funcional :

$y[i,V]={\begin{cases}y[i-1,V],&{\text{if }}V<v_{i}\\\min\{\ y[i- 1,V],y[i-1,V-v_{i}]+w_{i}\},&{\text{si}}V\geq v_{i}\end{casos}}$ ,

con condiciones iniciales :

${\ estilo de visualización y [0,0] = 0}$

${\ estilo de visualización y [0, V] = W + 1}$ [quince]

Métodos aproximados de solución

Como ocurre con la mayoría de los problemas NP-completos, no siempre es necesario obtener una solución exacta, ya que en los problemas aplicados se pueden aplicar soluciones cercanas al óptimo.

Algoritmo codicioso

Para resolver el problema con un algoritmo codicioso , es necesario ordenar las cosas por su valor específico (es decir, la relación entre el valor de un artículo y su peso) y colocar los artículos con el valor específico más alto en la mochila [10] .

El tiempo de ejecución de este algoritmo es la suma del tiempo de clasificación y el tiempo de apilamiento. La complejidad de clasificar elementos es . A continuación, calcula cuántos artículos caben en la mochila en el tiempo total [10] . La complejidad resultante cuando se necesita ordenar y cuando los datos ya están ordenados [10] . ${\ estilo de visualización O (N \ registro (N))}$ ${\ estilo de visualización O (N)}$ ${\ estilo de visualización O (N \ registro (N))}$ ${\ estilo de visualización O (N)}$

ejemplo _ Vamos a la capacidad de la mochila . Los artículos ya están ordenados por valor unitario. Usemos el algoritmo codicioso. ${\ estilo de visualización W = 80}$

i	el peso	precio	precio/peso
una	quince	60	cuatro
2	treinta	90	3
3	cincuenta	100	2

Ponemos el primer artículo en la mochila, y después el segundo. El tercer artículo no cabe en la mochila. El valor total de los artículos en la mochila es 150. Si se tomaran el segundo y el tercer artículo, el valor total sería 190. Por lo tanto, hemos obtenido una solución no óptima.

Debe entenderse que un algoritmo codicioso puede conducir a una respuesta arbitrariamente alejada de la óptima. Por ejemplo, si un artículo tiene un peso de 1 y un costo de 2, y el otro tiene un peso de W y un costo de W, entonces el algoritmo codicioso obtendrá un costo total de 2 con una respuesta óptima de W. En al mismo tiempo, el mismo algoritmo para el problema de la mochila sin límites conducirá a una respuesta de al menos el 50% del valor del óptimo [10] .

El algoritmo voraz fue propuesto por primera vez por George Danzig [16] para resolver el problema de la mochila ilimitada.

Esquema aproximado para tiempo completamente polinomial

Dado que no se encontró el algoritmo exacto para resolver el problema en tiempo polinomial , se planteó el problema de obtener una solución polinomial con precisión garantizada . Para ello, existen una serie de esquemas aproximados de tiempo totalmente polinomial , es decir, con complejidad que es un polinomio en y . $1-\varepsilon$ $norte$ ${\frac{1}{\varepsilon}}$

La idea detrás del esquema clásico es reducir la precisión con la que se dan los valores de los elementos. Al combinar elementos de valor similar en un grupo, puede reducir la cantidad de elementos diferentes. El algoritmo se escribe de la siguiente manera [15] :

Encontremos una solución aproximada usando un algoritmo codicioso. Sea la solución exacta. Luego, a partir de la estimación de la eficiencia del algoritmo codicioso . ${\ estilo de visualización x ^ {l}}$ $x^{*}$ ${\displaystyle x^{l}\leq x^{*}\leq 2x^{l))$
Escala los valores de la siguiente manera: . $v'_{i}=\left\lpiso {\frac {v_{i}}{\frac {x^{l}\varepsilon }{n}}}\right\rpiso$
Usando el algoritmo de programación dinámica para un problema con valores enteros de objetos, encontramos una solución.

Hay muchos esquemas de aproximación diferentes. Sin embargo, dependen fuertemente de la formulación del problema de la mochila. Por ejemplo, si en la condición aparece una segunda restricción del tipo desigualdad (mochila bidimensional), entonces el problema ya no tiene un esquema de tiempo polinomial conocido [17] .

Algoritmos genéticos

Al igual que con otros problemas de optimización NP-hard, se utilizan algoritmos genéticos para resolver el problema de la mochila . No garantizan encontrar la solución óptima en tiempo polinomial y no dan una estimación de la proximidad de la solución a la óptima, pero tienen buenos indicadores de tiempo, lo que le permite encontrar una solución bastante buena más rápido que otros deterministas o heurísticos conocidos. métodos. [Dieciocho]

Cada individuo ( genotipo ) es un subconjunto de los artículos que queremos empacar en la mochila (su peso total puede exceder la capacidad de carga permitida). Para mayor comodidad, la información se almacena como cadenas binarias, en las que cada bit determina si este artículo cabe en una cartera [19] .

La función de aptitud determina la proximidad de la solución a la óptima. Por ejemplo, el valor total de los artículos puede servir como tal, siempre que el peso total no exceda la capacidad de carga.

Tras una serie de cambios generacionales en los que se cruzan los individuos más aptos y se ignora al resto, se supone que el algoritmo mejora las soluciones originales [19] .

Resolviendo el problema de la suma de subconjuntos

Un caso especial del problema de la mochila 0-1 es el problema de la suma de subconjuntos . Sea la capacidad de carga de la mochila, el peso del -ésimo artículo y su costo . Por lo tanto, la tarea es cargar la mochila lo más apretada posible o agotar completamente los recursos: $W$ $Wisconsin}$ $i$ $v_{i}=w_{i}$

$W=\sum _{i=1}^{N}w_{i}x_{i},\qquad \ x_{i}\in \{0,1\}$

Para solucionarlo, puedes utilizar el citado algoritmo genético . Un individuo es un vector . Como función de fitness, se debe usar la proximidad del peso total de los objetos a , con la única característica de que los conjuntos que caben en una mochila son más preferibles (el peso total de los objetos es menor que ) [19] . ${\ estilo de visualización (x_{1},..,x_{n})}$ $W$ $W$

Definamos formalmente la función de aptitud . Sea la suma de los pesos de todos los elementos. Entonces , la desviación máxima posible del peso de los artículos en la mochila de . $f(x_{1},..,x_{n}):\{0,1\}^{n}\rightarrow \mathbb {R}$ $\mathcal{S}$ ${\textstyle \Delta _{max}=max(W,{\mathcal {S}}-W)}$ $W$

Sea el peso total de elementos para el vector dado. Luego ponemos: ${\textstyle W'=\sum_{i=1}^{N}w_{i}x_{i}}$

$f(x_{1},..,x_{n})={\begin{casos}1-{\sqrt {\frac {WW'}{W))},&W'\leq W,\ \1-{\sqrt {\frac {W'-W}{\Delta _{max)))),&W'>W.\end{casos))$ [19]

Usando el algoritmo general, podemos encontrar una solución aproximada:

Cree un conjunto aleatorio de individuos: una población.
Calcular la función de adaptación para cada individuo.
Dejar solo a los individuos más aptos (selección natural).
Realiza cruces.
descendencia mutada.
Continúe desde el segundo paso.

La ejecución se interrumpe cuando se encuentra una solución o después de un número determinado de iteraciones [19] .

Aplicaciones

No se sabe con certeza quién fue el primero en dar la formulación matemática del problema de la mochila. Una de las primeras referencias a ella se encuentra en un artículo de George Ballard Matthews[20] [21] con fecha de 1897. El estudio intensivo de este problema comenzó después de la publicación por D. B. Dantzig en 1957 del libro “ English. Problema extremo de variable discreta » [22] , especialmente en los años 70-90 del siglo XX, tanto por teóricos como por practicantes [2] . En muchos sentidos, el interés fue causado por una formulación bastante simple del problema, una gran cantidad de sus variedades y propiedades y, al mismo tiempo, la complejidad de su solución. En 1972, este problema se incluyó en la lista de problemas NP-completos de M. Karp ( artículo en inglés "Reducibility Among Combinatorial Problems" ) [23] .

Una interpretación visual del problema de la mochila ha llevado a que haya encontrado aplicación en varios campos del conocimiento: en las matemáticas, la informática y, en la intersección de estas ciencias, en la criptografía . En uno de los trabajos sobre lingüística computacional [24] , se propone la formulación del problema del resumen automático de textos , un caso especial del cual corresponde a la formulación del problema de la mochila.

Basado en el problema de la mochila, se creó el primer algoritmo de cifrado asimétrico . La idea de la criptografía de clave pública fue presentada por primera vez por Whitfield Diffie y Martin Hellman en la Conferencia Nacional de Computación de 1976 [25] [26] .

Además, el problema de la mochila puede servir como modelo para una gran cantidad de problemas industriales [2] [27] :

Colocación de mercancías en un almacén con una superficie mínima.
Corte de tela : de una pieza de material existente, obtenga la cantidad máxima de patrones de una determinada forma.
Cálculo de inversiones óptimas de capital .

El problema de la mochila en criptografía

En 1978, Ralph Merkle y Martin Hellman desarrollaron el primer algoritmo para el cifrado de clave pública generalizada , el criptosistema Merkle-Hellman , basado en el problema de la mochila. Publicaron versiones de una sola etapa ( inglés con una sola iteración ) y de varias etapas ( inglés con varias iteraciones ), y el algoritmo solo podía usarse para el cifrado. Pero Adi Shamir lo adaptó para su uso en firmas digitales [28] .

Posteriormente se propusieron otros criptosistemas basados en el problema de la mochila, algunos de los cuales son una modificación del criptosistema Merkle-Hellman. Criptosistemas conocidos [29] :

La mochila de Graham - Shamira
Mochila Goodman - Macauley
Mochila Nakkasha - Popa
Mochila de Shor - Rivesta

Cifrado con el problema de la mochila

Debido a que el problema general de la mochila no se puede resolver exactamente en un tiempo razonable, se puede utilizar en problemas criptográficos . Para ello, con un conjunto de elementos de conocimiento público, representaremos el mensaje como un conjunto de elementos transmitidos y enviaremos su peso total [28] .

Definición. Un vector mochila es un conjunto ordenado de n elementos, donde es el peso del -ésimo elemento [30] . $A=(a_{1},...,a_{n})$ $ai$ $i$

El vector mochila es una clave pública . Para cifrar el texto sin formato, se divide en bloques de bits, y cada bit determina la presencia de un elemento en la mochila (por ejemplo, el texto sin formato corresponde a la presencia de los primeros cuatro de los seis elementos posibles en la mochila). Se cree que uno indica la presencia de un artículo en la mochila y cero indica su ausencia [28] . $norte$ ${\ estilo de visualización (111100)}$

Después de eso, el peso total de los artículos en la mochila para el texto sin formato dado se calcula y se transmite como texto cifrado [28] .

Un ejemplo de cifrado con este algoritmo:

Sea dado un vector mochila de longitud . ${\ estilo de visualización A = (3\ 4\ 6\ 7\ 10\ 11)}$ $n=6$

Texto sin formato	1 1 1 1 1 0	0 0 1 1 0 0	0 0 0 0 0 0	0 0 0 0 0 1
cosas en la mochila	3 4 6 7 10	6 7		once
Texto cifrado	3 + 4 + 6 + 7 + 10 = 30	6 + 7 = 13	0	once

Notas

↑ Silvano, 1990 , pág. una.
↑ 1 2 3 Silvano, 1990 , p. 2.
↑ 1 2 Kellerer, Pferschy, Pisinger, 2004 , p. 127.
↑ 1 2 Kellerer, Pferschy, Pisinger, 2004 , p. 147.
↑ Silvano, 1990 , pág. 157.
↑ G. Gallo, P. L. Hammer, B. Simeone. Problemas de mochila cuadráticos // Estudios de programación matemática. - 2009. - 24 de febrero ( vol. 12 ). - pág. 132-149 . — ISSN 0303-3929 . Archivado desde el original el 24 de octubre de 2016.
↑ 1 2 Brettauer, Shetty, 2002 .
↑ Okulov, 2007 , págs. 92-93.
↑ Okulov, 2007 , págs. 101-105.
↑ 1 2 3 4 5 Martello S., Toth P. Problemas de mochila: algoritmos e implementaciones informáticas . - John Wiley & Sons Ltd., 1990. - S. 29,50 . — 296 págs. — ISBN 0-471-92420-2 .
↑ Burkov, Gorgidze, Lovetsky, 1974 , p. 225.
↑ 1 2 3 Romanovsky I.V. Algoritmos para la resolución de problemas extremos . - Nauka, 1977. - S. 252 -259. — 352 págs.
↑ Stephen S. Skiena. Algoritmos. Guía de desarrollo. - 2do. - San Petersburgo. : BHV-Petersburg, 2011. - S. 448-451. — 720 s. - ISBN 978-5-9775-0560-4 .
↑ 1 2 Novikov, 2001 , pág. 12
↑ 1 2 Kellerer, Pferschy, Pisinger, 2004 .
↑ Dantzig G. B. Problemas extremos de variables discretas // Oper . Res. - Instituto de Investigación Operativa y Ciencias de la Gestión , 1957. - Vol. 5, edición. 2.- Pág. 266-288. - 23 horas — ISSN 0030-364X ; 1526-5463 - doi:10.1287/OPRE.5.2.266
↑ Ariel Kulik, Hadas Shachnai. No hay EPTAS para cartas bidimensionales de procesamiento de información // de mochila. — 2010-07-31. - T. 110 , n. 16 _ — S. 707–710 . -doi : 10.1016/ j.ipl.2010.05.031 .
↑ D. I. Batishchev, E.A. Neimark, Nevada Starostin. Aplicación de Algoritmos Genéticos a la Solución de Problemas de Optimización Discreta . - 2007. - Nizhni Nóvgorod. Archivado el 22 de febrero de 2016 en Wayback Machine .
↑ 1 2 3 4 5 S. M. Avdoshin, A. A. Savelyeva. Criptoanálisis: estado actual y perspectivas de desarrollo . - art. 38 . Archivado desde el original el 17 de marzo de 2016. (Ruso)
↑ GB Mathews. Sobre la partición de números (inglés) . - 1897. - P. 486-490.
↑ Kellerer, Pferschy, Pisinger, 2004 , pág. 3.
↑ Kellerer, Pferschy, Pisinger, 2004 , pág. 9.
↑ R. Karp. Reducibilidad entre problemas combinatorios . — 1972.
↑ Riedhammer et al, 2008 , págs. 2436.
↑ Schnaer, 2002 , pág. 19.2.
↑ Gabidulin, Kshevetsky, Kolybelnikov, 2011 .
↑ Burkov, Gorgidze, Lovetsky, 1974 , p. 217.
↑ 1 2 3 4 Schnaer, 2002 , pág. 19.1.
↑ Kin Ming Lai. Criptosistemas de mochila: el pasado y el futuro . — 2001. (Ruso)
↑ Salomaa, 1995 , pág. 103.

Literatura

en ruso

Algoritmos de Levitin A. V. Introducción al desarrollo y análisis - M .: Williams , 2006. - S. 160-163. — 576 pág. — ISBN 978-5-8459-0987-9
Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmos: construcción y análisis = Introducción a los Algoritmos. - 2do. - M. : "Williams" , 2006. - S. 456-458. — ISBN 0-07-013151-1 .
Roberto Sedwick . Algoritmos fundamentales en C++. Partes 1-4. Análisis. Estructuras de datos. Clasificación. Buscar = Algoritmos en C++. Partes 1-4. fundamentos estructuras de datos. Clasificación. Buscando. - 3ro. - Rusia, San Petersburgo: "DiaSoft" , 2002. - S. 688. - ISBN 5-93772-047-4 , 0-201-35088-2.
Burkov V. N. , Gorgidze I. A. , Lovetsky S. E. Problemas aplicados de teoría de grafos / ed. A. Ya. Gorgidze - Tbilisi : Centro de Computación de la Academia de Ciencias de la URSS , 1974. - 231 p.
V. N. Burkov, D. A. Novikov. Elementos de Teoría de Grafos . - 2001. - S. 28.
S.Okulov. Programación en Algoritmos . - 1er. — Binom. Laboratorio del Conocimiento, 2007. - Pág. 384. - ISBN 5-94774-010-9 .
B. Schneier. Criptografía aplicada. Protocolos, algoritmos, código fuente en lenguaje C = Criptografía Aplicada. Protocolos, Algoritmos y Código Fuente en C. - 2º. - Triunfo, 2002. - 816 p. - 3000 copias. - ISBN 5-89392-055-4 . Archivado el 18 de diciembre de 2018 en Wayback Machine .
A. Salomaa. Criptografía de clave pública = Criptografía de clave pública. - M. : Mir, 1995. - S. 102-150. - ISBN 5-03-001991-X. Archivado el 4 de marzo de 2016 en Wayback Machine .
N. Koblitz. Curso de teoría de números en criptografía. - 2do. - M. : TVP Scientific Publishing House, 2001. - S. 254. - ISBN 5-85484-014-6 .
Gabidulin E. M. , Kshevetsky A. S. , Kolybelnikov A. I. Seguridad de la información : libro de texto - M .: MIPT , 2011. - 225 p. — ISBN 978-5-7417-0377-9
Osipyan V. O. Sobre el sistema de seguridad de la información basado en el problema de la mochila // Boletín de la Universidad Politécnica de Tomsk [Boletín TPU]. - 2006. - T. 309 , N º 2 . - S. 209-212 .

en inglés

Silvano Martelo, Paolo Toth. Problemas con la mochila . - Gran Bretaña: Wiley, 1990. - 306 p. — ISBN 0-471-92420-2 .
Kellerer H. , Pferschy U. , Pisinger D. Problemas de mochila (inglés) - Springer Science + Business Media , 2004. - 548 p. - ISBN 978-3-642-07311-3 - doi:10.1007/978-3-540-24777-7
K. Riedhammer, D. Gillick, B. Favre y D. Hakkani-Tür. Empacando la mochila de resumen de la reunión . — Brisbane Australia: Proc. Interspeech, Brisbane, Australia, 2008.
Brettauer K. M. , Shetty B. El problema de la mochila no lineal: algoritmos y aplicaciones (inglés) // European Journal of Operational Research - Elsevier BV , 2002. - vol. 138, edición. 3.- Págs. 459-472. — ISSN 0377-2217 ; 1872-6860 - doi:10.1016/S0377-2217(01)00179-5

Enlaces

Bienvenido a la mochila
El problema de la mochila Por Eric Grimsom John Guttag - MIT
Soluciones de problemas de mochila en muchos idiomas.
Das Rucksack-Problem (Problema de la mochila) (alemán)

El problema de la mochila
Aplicaciones	Problema de la mochila en criptografía Tarea de corte
Criptosistemas basados en el problema de la mochila	Merkla-Hellman Naccasha - popa Graham - Shamira
Además	Lista de tareas sobre la mochila

Problemas NP-completos
Problema de maximización del apilamiento (packing)	Envasado en contenedores embalaje bidimensional embalaje lineal embalaje por peso embalaje por valor El problema de la mochila
teoría de grafos teoría de conjuntos	Problema de cobertura de vértices Haga clic en problema El problema de un conjunto independiente (conjunto) Establecer problema de cobertura Problema de Steiner El problema del viajante de comercio Problema generalizado del viajante de comercio
Problemas algorítmicos	Problema de satisfacibilidad para fórmulas booleanas (en forma normal conjuntiva)
Juegos de lógica y rompecabezas.	Etiquetas generalizadas (juego en N 2 -1) problema de solución más corta Problemas cuyas soluciones se aplican en Tetris Problema de sudoku generalizado Problema de llenado de cuadrados latinos La tarea de Kakuro
Clases de dificultad La investigación de operaciones Mejoramiento optimización combinatoria Matemáticas Aplicadas Teoría de Algoritmos Programación dinámica 21 Problema de Karp NP-completo