Problema de la mochila

Problema en optimización combinatoria

Ejemplo de un problema de mochila unidimensional (con restricciones): ¿qué libros se deben elegir para maximizar la cantidad de dinero y, al mismo tiempo, mantener el peso total por debajo o igual a 15 kg? Un problema con restricciones múltiples podría considerar tanto el peso como el volumen de los libros.
(Solución: si hay cualquier cantidad de cada libro disponible, entonces tres libros amarillos y tres libros grises; si solo están disponibles los libros que se muestran, entonces todos excepto el libro verde).

El problema de la mochila es el siguiente problema de optimización combinatoria :

Dado un conjunto de elementos, cada uno con un peso y un valor, determine qué elementos incluir en la colección para que el peso total sea menor o igual a un límite dado y el valor total sea lo más grande posible.

Su nombre deriva del problema al que se enfrenta alguien que está limitado por una mochila de tamaño fijo y debe llenarla con los artículos más valiosos. El problema suele surgir en la asignación de recursos , donde los encargados de la toma de decisiones tienen que elegir entre un conjunto de proyectos o tareas no divisibles con un presupuesto fijo o una limitación de tiempo, respectivamente.

El problema de la mochila se ha estudiado durante más de un siglo y los primeros trabajos se remontan a 1897. ^[1]

Aplicaciones

Los problemas de mochila aparecen en los procesos de toma de decisiones del mundo real en una amplia variedad de campos, como encontrar la forma menos derrochadora de cortar materias primas, ^[2] la selección de inversiones y carteras , ^[3] la selección de activos para la titulización respaldada por activos , ^[4] y la generación de claves para Merkle–Hellman ^[5] y otros criptosistemas de mochila .

Una de las primeras aplicaciones de los algoritmos de mochila fue la construcción y calificación de exámenes en los que los examinados tienen la opción de elegir qué preguntas responder. Para ejemplos pequeños, es un proceso bastante simple proporcionar a los examinados esa opción. Por ejemplo, si un examen contiene 12 preguntas, cada una con un valor de 10 puntos, el examinado solo necesita responder 10 preguntas para lograr una puntuación máxima posible de 100 puntos. Sin embargo, en exámenes con una distribución heterogénea de valores de puntos, es más difícil proporcionar opciones. Feuerman y Weiss propusieron un sistema en el que se les da a los estudiantes un examen heterogéneo con un total de 125 puntos posibles. Se les pide a los estudiantes que respondan todas las preguntas lo mejor que puedan. De los posibles subconjuntos de problemas cuyos valores de puntos totales suman 100, un algoritmo de mochila determinaría qué subconjunto le da a cada estudiante la puntuación más alta posible. ^[6]

Un estudio de 1999 del Repositorio de Algoritmos de la Universidad Stony Brook mostró que, de 75 problemas algorítmicos relacionados con el campo de los algoritmos combinatorios y la ingeniería de algoritmos, el problema de la mochila fue el 19º más popular y el tercero más necesario después de los árboles de sufijos y el problema de empaquetamiento de contenedores . ^[7]

Definición

El problema más común que se resuelve es el problema de la mochila 0-1 , que restringe el número de copias de cada tipo de artículo a cero o uno. Dado un conjunto de artículos numerados del 1 al , cada uno con un peso y un valor , junto con una capacidad máxima de peso , ${\displaystyle x_{i}}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle w_{i}}$ ${\displaystyle v_{i}}$ ${\displaystyle W}$

