problema de mochila

Problema en optimización combinatoria.

Ejemplo de un problema de mochila unidimensional (restricción): ¿qué libros se deben elegir para maximizar la cantidad de dinero manteniendo 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 disponible cualquier cantidad de cada libro, entonces tres libros amarillos y tres libros grises; si solo están disponibles los libros mostrados, entonces todos excepto el libro verde).

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

Dado un conjunto de artículos, cada uno con un peso y un valor, determine qué artículos 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 que enfrenta alguien que está limitado por una mochila de tamaño fijo y debe llenarla con los artículos más valiosos. El problema surge a menudo en la asignación de recursos , cuando quienes toman las decisiones tienen que elegir entre un conjunto de proyectos o tareas no divisibles bajo un presupuesto fijo o una restricció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] selección de inversiones y carteras , ^[3] selección de activos para la titulización respaldada por activos. , ^[4] y generar claves para Merkle-Hellman ^[5] y otros criptosistemas de mochila .

Una de las primeras aplicaciones de los algoritmos de mochila fue en la construcción y puntuación de pruebas en las que los examinados podían elegir qué preguntas responder. Para ejemplos pequeños, es un proceso bastante simple brindar a los examinados esa opción. Por ejemplo, si un examen contiene 12 preguntas con un valor de 10 puntos cada una, el examinado solo necesita responder 10 preguntas para lograr una puntuación máxima posible de 100 puntos. Sin embargo, en pruebas con una distribución heterogénea de valores de puntos, es más difícil ofrecer opciones. Feuerman y Weiss propusieron un sistema en el que a los estudiantes se les aplica una prueba heterogénea con un total de 125 puntos posibles. Se pide a los estudiantes que respondan todas las preguntas lo mejor que puedan. De los posibles subconjuntos de problemas cuyos valores totales de puntos 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 de 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 era el 19º más popular y el tercero más necesario después de los árboles de sufijos y el problema del embalaje 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í representa el número de instancias de artículo a incluir en la mochila. Informalmente, el problema es maximizar la suma de los valores de los artículos en 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 hay una de cada artículo, pero restringe el número de copias de cada tipo de artículo 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 ningún límite superior al número de copias de cada tipo de artículo y puede formularse 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 principio de este artículo y el texto "si hay algún número de cada libro disponible" 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 mochila ( ¿Se puede lograr un valor de al menos V sin exceder el peso W ? ) es NP-completo , por lo que no se conoce ningún algoritmo que sea correcto y rápido (tiempo polinómico) en todos los casos. .
• No existe ningún algoritmo polinomial conocido que pueda decir, dada una solución, si es óptima (lo que significaría que no hay solución con una 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 totalmente 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 "casos aleatorios" de algunas distribuciones se pueden resolver exactamente.

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 polinómico aplicando este algoritmo de forma iterativa mientras aumentando el valor de k. Por otro lado, si un algoritmo encuentra el valor óptimo del problema de optimización en tiempo polinómico, entonces el problema de decisión se puede resolver en tiempo polinómico comparando el valor de la solución generada por este algoritmo con el valor de k. Por tanto, ambas versiones del problema presentan una dificultad similar.

Un tema en la literatura de investigación es identificar cómo son los casos "difíciles" del problema de la mochila, ^{[8] [9] [10]} o, vistos de otra manera, identificar qué propiedades de los casos en la práctica podrían hacerlos más manejables que sus sugiere el comportamiento NP-completo en el peor de los casos. ^{[11] [12]} El objetivo de encontrar estas instancias "duras" es su uso en sistemas de criptografía de clave pública , como el criptosistema de mochila 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 particular y puede mejorar la selección de algoritmos.

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

Modelos de costo unitario

La dureza NP del problema de 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 ^[14] muestran un límite inferior en los árboles de decisión lineal para el problema de la mochila, es decir, árboles donde los nodos de decisión prueban el signo de funciones afines . ^[15] Steele y Yao generalizaron esto a árboles de decisión algebraicos. ^[16] 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 real de acceso aleatorio con un conjunto de instrucciones que incluye suma, resta y multiplicación de números reales, así como comparación y ya sea división o resto ("piso"). ^[17] 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 sólo las decisiones. Meyer auf der Heide ^[18] dio un límite superior para un modelo de árbol de decisión , quien demostró que para cada n existe un árbol de decisión lineal profundo O ( n ⁴ ) que resuelve el problema de suma de subconjuntos con n elementos. Tenga en cuenta 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

Se encuentran disponibles varios algoritmos para resolver problemas de mochila, basados ​​en el enfoque de programación dinámica, ^[19] el enfoque de rama y enlace ^[20] o hibridaciones de ambos enfoques. ^{[11] [21] [22] [23]}

Algoritmo avanzado de programación dinámica

El problema de la mochila ilimitada ( UKP ) no impone ninguna restricción 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}$