maximizar ${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

sujeto a y . ${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$ ${\displaystyle x_{i}\in \{0,1\}}$

Aquí se representa el número de instancias del elemento que se incluirá en la mochila. De manera informal, el problema consiste en maximizar la suma de los valores de los elementos de la mochila de modo que la suma de los pesos sea menor o igual a la capacidad de la mochila. ${\displaystyle x_{i}}$ ${\displaystyle i}$

El problema de la mochila acotada ( BKP ) elimina la restricción de que solo existe uno de cada elemento, pero restringe el número de copias de cada tipo de elemento a un valor entero máximo no negativo : ${\displaystyle x_{i}}$ ${\displaystyle c}$

maximizar ${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

sujeto a y ${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$ ${\displaystyle x_{i}\in \{0,1,2,\dots ,c\}.}$

El problema de la mochila ilimitada ( UKP ) no impone un límite superior al número de copias de cada tipo de artículo y se puede formular como se indicó anteriormente, excepto que la única restricción es que sea un número entero no negativo. ${\displaystyle x_{i}}$

maximizar ${\displaystyle \sum _{i=1}^{n}v_{i}x_{i}}$

sujeto a y ${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq W}$ ${\displaystyle x_{i}\in \mathbb {Z} ,\ x_{i}\geq 0.}$

Un ejemplo del problema de la mochila ilimitada se da utilizando la figura que se muestra al comienzo de este artículo y el texto "si hay alguna cantidad disponible de cada libro" en el título de esa figura.

Complejidad computacional

El problema de la mochila es interesante desde la perspectiva de la informática por muchas razones:

• La forma del problema de decisión del problema de la mochila ( ¿Se puede lograr un valor de al menos V sin exceder el peso W ? ) es NP-completo , por lo tanto, no se conoce ningún algoritmo que sea correcto y rápido (tiempo polinomial) en todos los casos.
• No se conoce ningún algoritmo polinómico que pueda determinar, dada una solución, si es óptima (lo que significaría que no existe ninguna solución con un valor V mayor ). Este problema es co-NP-completo .
• Existe un algoritmo de tiempo pseudopolinomial que utiliza programación dinámica .
• Existe un esquema de aproximación de tiempo completamente polinomial , que utiliza el algoritmo de tiempo pseudopolinomial como subrutina, que se describe a continuación.
• Muchos casos que surgen en la práctica y "instancias aleatorias" de algunas distribuciones pueden, no obstante, resolverse con exactitud.

Existe un vínculo entre los problemas de "decisión" y de "optimización" en el sentido de que si existe un algoritmo polinomial que resuelve el problema de "decisión", entonces se puede encontrar el valor máximo para el problema de optimización en tiempo polinomial aplicando este algoritmo de manera iterativa mientras se aumenta el valor de k. Por otro lado, si un algoritmo encuentra el valor óptimo del problema de optimización en tiempo polinomial, entonces el problema de decisión se puede resolver en tiempo polinomial comparando el valor de la solución obtenida por este algoritmo con el valor de k. Por lo tanto, ambas versiones del problema tienen una dificultad similar.

Un tema en la literatura de investigación es identificar cómo se ven las instancias "duras" del problema de la mochila, ^{[8] [9]} o visto de otra manera, identificar qué propiedades de las instancias en la práctica podrían hacerlas más manejables de lo que sugiere su comportamiento NP-completo en el peor de los casos. ^[10] El objetivo de encontrar estas instancias "duras" es su uso en sistemas de criptografía de clave pública , como el criptosistema de mochila de Merkle-Hellman . De manera más general, una mejor comprensión de la estructura del espacio de instancias de un problema de optimización ayuda a avanzar en el estudio del problema en particular y puede mejorar la selección de algoritmos.

Además, es notable el hecho de que la dificultad del problema de la mochila depende de la forma de la entrada. Si los pesos y las ganancias se dan como números enteros, es débilmente NP-completo , mientras que es fuertemente NP-completo si los pesos y las ganancias se dan como números racionales. ^[11] Sin embargo, en el caso de pesos y ganancias racionales, todavía admite un esquema de aproximación de tiempo completamente polinomial .

Modelos de costos unitarios

La NP-dureza del problema de la mochila se relaciona con modelos computacionales en los que el tamaño de los números enteros importa (como la máquina de Turing ). Por el contrario, los árboles de decisión cuentan cada decisión como un solo paso. Dobkin y Lipton ^[12] muestran un límite inferior en los árboles de decisión lineales para el problema de la mochila, es decir, árboles donde los nodos de decisión prueban el signo de las funciones afines . ^[13] Esto fue generalizado a los árboles de decisión algebraicos por Steele y Yao. ^[14] Si los elementos del problema son números reales o racionales , el límite inferior del árbol de decisión se extiende al modelo de máquina de acceso aleatorio real con un conjunto de instrucciones que incluye suma, resta y multiplicación de números reales, así como comparación y división o resto ("piso"). ^[15] Este modelo cubre más algoritmos que el modelo de árbol de decisión algebraico, ya que abarca algoritmos que utilizan indexación en tablas. Sin embargo, en este modelo se cuentan todos los pasos del programa, no solo las decisiones. Meyer auf der Heide ^[16] proporcionó un límite superior para un modelo de árbol de decisión y demostró que para cada n existe un árbol de decisión lineal de profundidad O ( n ⁴ ) que resuelve el problema de suma de subconjuntos con n elementos. Obsérvese que esto no implica ningún límite superior para un algoritmo que debería resolver el problema para cualquier n dado . ${\displaystyle {1 \over 2}n^{2}}$

Resolviendo

Existen varios algoritmos disponibles para resolver problemas de mochila, basados ​​en el enfoque de programación dinámica, ^[17] el enfoque de ramificación y acotación ^[18] o hibridaciones de ambos enfoques. ^{[10] [19] [20] [21]}

Algoritmo de programación dinámica avanzada

El problema de la mochila ilimitada ( UKP ) no impone ninguna restricción en cuanto al número de copias de cada tipo de artículo. Además, aquí suponemos que ${\displaystyle x_{i}>0}$

${\displaystyle m[w']=\max \left(\sum _{i=1}^{n}v_{i}x_{i}\right)}$

sujeto a y ${\displaystyle \sum _{i=1}^{n}w_{i}x_{i}\leq w'}$ ${\displaystyle x_{i}>0}$

Observe que tiene las siguientes propiedades: ${\displaystyle m[w]}$

1. (la suma de cero elementos, es decir, la suma del conjunto vacío). ${\displaystyle m[0]=0\,\!}$

2. , , donde es el valor del -ésimo tipo de elemento. ${\displaystyle m[w]=\max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n}])}$ ${\displaystyle w_{i}\leq w}$ ${\displaystyle v_{i}}$ ${\displaystyle i}$

La segunda propiedad debe explicarse en detalle. Durante el proceso de ejecución de este método, ¿cómo obtenemos el peso ? Solo hay formas y los pesos anteriores son donde hay un total de tipos de elementos diferentes (al decir diferentes, queremos decir que el peso y el valor no son completamente iguales). Si conocemos cada valor de estos elementos y el valor máximo relacionado previamente, simplemente los comparamos entre sí y obtenemos el valor máximo en última instancia y listo. ${\displaystyle w}$ ${\displaystyle i}$ ${\displaystyle w-w_{1},w-w_{2},...,w-w_{i}}$ ${\displaystyle i}$ ${\displaystyle i}$

Aquí se toma como cero el máximo del conjunto vacío. Tabulando los resultados de arriba a abajo se obtiene la solución. Dado que el cálculo de cada uno implica examinar como máximo elementos y hay como máximo valores de para calcular, el tiempo de ejecución de la solución de programación dinámica es . Dividir por su máximo común divisor es una forma de mejorar el tiempo de ejecución. ${\displaystyle m[0]}$ ${\displaystyle m[W]}$ ${\displaystyle m[w]}$ ${\displaystyle n}$ ${\displaystyle W}$ ${\displaystyle m[w]}$ ${\displaystyle O(nW)}$ ${\displaystyle w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W}$

Incluso si P≠NP , la complejidad no contradice el hecho de que el problema de la mochila es NP-completo , ya que , a diferencia de , no es polinomial en la longitud de la entrada al problema. La longitud de la entrada al problema es proporcional al número de bits en , , no a sí misma. Sin embargo, dado que este tiempo de ejecución es pseudopolinomial , esto hace que el (versión de decisión del) problema de la mochila sea un problema débilmente NP-completo . ${\displaystyle O(nW)}$ ${\displaystyle W}$ ${\displaystyle n}$ ${\displaystyle W}$ ${\displaystyle W}$ ${\displaystyle \log W}$ ${\displaystyle W}$

Problema de la mochila 0-1

Una demostración del enfoque de programación dinámica.

Una solución de programación dinámica similar para el problema de la mochila 0-1 también se ejecuta en tiempo pseudopolinomial. Supongamos que son números enteros estrictamente positivos. Definamos que es el valor máximo que se puede alcanzar con un peso menor o igual a utilizando elementos hasta (primeros elementos). ${\displaystyle w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W}$ ${\displaystyle m[i,w]}$ ${\displaystyle w}$ ${\displaystyle i}$ ${\displaystyle i}$

Podemos definir recursivamente de la siguiente manera: (Definición A) ${\displaystyle m[i,w]}$

• ${\displaystyle m[0,\,w]=0}$
• ${\displaystyle m[i,\,w]=m[i-1,\,w]}$si (el nuevo artículo supera el límite de peso actual) ${\displaystyle w_{i}>w\,\!}$
• ${\displaystyle m[i,\,w]=\max(m[i-1,\,w],\,m[i-1,w-w_{i}]+v_{i})}$si . ${\displaystyle w_{i}\leqslant w}$

La solución se puede encontrar calculando . Para hacerlo de manera eficiente, podemos usar una tabla para almacenar los cálculos anteriores. ${\displaystyle m[n,W]}$

El siguiente es el pseudocódigo para el programa dinámico:

// Aporte:// Valores (almacenados en la matriz v)// Pesos (almacenados en la matriz w)// Número de elementos distintos (n)// Capacidad de la mochila (W)// NOTA: Se supone que la matriz "v" y la matriz "w" almacenan todos los valores relevantes a partir del índice 1.matriz m [ 0. . n , 0. . W ];  Para j de 0 a W hacemos :       m [ 0 , j ] := 0   para i de 1 a n hacer :       m [ yo , 0 ] := 0   para i de 1 a n hacer :       Para j de 1 a W hacemos :       Si w [ i ] > j entonces :     m [ i , j ] := m [ i -1 , j ]     demás : m [ i , j ] := máx ( m [ i -1 , j ], m [ i -1 , j - w [ i ]] + v [ i ])        

Por lo tanto, esta solución se ejecutará en el tiempo y el espacio. (Si solo necesitamos el valor m[n,W], podemos modificar el código para que la cantidad de memoria requerida sea O(W), que almacena las dos líneas recientes de la matriz "m"). ${\displaystyle O(nW)}$ ${\displaystyle O(nW)}$

Sin embargo, si lo llevamos un paso o dos más allá, deberíamos saber que el método se ejecutará en el tiempo entre y . A partir de la Definición A , sabemos que no es necesario calcular todos los pesos cuando la cantidad de elementos y los elementos mismos que elegimos son fijos. Es decir, el programa anterior calcula más de lo necesario porque el peso cambia de 0 a W con frecuencia. Desde esta perspectiva, podemos programar este método para que se ejecute de forma recursiva. ${\displaystyle O(nW)}$ ${\displaystyle O(2^{n})}$

// Aporte:// Valores (almacenados en la matriz v)// Pesos (almacenados en la matriz w)// Número de elementos distintos (n)// Capacidad de la mochila (W)// NOTA: Se supone que la matriz "v" y la matriz "w" almacenan todos los valores relevantes a partir del índice 1.Definir valor [ n , W ]  Inicializar todos los valores [ i , j ] = -1     Define m := ( i , j ) // Define la función m para que represente el valor máximo que podemos obtener bajo la condición: usar los primeros i artículos, el límite de peso total es j  { Si i == 0 o j <= 0 entonces :         valor [ i , j ] = 0    devolver si ( valor [ i -1 , j ] == -1 ) entonces : // m[i-1, j] no se ha calculado, tenemos que llamar a la función m       m ( i -1 , j )  si w [ i ] > j entonces : // el artículo no cabe en la bolsa      valor [ i , j ] = valor [ i -1 , j ]     demás :  si ( valor [ i -1 , j - w [ i ]] == -1 ) entonces : // m[i-1,jw[i]] no se ha calculado, tenemos que llamar a la función m       m ( i -1 , j - w [ i ])  valor [ i , j ] = máx ( valor [ i -1 , j ], valor [ i -1 , j - w [ i ]] + v [ i ])       }Ejecutar m ( n , W )  

Por ejemplo, hay 10 elementos diferentes y el límite de peso es 67. Entonces, si usa el método anterior para calcular , obtendrá esto, excluyendo las llamadas que producen : $${\displaystyle {\begin{aligned}&w[1]=23,w[2]=26,w[3]=20,w[4]=18,w[5]=32,w[6]=27,w[7]=29,w[8]=26,w[9]=30,w[10]=27\\&v[1]=505,v[2]=352,v[3]=458,v[4]=220,v[5]=354,v[6]=414,v[7]=498,v[8]=545,v[9]=473,v[10]=543\\\end{aligned}}}$$ ${\displaystyle m(10,67)}$ ${\displaystyle m(i,j)=0}$ $${\displaystyle {\begin{aligned}&m(10,67)=1270\\&m(9,67)=1270,m(9,40)=678\\&m(8,67)=1270,m(8,40)=678,m(8,37)=545\\&m(7,67)=1183,m(7,41)=725,m(7,40)=678,m(7,37)=505\\&m(6,67)=1183,m(6,41)=725,m(6,40)=678,m(6,38)=678,m(6,37)=505\\&m(5,67)=1183,m(5,41)=725,m(5,40)=678,m(5,38)=678,m(5,37)=505\\&m(4,67)=1183,m(4,41)=725,m(4,40)=678,m(4,38)=678,m(4,37)=505,m(4,35)=505\\&m(3,67)=963,m(3,49)=963,m(3,41)=505,m(3,40)=505,m(3,38)=505,m(3,37)=505,m(3,35)=505,m(3,23)=505,m(3,22)=458,m(3,20)=458\\&m(2,67)=857,m(2,49)=857,m(2,47)=505,m(2,41)=505,m(2,40)=505,m(2,38)=505,m(2,37)=505,m(2,35)=505,m(2,29)=505,m(2,23)=505\\&m(1,67)=505,m(1,49)=505,m(1,47)=505,m(1,41)=505,m(1,40)=505,m(1,38)=505,m(1,37)=505,m(1,35)=505,m(1,29)=505,m(1,23)=505\\\end{aligned}}}$$

Además, podemos romper la recursión y convertirla en un árbol. Luego podemos cortar algunas hojas y utilizar computación paralela para acelerar la ejecución de este método.

Para encontrar el subconjunto real de elementos, en lugar de solo su valor total, podemos ejecutar esto después de ejecutar la función anterior:

/*** Devuelve los índices de los artículos de la mochila óptima.* i: Podemos incluir los artículos 1 a i en la mochila.* j: peso máximo de la mochila*/función mochila ( i : int , j : int ) : Establecer < int > {       Si i == 0 entonces :     devolver {}  si m [ i , j ] > m [ i -1 , j ] entonces :       devuelve { i } ∪ mochila ( i -1 , j - w [ i ])     demás : volver mochila ( i -1 , j )  }mochila ( n , W ) 

Encuentro en el medio

Otro algoritmo para la mochila 0-1, descubierto en 1974 ^[22] y a veces llamado "encuentro en el medio" debido a los paralelismos con un algoritmo de nombre similar en criptografía , es exponencial en el número de elementos diferentes, pero puede ser preferible al algoritmo DP cuando es grande en comparación con n . En particular, si son no negativos pero no enteros, aún podríamos usar el algoritmo de programación dinámica mediante escalado y redondeo (es decir, usando aritmética de punto fijo ), pero si el problema requiere dígitos fraccionarios de precisión para llegar a la respuesta correcta, necesitará ser escalado por , y el algoritmo DP requerirá espacio y tiempo. ${\displaystyle W}$ ${\displaystyle w_{i}}$ ${\displaystyle d}$ ${\displaystyle W}$ ${\displaystyle 10^{d}}$ ${\displaystyle O(W10^{d})}$ ${\displaystyle O(nW10^{d})}$

El algoritmo Meet-in-the-middle es  entrada: un conjunto de elementos con pesos y valores. salida: el mayor valor combinado de un subconjunto. Dividir el conjunto {1... n } en dos conjuntos A y B de tamaño aproximadamente igual. Calcular los pesos y valores de todos los subconjuntos de cada conjunto. Para cada subconjunto de  A,  encuentre el subconjunto de B de mayor valor tal que el peso combinado sea menor que W. Realizar un seguimiento del mayor valor combinado visto hasta ahora

El algoritmo ocupa espacio, y las implementaciones eficientes del paso 3 (por ejemplo, ordenar los subconjuntos de B por peso, descartar subconjuntos de B que pesen más que otros subconjuntos de B de valor mayor o igual, y usar la búsqueda binaria para encontrar la mejor coincidencia) dan como resultado un tiempo de ejecución de . Al igual que con el ataque de encuentro en el medio en criptografía, esto mejora el tiempo de ejecución de un enfoque de fuerza bruta ingenuo (examinar todos los subconjuntos de ), a costa de usar espacio exponencial en lugar de constante (ver también paso de bebé paso de gigante ). La mejora actual del estado del arte del algoritmo de encuentro en el medio, que utiliza conocimientos del Algoritmo para la suma de subconjuntos de Schroeppel y Shamir, proporciona como corolario un algoritmo aleatorio para Knapsack que preserva el tiempo de ejecución (hasta factores polinómicos) y reduce los requisitos de espacio a (ver ^[23] Corolario 1.4). En contraste, el algoritmo determinista más conocido se ejecuta en el tiempo con una complejidad espacial ligeramente peor de . ^[24] ${\displaystyle O(2^{n/2})}$ ${\displaystyle O(n2^{n/2})}$ ${\displaystyle O(n2^{n})}$ ${\displaystyle \{1...n\}}$ ${\displaystyle O^{*}(2^{n/2})}$ ${\displaystyle O^{*}(2^{0.249999n})}$ ${\displaystyle O^{*}(2^{n/2})}$ ${\displaystyle O^{*}(2^{n/4})}$

Algoritmos de aproximación

Como en la mayoría de los problemas NP-completos, puede ser suficiente encontrar soluciones viables incluso si no son óptimas. Sin embargo, es preferible que la aproximación venga con una garantía de la diferencia entre el valor de la solución encontrada y el valor de la solución óptima.

Al igual que ocurre con muchos algoritmos útiles pero computacionalmente complejos, se han llevado a cabo importantes investigaciones sobre la creación y el análisis de algoritmos que se aproximan a una solución. El problema de la mochila, aunque es NP-Hard, forma parte de una colección de algoritmos que aún pueden aproximarse a cualquier grado especificado. Esto significa que el problema tiene un esquema de aproximación de tiempo polinomial. Para ser exactos, el problema de la mochila tiene un esquema de aproximación de tiempo completamente polinomial (FPTAS). ^[25]

Algoritmo de aproximación codiciosa

George Dantzig propuso un algoritmo de aproximación voraz para resolver el problema de la mochila ilimitada. ^[26] Su versión ordena los artículos en orden decreciente de valor por unidad de peso, . Luego procede a insertarlos en la bolsa, comenzando con tantas copias como sea posible del primer tipo de artículo hasta que ya no haya espacio en la bolsa para más. Siempre que haya un suministro ilimitado de cada tipo de artículo, si es el valor máximo de los artículos que caben en la bolsa, entonces se garantiza que el algoritmo voraz logrará al menos un valor de . ${\displaystyle v_{1}/w_{1}\geq \cdots \geq v_{n}/w_{n}}$ ${\displaystyle m}$ ${\displaystyle m/2}$

Para el problema acotado, donde la oferta de cada tipo de artículo es limitada, el algoritmo anterior puede estar lejos de ser óptimo. Sin embargo, una modificación simple nos permite resolver este caso: supongamos para simplificar que todos los artículos caben individualmente en el saco ( para todos ). Construya una solución empaquetando artículos con avidez el mayor tiempo posible, es decir, donde . Además, construya una segunda solución que contenga el primer artículo que no cabía. Dado que proporciona un límite superior para la relajación LP del problema, uno de los conjuntos debe tener un valor de al menos ; por lo tanto, devolvemos el que de y tenga mejor valor para obtener una aproximación. ${\displaystyle w_{i}\leq W}$ ${\displaystyle i}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{1}=\left\{1,\ldots ,k\right\}}$ ${\displaystyle k=\textstyle \max _{1\leq k'\leq n}\textstyle \sum _{i=1}^{k'}w_{i}\leq W}$ ${\displaystyle S_{2}=\left\{k+1\right\}}$ ${\displaystyle S_{1}\cup S_{2}}$ ${\displaystyle m/2}$ ${\displaystyle S_{1}}$ ${\displaystyle S_{2}}$ ${\displaystyle 1/2}$

Se puede demostrar que el rendimiento promedio converge a la solución óptima en la distribución en la tasa de error ^[27] ${\displaystyle n^{-1/2}}$

Esquema de aproximación temporal completamente polinomial

El esquema de aproximación de tiempo completamente polinomial (FPTAS) para el problema de la mochila aprovecha el hecho de que la razón por la que el problema no tiene soluciones de tiempo polinomial conocidas es porque las ganancias asociadas con los artículos no están restringidas. Si uno redondea algunos de los dígitos menos significativos de los valores de las ganancias, entonces estarán limitados por un polinomio y 1/ε donde ε es un límite en la exactitud de la solución. Esta restricción significa entonces que un algoritmo puede encontrar una solución en tiempo polinomial que sea correcta dentro de un factor de (1-ε) de la solución óptima. ^[25]

Se ingresa  el algoritmo FPTAS : ε ∈ (0,1] una lista A de n elementos, especificados por sus valores, y pesos salida: S' la solución FPTAS ${\displaystyle v_{i}}$ P := max // el valor del artículo más alto ${\displaystyle \{v_{i}\mid 1\leq i\leq n\}}$ K := ε ${\displaystyle {\frac {P}{n}}}$ para i de 1 a n hacer  := fin para ${\displaystyle v'_{i}}$ ${\displaystyle \left\lfloor {\frac {v_{i}}{K}}\right\rfloor }$  Devuelve la solución, S', utilizando los valores del programa dinámico descrito anteriormente. ${\displaystyle v'_{i}}$

Teorema: El conjunto calculado por el algoritmo anterior satisface , donde es una solución óptima. ${\displaystyle S'}$ ${\displaystyle \mathrm {profit} (S')\geq (1-\varepsilon )\cdot \mathrm {profit} (S^{*})}$ ${\displaystyle S^{*}}$

Optimización aproximada cuántica

El algoritmo de optimización aproximada cuántica (QAOA) se puede emplear para resolver el problema de Knapsack mediante computación cuántica al minimizar el hamiltoniano del problema. El hamiltoniano de Knapsack se construye incorporando la condición de restricción a la función de costo del problema con un término de penalización. ^[28] donde es la constante de penalización que se determina mediante un ajuste fino específico del caso. $${\displaystyle {H}=-\sum _{i=1}^{n}v_{i}x_{i}+P\left(\sum _{i=1}^{n}w_{i}x_{i}-W\right)^{2},}$$ ${\displaystyle P}$

Relaciones de dominancia

La solución del problema de la mochila ilimitada se puede hacer más fácil si se desechan los elementos que nunca se necesitarán. Para un elemento dado , supongamos que pudiéramos encontrar un conjunto de elementos tales que su peso total sea menor que el peso de , y su valor total sea mayor que el valor de . Entonces no puede aparecer en la solución óptima, porque siempre podríamos mejorar cualquier solución potencial que contenga reemplazando con el conjunto . Por lo tanto, podemos descartar el elemento -ésimo por completo. En tales casos, se dice que domina . (Tenga en cuenta que esto no se aplica a los problemas de mochilas acotadas, ya que es posible que ya hayamos usado los elementos en ). ${\displaystyle i}$ ${\displaystyle J}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle J}$ ${\displaystyle i}$ ${\displaystyle J}$ ${\displaystyle i}$ ${\displaystyle J}$