Observa 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 está el valor del -ésimo tipo de artículo. ${\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 necesita ser explicada en detalle. Durante el proceso de ejecución de este método, ¿cómo obtenemos el peso ? Sólo hay formas y en los pesos anteriores es donde hay totales de tipos de artículos 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 finalmente obtenemos el valor máximo y listo. ${\displaystyle w}$ ${\displaystyle i}$ ${\displaystyle w-w_{1},w-w_{2},...,w-w_{i}}$ ${\displaystyle i}$ ${\displaystyle i}$

Aquí el máximo del conjunto vacío se toma como cero. Tabular los resultados desde arriba da la solución. Dado que el cálculo de cada uno implica examinar como máximo los 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 polinomio 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 la (versión de decisión del) problema de mochila sea un problema débilmente NP-completo . ${\displaystyle O(nW)}$ ${\displaystyle W}$ ${\displaystyle n}$ ${\displaystyle W}$ ${\displaystyle W}$ ${\displaystyle \log W}$ ${\displaystyle W}$

0-1 problema de mochila

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. Defina como el valor máximo que se puede alcanzar con un peso menor o igual al uso de artículos hasta (primeros artículos). ${\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}$

Luego se puede encontrar la solución calculando . Para hacer esto de manera eficiente, podemos usar una tabla para almacenar 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 mochila (W)// NOTA: Se supone que la matriz "v" y la matriz "w" almacenan todos los valores relevantes comenzando en el índice 1.matriz m [ 0. . norte , 0. . W ];  para j de 0 a W haga :       metro [ 0 , j ] := 0   para i de 1 a n hacer :       metro [ yo , 0 ] := 0   para i de 1 a n hacer :       para j de 1 a W haga :       si w [ i ] > j entonces :     metro [ yo , j ] := metro [ yo -1 , j ]     demás : m [ i , j ] := máx ( m [ i -1 , j ], m [ i -1 , j - w [ i ]] + v [ i ])        

Por tanto, esta solución funcionará 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 avanzamos uno o dos pasos más, debemos saber que el método se ejecutará en el tiempo comprendido entre y . Por la Definición A , sabemos que no es necesario calcular todos los pesos cuando el número 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 mochila (W)// NOTA: Se supone que la matriz "v" y la matriz "w" almacenan todos los valores relevantes comenzando en el índice 1.Definir valor [ n , W ]  Inicializar todos los valores [ i , j ] = -1     Definir m := ( i , j ) // Definir la función m para que represente el valor máximo que podemos obtener bajo la condición: usar los primeros i elementos, 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 ha sido calculado, tenemos que llamar a la función m       metro ( yo -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 ha sido calculado, tenemos que llamar a la función m       metro ( yo -1 , j - w [ yo ])  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 recursividad y convertirla en un árbol. Luego podemos cortar algunas hojas y usar 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 del 1 al i en la mochila* j: peso máximo de la mochila*/función mochila ( i : int , j : int ) : Establecer <int> {​​       si yo == 0 entonces :     devolver {}  si m [ i , j ] > m [ i -1 , j ] entonces :       return { i } ∪ mochila ( i -1 , j - w [ i ])     demás : mochila de regreso ( i -1 , j )  }mochila ( n , W ) 

Encontrarse en el medio

Otro algoritmo para mochila 0-1, descubierto en 1974 ^[24] y a veces llamado "encuentro en el medio" debido a los paralelos con un algoritmo de nombre similar en criptografía , es exponencial en el número de elementos diferentes, pero puede ser preferible a el algoritmo DP cuando es grande en comparación con n . En particular, si no son negativos pero no son enteros, aún podríamos usar el algoritmo de programación dinámica escalando y redondeando (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, será necesario para 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  la 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 aproximadamente el mismo tamaño 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 realice un seguimiento del mayor valor combinado visto hasta el momento

El algoritmo requiere espacio e implementaciones eficientes del paso 3 (por ejemplo, ordenar los subconjuntos de B por peso, descartar subconjuntos de B que pesan más que otros subconjuntos de B de mayor o igual valor 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 ingenuo de fuerza bruta (examinando 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, utilizando conocimientos del algoritmo de Schroeppel y Shamir para la suma de subconjuntos, proporciona como corolario un algoritmo aleatorio para Knapsack que preserva el tiempo de ejecución (hasta factores polinomiales) y reduce los requisitos de espacio a (ver ^[25] Corolario 1.4). Por el contrario, el algoritmo determinista más conocido se ejecuta en el tiempo con una complejidad espacial ligeramente peor de . ^[26] ${\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 ocurre con la mayoría de los problemas NP completos, puede ser suficiente encontrar soluciones viables incluso si no son óptimas. Preferiblemente, sin embargo, la aproximación viene con una garantía de la diferencia entre el valor de la solución encontrada y el valor de la solución óptima.

Como ocurre con muchos algoritmos útiles pero computacionalmente complejos, se han realizado importantes investigaciones sobre la creación y análisis de algoritmos que se aproximan a una solución. El problema de la mochila, aunque NP-Hard, forma parte de una colección de algoritmos que aún pueden aproximarse a cualquier grado específico. 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 totalmente polinomial (FPTAS). ^[27]

Algoritmo de aproximación codicioso

George Dantzig propuso un algoritmo de aproximación codiciosa para resolver el problema de la mochila ilimitada. ^[28] Su versión clasifica los artículos en orden decreciente de valor por unidad de peso, . Luego procede a introducirlos en el saco, comenzando con tantas copias como sea posible del primer tipo de artículo hasta que ya no haya espacio en el saco para más. Siempre que haya un suministro ilimitado de cada tipo de artículo, si es el valor máximo de artículos que caben en el saco, entonces se garantiza que el algoritmo codicioso alcanzará 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 simple modificación nos permite resolver este caso: Supongamos por simplicidad que todos los artículos caben individualmente en el saco ( para todos ). Construya una solución empaquetando los artículos con avidez el mayor tiempo posible, es decir, donde . Además, construya una segunda solución que contenga el primer elemento que no encajaba. Dado que proporciona un límite superior para la relajación PL del problema, uno de los conjuntos debe tener un valor al menos ; por lo tanto, devolvemos cualquiera de y que 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 con la tasa de error ^[29] ${\displaystyle n^{-1/2}}$

Esquema de aproximación de tiempo totalmente polinomial

El esquema de aproximación de tiempo totalmente 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 polinomiales conocidas es porque las ganancias asociadas con los artículos no están restringidas. Si se redondean algunos de los dígitos menos significativos de los valores de beneficio, entonces estarán acotados por un polinomio y 1/ε donde ε es un límite de la corrección de la solución. Esta restricción significa entonces que un algoritmo puede encontrar una solución en tiempo polinómico que sea correcta dentro de un factor de (1-ε) de la solución óptima. ^[27]

Se ingresa  el algoritmo FPTAS : ε ∈ (0,1] una lista A de n elementos, especificados por sus valores, y pesos de salida: S' la solución FPTAS ${\displaystyle v_{i}}$ P := max // el valor más alto del artículo ${\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 }$  devolver la solución, S', usando los valores en el 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 cuántica aproximada (QAOA) se puede emplear para resolver el problema de mochila mediante computación cuántica minimizando el hamiltoniano del problema. El hamiltoniano de mochila se construye incorporando la condición de restricción a la función de costos del problema con un término de penalización. ^[30] donde es la constante de penalización que se determina mediante un ajuste específico de cada 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 al problema de la mochila ilimitada se puede facilitar desechando elementos que nunca serán necesarios. Para un artículo dado , supongamos que podemos encontrar un conjunto de artículos cuyo peso total es menor que el peso de y su valor total es mayor que el valor de . Entonces no puede aparecer en la solución óptima, porque siempre podemos mejorar cualquier solución potencial que contenga reemplazándola con el conjunto . Por lo tanto, podemos ignorar el elemento -ésimo por completo. En tales casos, se dice que domina . (Tenga en cuenta que esto no se aplica a los problemas de mochila limitada, ya que es posible que ya hayamos agotado 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. Hay varios tipos diferentes de relaciones de dominancia, ^[11] las cuales 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}}$

dónde 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 -ésimo elemento está dominado colectivamente por , escrito como , si el peso total de alguna combinación de elementos en es menor que wi y su valor total es mayor que _{vi .} Formalmente, y para algunos , es decir . Verificar este dominio es difícil desde el punto de vista computacional, por lo que sólo se puede utilizar con un enfoque de programación dinámica. De hecho, esto equivale a resolver un problema de decisión de mochila más pequeño donde , y los artículos 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 -ésimo elemento es un umbral dominado por , escrito como , si un número determinado de copias de están dominados por . Formalmente, y para algunos y . Esta es una generalización de la dominancia colectiva, introducida por primera vez en ^[19] y utilizada en el algoritmo EDUK. El más pequeño define el umbral del artículo , 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 -ésimo elemento está dominado múltiplemente por un solo elemento , escrito como , si está dominado por un número determinado de copias de . Formalmente, y para algunos , es decir . 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 artículo , es decir, para todos . Este es el artículo con mayor densidad de valor. El -ésimo elemento 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

Hay muchas variaciones del problema de la mochila que han surgido 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 ítems, el número de objetivos o incluso el número de mochilas.

Problema de mochila multiobjetivo

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

Como ejemplo, supongamos que dirige un crucero. Tienes que decidir cuántos comediantes famosos contratar. Este barco no puede transportar más de una tonelada de pasajeros y los animadores deben pesar menos de 1000 libras. Cada comediante tiene un peso, genera negocios en función de su popularidad y pide un salario específico. En este ejemplo, tiene múltiples objetivos. Por supuesto, desea maximizar la popularidad de sus artistas y al mismo tiempo minimizar sus salarios. Además, desea tener tantos animadores como sea posible.

Problema de mochila multidimensional

En esta variación, el peso del artículo de la mochila viene dado por un vector de dimensiones D y la mochila tiene un vector de capacidad de dimensiones D. El objetivo es maximizar la suma de los valores de los artículos en la mochila para 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. ^[33] Sin embargo, se muestra que el algoritmo en ^[34] resuelve instancias dispersas de manera eficiente. Una instancia de mochila multidimensional es escasa si hay un conjunto tal que para cada elemento de la mochila , tal que y . Estos casos ocurren, por ejemplo, cuando se programan paquetes en una red inalámbrica con nodos de retransmisión. ^[34] El algoritmo de ^[34] también resuelve casos escasos 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 mochila 2D (empacar cuadrados en un cuadrado de tamaño unitario bidimensional): cuando hay como máximo cinco cuadrados en un empaque óptimo. ^[35]

Problema de mochilas múltiples

Esta variación es similar al problema del embalaje del contenedor . Se diferencia del Problema de embalaje en contenedores en que se puede seleccionar un subconjunto de artículos, mientras que, en el Problema de embalaje en contenedores, todos los artículos deben empaquetarse en determinados contenedores. El concepto es que hay múltiples mochilas. Esto puede parecer un cambio trivial, pero no equivale a aumentar la capacidad de la mochila inicial. Esta variación se utiliza en muchos problemas de carga y programación en Investigación de Operaciones y tiene un esquema de aproximación de tiempo polinomial . ^[36]

Problema de mochila cuadrática

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

Problema de suma de subconjuntos

El problema de suma de subconjuntos es un caso especial de decisión y problemas 0-1 donde el peso de cada tipo de elemento es igual al valor: . En el campo de la criptografía , el término problema de mochila suele utilizarse para referirse específicamente al problema de suma de subconjuntos. El problema de la suma de subconjuntos es uno de los 21 problemas NP-completos de Karp . ^[40] ${\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 varios contenedores con la misma capacidad. Se ha demostrado que la generalización no tiene FPTAS . ^[41]

Problema de mochila geométrica

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

Ver también

• portal de programación informática

• Problema de embalaje de contenedores  : problema matemático y computacional
• Problema de realización de cambios  : 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 por 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 optimización matemática
• Problema continuo de mochila
• Problema de reducción de existencias  : problema matemático en investigación de operaciones
• Subasta de mochilas
• Lista de problemas de mochila
• Problema de embalaje  : problemas que intentan encontrar la forma más eficiente de empaquetar 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 Sociedad Matemática de Londres . 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. Consultado 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. Consultado 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. Consultado 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. Consultado el 5 de mayo de 2022 .
6. Feuerman, Martín; Weiss, Harvey (abril de 1973). "Un modelo de programación matemática para la construcción y puntuación de pruebas". Ciencias de la gestión . 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". Noticias ACM SIGACT . 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 duras? Informe técnico 2003/08, Departamento de Ciencias de la Computación, Universidad de Copenhague, Copenhague, Dinamarca.
9. Caccetta, L.; Kulanot, A. (2001). "Aspectos computacionales de los problemas de mochila dura". Análisis no lineal . 47 (8): 5547–5558. doi :10.1016/s0362-546x(01)00658-7.
10. J. Jooken, P. Leyman, P. De Causmaecker, Una nueva clase de instancias de problemas difíciles para el problema de la mochila 0-1, European Journal of Operational Research , 301 (3): 841-854, 2022.
11. Poirriez, Vicente; Yanev, Nicola; Andonov, Rumen (2009). "Un algoritmo híbrido para el problema de la mochila ilimitada". Optimización discreta . 6 (1): 110–124. doi : 10.1016/j.disopt.2008.09.004 . ISSN  1572-5286. S2CID  8820628.
12. J. Jooken, P. Leyman, P. De Causmaecker, Funciones para el problema de la mochila 0-1 basadas en soluciones máximas de inclusión, European Journal of Operational Research , 311 (1): 36-55, 2023.
13. Wojtczak, Dominik (2018). "Sobre la fuerte integridad NP de los problemas racionales". Informática: teoría y aplicaciones . Apuntes de conferencias sobre informática. vol. 10846. págs. 308–320. arXiv : 1802.09465 . doi :10.1007/978-3-319-90530-3_26. ISBN 978-3-319-90529-7. S2CID  3637366.
14. 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.
15. De hecho, el límite inferior se aplica al problema de la suma de subconjuntos, que es un caso especial de Knapsack.
16. Michael Steele, J; Yao, Andrew C (1 de marzo de 1982). "Límites inferiores de árboles de decisión algebraicos". Revista de algoritmos . 3 (1): 1–8. doi :10.1016/0196-6774(82)90002-5. ISSN  0196-6774.
17. Ben-Amram, Amir M.; Galil, Zvi (2001), "Límites inferiores topológicos en máquinas algebraicas de acceso aleatorio", SIAM Journal on Computing , 31 (3): 722–761, doi :10.1137/S0097539797329397.
18. auf der Heide, Meyer (1984), "Un algoritmo de búsqueda lineal polinomial para el problema de mochila n -dimensional", Journal of the ACM , 31 (3): 668–676, doi :10.1145/828.322450
19. Andonov, Rumen; Poirriez, Vicente; Rajopadhye, Sanjay (2000). "Problema de la mochila ilimitada: 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. 
20. S. Martello, P. Toth, Problemas de mochila: algoritmos e implementaciones informáticas, John Wiley and Sons, 1990
21. S. Martello, D. Pisinger, P. Toth, Programación dinámica y límites fuertes para el problema de la mochila 0-1, Manag. Ciencia. , 45:414–424, 1999.
22. Meseta, G.; Elkihel, M. (1985). "Un algoritmo híbrido para el problema de la mochila 0-1". Métodos de ópera. Res . 49 : 277–293.
23. Martello, S.; Toth, P. (1984). "Una mezcla de programación dinámica y ramificación y limitación para el problema de suma de subconjuntos". Gestionar. Ciencia . 30 (6): 765–771. doi :10.1287/mnsc.30.6.765.
24. Horowitz, Ellis; Sahni, Sartaj (1974), "Computación de particiones con aplicaciones al problema de la mochila", Revista de la Asociación de Maquinaria de Computación , 21 (2): 277–292, doi :10.1145/321812.321823, hdl : 1813/5989 , MR  0354006, S2CID  16866858
25. 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].
26. 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.
27. Vazirani, Vijay. Algoritmos de aproximación. Springer-Verlag Berlín Heidelberg, 2003.
28. Dantzig, George B. (1957). "Problemas de extremos de variables discretas". La investigación de operaciones . 5 (2): 266–288. doi :10.1287/opre.5.2.266.
29. Calvino, James M.; Leung, Joseph Y.-T. (1 de mayo de 2003). "Análisis de caso promedio de un algoritmo codicioso para el problema de la mochila 0/1". Cartas de investigación operativa . 31 (3): 202–210. doi :10.1016/S0167-6377(02)00222-5.
30. Lucas, Andrés (2014). "Ising formulaciones de muchos problemas de NP". Fronteras en Física . 2 : 5. arXiv : 1302.5843 . Código Bib : 2014FrP.....2....5L. doi : 10.3389/fphy.2014.00005 . ISSN  2296-424X.
31. Chang, TJ y col. Heurísticas para la optimización de carteras restringidas por cardinalidad. Informe técnico, Londres SW7 2AZ, Inglaterra: The Management School, Imperial College, mayo de 1998
32. Chang, CS y col. "Optimización de bicriterios basada en algoritmos genéticos para subestaciones de tracción en el sistema ferroviario de CC". En Fogel [102], 11-16.
33. Kulik, A.; Shachnai, H. (2010). «No existe EPTAS para mochila bidimensional» (PDF) . Inf. Proceso. Lett . 110 (16): 707–712. CiteSeerX 10.1.1.161.5838 . doi :10.1016/j.ipl.2010.05.031. 
34. 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.
35. 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.
36. Chandra Chekuri y Sanjeev Khanna (2005). "Un PTAS para el problema de las mochilas múltiples". Revista SIAM de Computación . 35 (3): 713–728. CiteSeerX 10.1.1.226.3387 . doi :10.1137/s0097539700382820. 
37. Wu, ZY; Yang, YJ; Bai, FS; Mammadov, M. (2011). "Condiciones de optimización global y métodos de optimización para problemas de mochila cuadrática". Aplicación de la teoría J Optim . 151 (2): 241–259. doi :10.1007/s10957-011-9885-4. S2CID  31208118.
38. Gallo, G.; Martillo, PL; Simeone, B. (1980). "Problemas cuadráticos de mochila". 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.
39. Witzgall, C. (1975). "Métodos matemáticos de selección de sitio para Sistemas de Mensajes Electrónicos (EMS)". Informe técnico de Sti/Recon de la NASA N. 76 . Informe interno de NBS: 18321. Bibcode : 1975STIN...7618321W.
40. Richard M. Karp (1972). "Reducibilidad entre problemas combinatorios". En RE Miller y JW Thatcher (editores). Complejidad de los cálculos informáticos. Nueva York: Pleno. págs. 85-103
41. 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. 
42. Gálvez, Waldo; Grandoni, Fabricio; Ingala, Salvatore; Heydrich, Sandy; Khan, Arindam; Wiese, Andreas (2021). "Aproximación de la mochila geométrica mediante empaquetaduras en L". Transmisión ACM. Algoritmos : 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 integridad NP . 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. SEÑOR  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

• Repositorio de GitHub que contiene instancias difíciles de problemas de mochila 0-1
• Repositorio de GitHub que contiene funciones para identificar qué dificulta una instancia de problema de mochila 0-1
• Diapositivas de conferencias sobre el problema de la mochila.
• PYAsUKP: Otro solucionador más del problema de la mochila ilimitada, con código que aprovecha las relaciones de dominancia 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 la mochila dura?")
• Soluciones de problemas de mochila en muchos idiomas en Rosetta Code
• Algoritmo de programación dinámica para el problema de mochila 0/1
• Solucionador de problemas de mochila (en línea)
• Resolviendo 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 de contenedores tridimensionales
• Solución de programación entera Knapsack en Python Gekko (software de optimización)