Encontrar relaciones de dominancia nos permite reducir significativamente el tamaño del espacio de búsqueda. Existen varios tipos diferentes de relaciones de dominancia, ^[10] y todas satisfacen una desigualdad de la forma:

${\displaystyle \qquad \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}}$, y para algunos ${\displaystyle \sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,}$ ${\displaystyle x\in Z_{+}^{n}}$

donde y . El vector denota el número de copias de cada miembro de . ${\displaystyle \alpha \in Z_{+}\,,J\subsetneq N}$ ${\displaystyle i\not \in J}$ ${\displaystyle x}$ ${\displaystyle J}$

Dominio colectivo

El elemento -ésimo está dominado colectivamente por , escrito como , si el peso total de alguna combinación de elementos en es menor que w _i y su valor total es mayor que v _i . Formalmente, y para algunos , es decir . Verificar este predominio es computacionalmente difícil, por lo que solo se puede utilizar con un enfoque de programación dinámica. De hecho, esto es equivalente a resolver un problema de decisión de mochila más pequeño donde , , y los elementos están restringidos a . ${\displaystyle i}$ ${\displaystyle J}$ ${\displaystyle i\ll J}$ ${\displaystyle J}$ ${\displaystyle \sum _{j\in J}w_{j}\,x_{j}\ \leq w_{i}}$ ${\displaystyle \sum _{j\in J}v_{j}\,x_{j}\ \geq v_{i}}$ ${\displaystyle x\in Z_{+}^{n}}$ ${\displaystyle \alpha =1}$ ${\displaystyle V=v_{i}}$ ${\displaystyle W=w_{i}}$ ${\displaystyle J}$

Dominio del umbral

El elemento -ésimo está dominado por umbral , escrito como , si cierta cantidad de copias de están dominadas por . Formalmente, , y para algunas y . Esta es una generalización de la dominancia colectiva, introducida por primera vez en ^[17] y utilizada en el algoritmo EDUK. El tal más pequeño define el umbral del elemento , escrito . En este caso, la solución óptima podría contener como máximo copias de . ${\displaystyle i}$ ${\displaystyle J}$ ${\displaystyle i\prec \prec J}$ ${\displaystyle i}$ ${\displaystyle J}$ ${\displaystyle \sum _{j\in J}w_{j}\,x_{j}\ \leq \alpha \,w_{i}}$ ${\displaystyle \sum _{j\in J}v_{j}\,x_{j}\ \geq \alpha \,v_{i}\,}$ ${\displaystyle x\in Z_{+}^{n}}$ ${\displaystyle \alpha \geq 1}$ ${\displaystyle \alpha }$ ${\displaystyle i}$ ${\displaystyle t_{i}=(\alpha -1)w_{i}}$ ${\displaystyle \alpha -1}$ ${\displaystyle i}$

Dominio múltiple

El elemento -ésimo está dominado de forma múltiple por un solo elemento , escrito como , si está dominado por cierta cantidad de copias de . Formalmente, , y para algunos ie . Esta dominancia podría usarse de manera eficiente durante el preprocesamiento porque puede detectarse con relativa facilidad. ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle i\ll _{m}j}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle w_{j}\,x_{j}\ \leq w_{i}}$ ${\displaystyle v_{j}\,x_{j}\ \geq v_{i}}$ ${\displaystyle x_{j}\in Z_{+}}$ ${\displaystyle J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor }$

Dominio modular

Sea el mejor elemento , es decir, para todos . Este es el elemento con la mayor densidad de valor. El elemento -ésimo está dominado modularmente por un solo elemento , escrito como , si está dominado por más varias copias de . Formalmente, , y es decir . ${\displaystyle b}$ ${\displaystyle {\frac {v_{b}}{w_{b}}}\geq {\frac {v_{i}}{w_{i}}}\,}$ ${\displaystyle i}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle i\ll _{\equiv }j}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle b}$ ${\displaystyle w_{j}+tw_{b}\leq w_{i}}$ ${\displaystyle v_{j}+tv_{b}\geq v_{i}}$ ${\displaystyle J=\{b,j\},\alpha =1,x_{b}=t,x_{j}=1}$

Variaciones

Existen muchas variantes del problema de la mochila que han surgido a partir de la gran cantidad de aplicaciones del problema básico. Las principales variaciones se producen al cambiar el número de algún parámetro del problema, como el número de elementos, el número de objetivos o incluso el número de mochilas.

Problema de la mochila multiobjetivo

Esta variación cambia el objetivo del individuo que llena la mochila. En lugar de un objetivo, como maximizar la ganancia monetaria, el objetivo podría tener varias dimensiones. Por ejemplo, podría haber preocupaciones ambientales o sociales, así como objetivos económicos. Los problemas que se abordan con frecuencia incluyen optimizaciones de la logística de transporte y de la cartera. ^{[29] [30]}

Por ejemplo, supongamos que gestionas un crucero. Tienes que decidir cuántos comediantes famosos vas a contratar. Este barco no puede transportar más de una tonelada de pasajeros y los artistas deben pesar menos de 1000 libras. Cada comediante tiene un peso, genera clientes en función de su popularidad y pide un salario específico. En este ejemplo, tienes varios objetivos. Por supuesto, quieres maximizar la popularidad de tus artistas y minimizar sus salarios. Además, quieres tener tantos artistas como sea posible.

Problema de la mochila multidimensional

En esta variación, el peso del elemento de la mochila está dado por un vector de dimensión D y la mochila tiene un vector de capacidad de dimensión D. El objetivo es maximizar la suma de los valores de los elementos de la mochila de modo que la suma de los pesos en cada dimensión no exceda . ${\displaystyle i}$ ${\displaystyle {\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})}$ ${\displaystyle (W_{1},\ldots ,W_{D})}$ ${\displaystyle d}$ ${\displaystyle W_{d}}$

La mochila multidimensional es computacionalmente más difícil que la mochila; incluso para , el problema no tiene EPTAS a menos que P NP. ^[31] Sin embargo, se muestra que el algoritmo en ^[32] resuelve instancias dispersas de manera eficiente. Una instancia de mochila multidimensional es dispersa si hay un conjunto para tal que para cada elemento de mochila , tal que y . Tales instancias ocurren, por ejemplo, al programar paquetes en una red inalámbrica con nodos de retransmisión. ^[32] El algoritmo de ^[32] también resuelve instancias dispersas de la variante de opción múltiple, mochila multidimensional de opción múltiple. ${\displaystyle D=2}$ ${\displaystyle =}$ ${\displaystyle J=\{1,2,\ldots ,m\}}$ ${\displaystyle m<D}$ ${\displaystyle i}$ ${\displaystyle \exists z>m}$ ${\displaystyle \forall j\in J\cup \{z\},\ w_{ij}\geq 0}$ ${\displaystyle \forall y\notin J\cup \{z\},w_{iy}=0}$

El algoritmo IHS (Increasing Height Shelf) es óptimo para una mochila 2D (empaquetado de cuadrados en un cuadrado de tamaño unitario bidimensional): cuando hay como máximo cinco cuadrados en un empaquetamiento óptimo. ^[33]

Problema de múltiples mochilas

Esta variación es similar al problema de empaquetado de contenedores . Se diferencia de este último en que se puede seleccionar un subconjunto de elementos, mientras que en este último se deben empaquetar todos los elementos en contenedores determinados. El concepto es que hay varias mochilas. Esto puede parecer un cambio trivial, pero no es equivalente a aumentar la capacidad de la mochila inicial. Esta variación se utiliza en muchos problemas de carga y programación en la investigación de operaciones y tiene un esquema de aproximación de tiempo polinomial . ^[34]

Problema de la mochila cuadrática

El problema de la mochila cuadrática maximiza una función objetivo cuadrática sujeta a restricciones de capacidad binaria y lineal. ^[35] El problema fue introducido por Gallo, Hammer y Simeone en 1980, ^[36] sin embargo el primer tratamiento del problema se remonta a Witzgall en 1975. ^[37]

Problema de suma de subconjuntos

El problema de la suma de subconjuntos es un caso especial de los problemas de decisión y 0-1 donde cada tipo de elemento, el peso es igual al valor: . En el campo de la criptografía , el término problema de la mochila se utiliza a menudo para referirse específicamente al problema de la suma de subconjuntos. El problema de la suma de subconjuntos es uno de los 21 problemas NP-completos de Karp . ^[38] ${\displaystyle w_{i}=v_{i}}$

Una generalización del problema de suma de subconjuntos se denomina problema de suma de subconjuntos múltiples, en el que existen múltiples contenedores con la misma capacidad. Se ha demostrado que la generalización no tiene un FPTAS . ^[39]

Problema geométrico de la mochila

En el problema geométrico de la mochila, hay un conjunto de rectángulos con diferentes valores y una mochila rectangular. El objetivo es meter el mayor valor posible en la mochila. ^[40]

Véase también

• Portal de programación informática

• Problema de empaquetamiento de contenedores  : problema matemático y computacional
• Problema de cambio  : elegir la menor cantidad de monedas para generar una cantidad determinada de dinero
• Subasta combinatoria  : mercado inteligente en el que los participantes pueden realizar ofertas sobre combinaciones de artículos discretos, en lugar de artículos individuales o cantidades continuas.Pages displaying wikidata descriptions as a fallback
• Optimización combinatoria  : subcampo de la optimización matemática
• Problema continuo de la mochila
• Problema de corte de stock  : problema matemático en la investigación de operaciones
• Subasta de mochilas
• Lista de problemas de la mochila
• Problema de embalaje  : problemas que intentan encontrar la forma más eficiente de embalar objetos en contenedores.Pages displaying short descriptions of redirect targets

Notas

1. Mathews, GB (25 de junio de 1897). "Sobre la partición de números" (PDF) . Actas de la London Mathematical Society . 28 : 486–490. doi :10.1112/plms/s1-28.1.486.
2. Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Problemas con la mochila. Berlín: Springer. pag. 449.ISBN​ 978-3-540-40286-2. Recuperado el 5 de mayo de 2022 .
3. Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Problemas con la mochila. Berlín: Springer. pag. 461.ISBN​ 978-3-540-40286-2. Recuperado el 5 de mayo de 2022 .
4. Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Problemas con la mochila. Berlín: Springer. pag. 465.ISBN​ 978-3-540-40286-2. Recuperado el 5 de mayo de 2022 .
5. Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Problemas con la mochila. Berlín: Springer. pag. 472.ISBN​ 978-3-540-40286-2. Recuperado el 5 de mayo de 2022 .
6. Feuerman, Martin; Weiss, Harvey (abril de 1973). "Un modelo de programación matemática para la construcción y calificación de pruebas". Management Science . 19 (8): 961–966. doi :10.1287/mnsc.19.8.961. JSTOR  2629127.
7. Skiena, SS (septiembre de 1999). "¿Quién está interesado en los algoritmos y por qué? Lecciones del repositorio de algoritmos de Stony Brook". ACM SIGACT News . 30 (3): 65–74. CiteSeerX 10.1.1.41.8357 . doi :10.1145/333623.333627. ISSN  0163-5700. S2CID  15619060. 
8. Pisinger, D. 2003. ¿Dónde están los problemas de las mochilas rígidas? Informe técnico 2003/08, Departamento de Ciencias de la Computación, Universidad de Copenhague, Copenhague, Dinamarca.
9. Caccetta, L.; Kulanoot, A. (2001). "Aspectos computacionales de problemas de mochilas rígidas". Análisis no lineal . 47 (8): 5547–5558. doi :10.1016/s0362-546x(01)00658-7.
10. Poirriez, Vincent; Yanev, Nicola; Andonov, Rumen (2009). "Un algoritmo híbrido para el problema de la mochila sin límites". Optimización discreta . 6 (1): 110–124. doi : 10.1016/j.disopt.2008.09.004 . ISSN  1572-5286. S2CID  8820628.
11. Wojtczak, Dominik (2018). "Sobre la NP-completitud fuerte de los problemas racionales". Ciencias de la computación: teoría y aplicaciones . Apuntes de clase en ciencias de la computación. Vol. 10846. págs. 308–320. arXiv : 1802.09465 . doi :10.1007/978-3-319-90530-3_26. ISBN 978-3-319-90529-7. Número de identificación del sujeto  3637366.
12. Dobkin, David; Lipton, Richard J. (1978). "Un límite inferior de ½n2 en programas de búsqueda lineal para el problema de la mochila". Revista de Ciencias de la Computación y de Sistemas . 16 (3): 413–417. doi :10.1016/0022-0000(78)90026-0.
13. De hecho, el límite inferior se aplica al problema de suma de subconjuntos, que es un caso especial de Knapsack.
14. Michael Steele, J; Yao, Andrew C (1 de marzo de 1982). "Límites inferiores para árboles de decisión algebraicos". Journal of Algorithms . 3 (1): 1–8. doi :10.1016/0196-6774(82)90002-5. ISSN  0196-6774.
15. Ben-Amram, Amir M.; Galil, Zvi (2001), "Límites inferiores topológicos en máquinas de acceso aleatorio algebraico", SIAM Journal on Computing , 31 (3): 722–761, doi :10.1137/S0097539797329397.
16. der Heide, Meyer (1984), "Un algoritmo de búsqueda lineal polinomial para el problema de la mochila de n dimensiones", Journal of the ACM , 31 (3): 668–676, doi :10.1145/828.322450
17. Andonov, Rumen; Poirriez, Vincent; Rajopadhye, Sanjay (2000). "Problema de la mochila sin límites: revisión de la programación dinámica". Revista Europea de Investigación Operativa . 123 (2): 168–181. CiteSeerX 10.1.1.41.2135 . doi :10.1016/S0377-2217(99)00265-9. 
18. S. Martello, P. Toth, Problemas de mochila: algoritmos e implementaciones informáticas, John Wiley and Sons, 1990
19. S. Martello, D. Pisinger, P. Toth, Programación dinámica y límites fuertes para el problema de la mochila 0-1, Manag. Sci. , 45:414–424, 1999.
20. Plateau, G.; Elkihel, M. (1985). "Un algoritmo híbrido para el problema de la mochila 0-1". Métodos de Oper. Res . 49 : 277–293.
21. Martello, S.; Toth, P. (1984). "Una mezcla de programación dinámica y ramificación y acotación para el problema de suma de subconjuntos". Manag. Sci . 30 (6): 765–771. doi :10.1287/mnsc.30.6.765.
22. Horowitz, Ellis; Sahni, Sartaj (1974), "Computación de particiones con aplicaciones al problema de la mochila", Journal of the Association for Computing Machinery , 21 (2): 277–292, doi :10.1145/321812.321823, hdl : 1813/5989 , MR  0354006, S2CID  16866858
23. Nederlof, Jesper; Węgrzycki, Karol (12 de abril de 2021). "Mejora del algoritmo de Schroeppel y Shamir para la suma de subconjuntos mediante vectores ortogonales". arXiv : 2010.08576 [cs.DS].
24. Schroeppel, Richard; Shamir, Adi (agosto de 1981). "Un algoritmo $T = O(2^{n/2} )$, $S = O(2^{n/4} )$ para ciertos problemas NP-completos". Revista SIAM de Computación . 10 (3): 456–464. doi :10.1137/0210033. ISSN  0097-5397.
25. Vazirani, Vijay. Algoritmos de aproximación. Springer-Verlag Berlín Heidelberg, 2003.
26. Dantzig, George B. (1957). "Problemas de extremos con variables discretas". Investigación de operaciones . 5 (2): 266–288. doi :10.1287/opre.5.2.266.
27. Calvin, James M.; Leung, Joseph Y. -T. (1 de mayo de 2003). "Análisis de caso promedio de un algoritmo voraz para el problema de la mochila 0/1". Operations Research Letters . 31 (3): 202–210. doi :10.1016/S0167-6377(02)00222-5.
28. Lucas, Andrew (2014). "Formulaciones de Ising de muchos problemas NP". Frontiers in Physics . 2 : 5. arXiv : 1302.5843 . Bibcode :2014FrP.....2....5L. doi : 10.3389/fphy.2014.00005 . ISSN  2296-424X.
29. Chang, TJ, et al. Heurísticas para la optimización de carteras con restricciones de cardinalidad. Informe técnico, Londres SW7 2AZ, Inglaterra: The Management School, Imperial College, mayo de 1998
30. Chang, CS, et al. "Optimización de bicriterio basada en algoritmo genético para subestaciones de tracción en sistemas ferroviarios de CC". En Fogel [102], 11-16.
31. Kulik, A.; Shachnai, H. (2010). "No hay EPTAS para la mochila bidimensional" (PDF) . Inf. Proceso. Lett . 110 (16): 707–712. CiteSeerX 10.1.1.161.5838 . doi :10.1016/j.ipl.2010.05.031. 
32. Cohen, R. y Grebla, G. 2014. "Programación OFDMA multidimensional en una red inalámbrica con nodos de retransmisión". en Proc. IEEE INFOCOM'14 , 2427–2435.
33. Yan Lan, György Dósa, Xin Han, Chenyang Zhou, Attila Benkő [1]: Mochila 2D: cuadrados de embalaje , Informática teórica vol. 508, págs. 35–40.
34. Chandra Chekuri y Sanjeev Khanna (2005). "Un PTAS para el problema de múltiples mochilas". Revista SIAM de Computación . 35 (3): 713–728. CiteSeerX 10.1.1.226.3387 . doi :10.1137/s0097539700382820. 
35. Wu, ZY; Yang, YJ; Bai, FS; Mammadov, M. (2011). "Condiciones de optimalidad global y métodos de optimización para problemas de mochila cuadráticos". J Optim Theory Appl . 151 (2): 241–259. doi :10.1007/s10957-011-9885-4. S2CID  31208118.
36. Gallo, G.; Hammer, PL; Simeone, B. (1980). "Problemas de mochila cuadráticos". Optimización combinatoria . Estudios de programación matemática. Vol. 12. págs. 132–149. doi :10.1007/BFb0120892. ISBN. 978-3-642-00801-6.
37. Witzgall, C. (1975). "Métodos matemáticos de selección de sitios para sistemas de mensajes electrónicos (EMS)". Informe técnico N.º 76 de la NASA Sti/Recon . Informe interno del NBS: 18321. Código Bibliográfico :1975STIN...7618321W.
38. Richard M. Karp (1972). "Reducibilidad entre problemas combinatorios". En RE Miller y JW Thatcher (editores). Complejidad de los cálculos informáticos. Nueva York: Plenum. págs. 85-103.
39. Caprara, Alberto; Kellerer, Hans; Pferschy, Ulrich (2000). "El problema de la suma de subconjuntos múltiples". SIAM J. Optim . 11 (2): 308–319. CiteSeerX 10.1.1.21.9826 . doi :10.1137/S1052623498348481. 
40. Galvez, Waldo; Grandoni, Fabrizio; Ingala, Salvatore; Heydrich, Sandy; Khan, Arindam; Wiese, Andreas (2021). "Aproximación de la mochila geométrica mediante empaquetamientos en L". ACM Trans. Algoritmos . 17 (4): 33:1–33:67. arXiv : 1711.07710 . doi :10.1145/3473713.

Referencias

• Garey, Michael R .; David S. Johnson (1979). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . WH Freeman. ISBN 978-0-7167-1045-5.A6: MP9, pág.247.
• Kellerer, Hans; Pferschy, Ulrich; Pisinger, David (2004). Problemas con la mochila . Saltador. doi :10.1007/978-3-540-24777-7. ISBN 978-3-540-40286-2. Sr.  2161720. S2CID  28836720.
• Martello, Silvano; Toth, Paolo (1990). Problemas de mochila: algoritmos e implementaciones informáticas. Wiley-Interscience. ISBN 978-0-471-92420-3.Señor 1086874  .

Enlaces externos

• Diapositivas de la conferencia sobre el problema de la mochila
• PYAsUKP: Otro solucionador para el problema de la mochila sin límites, con código que aprovecha las relaciones de dominio en un algoritmo híbrido, puntos de referencia y copias descargables de algunos artículos.
• Página de inicio de David Pisinger con copias descargables de algunos artículos de la lista de publicaciones (incluido "¿Dónde están los problemas de las mochilas duras?")
• Soluciones al problema de la mochila en varios idiomas en Rosetta Code
• Algoritmo de programación dinámica para el problema de la mochila 0/1
• Solucionador de problemas de mochilas (en línea)
• Solución de 0-1-KNAPSACK con algoritmos genéticos en Ruby Archivado el 23 de mayo de 2011 en Wayback Machine
• Códigos para el problema de la mochila cuadrática Archivado el 14 de febrero de 2015 en Wayback Machine

• Optimización del embalaje tridimensional de contenedores
• Solución de programación entera de mochila en Python Gekko (software de optimización)