Problema de la mochila

La NP-dificultad del problema de la mochila se relaciona con modelos computacionales en los que el tamaño de los enteros importa (como la máquina de Turing ). En contraste, los árboles de decisión cuentan cada decisión como un solo paso. Dobkin y Lipton ^{[ 13 ]} muestran una${\displaystyle {1 \over 2}n^{2}}$cota inferior en árboles de decisión lineales para el problema de la mochila, es decir, árboles donde los nodos de decisión prueban el signo de funciones afines . ^{[ 14 ]} Esto fue generalizado a árboles de decisión algebraicos por Steele y Yao. ^{[ 15 ]} Si los elementos en el problema son números reales o racionales , la cota 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"). ^{[ 16 ]} Este modelo cubre más algoritmos que el modelo de árbol de decisión algebraico, ya que abarca algoritmos que usan indexación en tablas. Sin embargo, en este modelo se cuentan todos los pasos del programa, no solo las decisiones. Meyer auf der Heide ^{[ 17 ]} dio una cota superior para un modelo de árbol de decisión , quien demostró que para cada n existe un árbol de decisión lineal de O ( n ⁴ ) de profundidad 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 deba resolver el problema para cualquier n dado .

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

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

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

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

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

2.${\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}$, dónde${\displaystyle v_{i}}$es el valor de la${\displaystyle i}$-tipo de artículo.

La segunda propiedad necesita ser explicada en detalle. Durante el proceso de ejecución de este método, ¿cómo obtenemos el peso?${\displaystyle w}$¿Solo hay unos pocos?${\displaystyle i}$formas y los pesos anteriores son${\displaystyle w-w_{1},w-w_{2},...,w-w_{i}}$donde hay totales${\displaystyle i}$tipos de artículos diferentes (al decir diferentes, queremos decir que el peso y el valor no son completamente iguales). Si conocemos el valor de cada uno de estos${\displaystyle i}$Los elementos y el valor máximo relacionado previamente, simplemente los comparamos entre sí y obtenemos el valor máximo final y hemos terminado.

Aquí se toma como cero el máximo del conjunto vacío. Tabulando los resultados de${\displaystyle m[0]}$hasta el final${\displaystyle m[W]}$da la solución. Dado que el cálculo de cada${\displaystyle m[w]}$implica examinar como máximo${\displaystyle n}$artículos, y hay como máximo${\displaystyle W}$valores de${\displaystyle m[w]}$Para calcular el tiempo de ejecución de la solución de programación dinámica es${\displaystyle O(nW)}$. Dividiendo${\displaystyle w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W}$Reducir el tiempo de ejecución mediante su máximo común divisor es una forma de mejorarlo.

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

Problema de la mochila 0-1

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${\displaystyle w_{1},\,w_{2},\,\ldots ,\,w_{n},\,W}$son enteros estrictamente positivos. Definir${\displaystyle m[i,w]}$ser el valor máximo que se puede alcanzar con un peso menor o igual a${\displaystyle w}$utilizando artículos hasta${\displaystyle i}$(primero${\displaystyle i}$elementos).

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

• ${\displaystyle m[0,\,w]=0}$
• ${\displaystyle m[i,\,w]=m[i-1,\,w]}$si${\displaystyle w_{i}>w\,\!}$(el nuevo artículo supera el límite de peso actual)
• ${\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 entonces calculando${\displaystyle m[n,W]}$Para hacerlo de manera eficiente, podemos usar una tabla para almacenar cálculos anteriores.

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

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

Por lo tanto, esta solución se ejecutará en${\displaystyle O(nW)}$tiempo y${\displaystyle O(nW)}$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 últimas líneas del array "m".)

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

// Aporte:// Valores (almacenados en el array v)// Pesos (almacenados en el array w)// Número de elementos distintos (n)// Capacidad de la mochila (W)// NOTA: Se supone que los arrays "v" y "w" almacenan todos los valores relevantes a partir del índice 1.Definir valor [ n , W ]Inicializar todos los valores [ i , j ] = -1Define m := ( i , j ) // Define la función m de modo 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 ] = 0devolverSi ( valor [ i -1 , j ] == -1 ) entonces : // m[i-1, j] no se ha calculado, tenemos que llamar a la función mm ( i -1 , j )Si w [ i ] > j entonces : // el artículo no cabe en la bolsavalor [ 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 mm ( i -1 , j - w [ i ])valor [ i , j ] = max ( valor [ i -1 , j ], valor [ i -1 , j - w [ i ]] + v [ i ])}Ejecutar m ( n , W )

Por ejemplo, hay 10 artículos diferentes y el límite de peso es 67. Entonces, $${\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}}}$$ Si utiliza el método anterior para calcular${\displaystyle m(10,67)}$, obtendrás esto, excluyendo las llamadas que producen${\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 eliminar 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 elementos 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 ) : Set < int > {Si i == 0 entonces :devolver {}Si m [ i , j ] > m [ i -1 , j ] entonces :devolver { i } ∪ mochila ( i -1 , j - w [ i ])demás :devolver mochila ( i -1 , j )}mochila ( n , W )

Otro algoritmo para la mochila 0-1, descubierto en 1974 ^{[ 23 ]} y a veces llamado "encuentro en el medio" debido a 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${\displaystyle W}$es grande en comparación con n . En particular, si el${\displaystyle w_{i}}$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${\displaystyle d}$dígitos fraccionarios de precisión para llegar a la respuesta correcta,${\displaystyle W}$será necesario escalarlo por${\displaystyle 10^{d}}$y el algoritmo DP requerirá${\displaystyle O(W10^{d})}$espacio y${\displaystyle O(nW10^{d})}$tiempo.

El algoritmo Meet-in-the-middle tiene como 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. Mantener un registro del mayor valor combinado visto hasta ahora.

El algoritmo toma${\displaystyle O(2^{n/2})}$espacio, y las implementaciones eficientes del paso 3 (por ejemplo, ordenar los subconjuntos de B por peso, descartar los 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${\displaystyle O(n2^{n/2})}$. Al igual que con el ataque de encuentro en el medio en criptografía, esto mejora el${\displaystyle O(n2^{n})}$tiempo de ejecución de un enfoque ingenuo de fuerza bruta (examinando todos los subconjuntos de${\displaystyle \{1...n\}}$), a costa de utilizar espacio exponencial en lugar de constante (véase también paso a paso, paso a paso ). La mejora actual del algoritmo de encuentro en el medio, utilizando ideas del algoritmo de Schroeppel y Shamir para la suma de subconjuntos, proporciona como corolario un algoritmo aleatorio para la mochila que conserva el${\displaystyle O^{*}(2^{n/2})}$(hasta factores polinomiales) tiempo de ejecución y reduce los requisitos de espacio a${\displaystyle O^{*}(2^{0.249999n})}$(véase ^{[ 24 ]} Corolario 1.4). En contraste, el algoritmo determinista más conocido se ejecuta en${\displaystyle O^{*}(2^{n/2})}$tiempo con una complejidad espacial ligeramente peor de${\displaystyle O^{*}(2^{n/4})}$. ^{[ 25 ]}

Como ocurre con la mayoría de los problemas NP-completos, puede ser suficiente encontrar soluciones viables, aunque no sean óptimas. Sin embargo, lo ideal es que la aproximación incluya 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 ha investigado ampliamente la creación y el análisis de algoritmos que aproximan una solución. El problema de la mochila, aunque NP-difícil, pertenece a un conjunto de algoritmos que pueden aproximarse a cualquier grado especificado. Esto significa que el problema tiene un esquema de aproximación en tiempo polinomial. Para ser exactos, el problema de la mochila tiene un esquema de aproximación en tiempo totalmente polinomial (FPTAS). ^{[ 26 ]}

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

Resolver el problema de la mochila ilimitada puede hacerse más fácil descartando los objetos que nunca se necesitarán. Para un objeto dado${\displaystyle i}$Supongamos que pudiéramos encontrar un conjunto de elementos${\displaystyle J}$de tal manera que su peso total sea menor que el peso de${\displaystyle i}$y su valor total es mayor que el valor de${\displaystyle i}$. Entonces${\displaystyle i}$no puede aparecer en la solución óptima, porque siempre podríamos mejorar cualquier solución potencial que contenga${\displaystyle i}$reemplazando${\displaystyle i}$con el conjunto${\displaystyle J}$Por lo tanto, podemos ignorar el${\displaystyle i}$-ésimo elemento en total. En tales casos,${\displaystyle J}$Se dice que domina${\displaystyle i}$. (Tenga en cuenta que esto no se aplica a los problemas de la mochila acotada, ya que es posible que ya hayamos utilizado los elementos en${\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 , ^{[ 11 ]} que satisfacen una desigualdad de la forma:

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

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

Dominio colectivo

El${\displaystyle i}$El elemento -ésimo está dominado colectivamente por${\displaystyle J}$, escrito como${\displaystyle i\ll J}$, si el peso total de alguna combinación de elementos en${\displaystyle J}$es menor que w _i y su valor total es mayor que v _i . Formalmente,${\displaystyle \sum _{j\in J}w_{j}\,x_{j}\ \leq w_{i}}$y${\displaystyle \sum _{j\in J}v_{j}\,x_{j}\ \geq v_{i}}$para algunos${\displaystyle x\in Z_{+}^{n}}$, es decir${\displaystyle \alpha =1}$Verificar este dominio 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${\displaystyle V=v_{i}}$,${\displaystyle W=w_{i}}$y los artículos están restringidos a${\displaystyle J}$.

Dominancia del umbral

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

Dominancia múltiple

El${\displaystyle i}$El elemento -ésimo está dominado múltiplemente por un solo elemento.${\displaystyle j}$, escrito como${\displaystyle i\ll _{m}j}$, si${\displaystyle i}$está dominado por un cierto número de copias de${\displaystyle j}$Formalmente,${\displaystyle w_{j}\,x_{j}\ \leq w_{i}}$, y${\displaystyle v_{j}\,x_{j}\ \geq v_{i}}$para algunos${\displaystyle x_{j}\in Z_{+}}$es decir${\displaystyle J=\{j\},\alpha =1,x_{j}=\lfloor {\frac {w_{i}}{w_{j}}}\rfloor }$Este predominio podría utilizarse eficazmente durante el preprocesamiento, ya que puede detectarse con relativa facilidad.

Dominio modular

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

Aquí, en lugar de un único objetivo (por ejemplo, maximizar el beneficio monetario de los artículos en la mochila), puede haber varios objetivos. Por ejemplo, podrían existir preocupaciones ambientales o sociales, además de objetivos económicos. Entre los problemas que se abordan con frecuencia se incluyen la optimización de la cartera y la logística del transporte. ^{[ 30 ] [ 31 ]}

Por ejemplo, supongamos que usted dirige un crucero. Debe decidir cuántos comediantes famosos contratar. El barco tiene una capacidad máxima de una tonelada de pasajeros y los artistas deben pesar menos de 450  kg. Cada comediante tiene un peso, genera ingresos según su popularidad y solicita un salario específico. En este ejemplo, usted tiene varios objetivos. Por supuesto, desea maximizar la popularidad de sus artistas y minimizar sus salarios. Además, desea contar con la mayor cantidad de artistas posible.

Aquí, el peso del artículo de la mochila${\displaystyle i}$está dado por un vector D-dimensional${\displaystyle {\overline {w_{i}}}=(w_{i1},\ldots ,w_{iD})}$y la mochila tiene un vector de capacidad D-dimensional${\displaystyle (W_{1},\ldots ,W_{D})}$El objetivo es maximizar la suma de los valores de los artículos en la mochila de modo que la suma de los pesos en cada dimensión${\displaystyle d}$no excede${\displaystyle W_{d}}$.

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

El algoritmo IHS (Increasing Height Shelf) es óptimo para el problema de la mochila 2D (empaquetar cuadrados en un cuadrado bidimensional de tamaño unitario): cuando hay como máximo cinco cuadrados en un empaquetamiento óptimo. ^{[ 34 ]}

Aquí, hay varias mochilas. Esto puede parecer un cambio trivial, pero no es equivalente a aumentar la capacidad de la mochila inicial, ya que cada mochila tiene su propia restricción de capacidad. Esta variación se utiliza en muchos problemas de carga y programación en Investigación Operativa y tiene un esquema de aproximación de tiempo polinomial . ^{[ 35 ]} Esta variación es similar al Problema de Empaquetado de Contenedores . Se diferencia del Problema de Empaquetado de Contenedores en que se puede seleccionar un subconjunto de artículos, mientras que, en el Problema de Empaquetado de Contenedores, todos los artículos deben empaquetarse en ciertos contenedores.

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

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. ^{[ 39 ]}

En el problema de la mochila en línea , los objetos llegan uno a uno. Cada vez que llega un objeto, debemos decidir inmediatamente si lo colocamos en la mochila o lo descartamos. Hay dos variantes: (a) no extraíble: un objeto insertado permanece en la mochila para siempre; (b) extraíble: un objeto insertado puede retirarse posteriormente para dejar espacio para uno nuevo.

Han, Kawase y Makino ^{[ 40 ]} presentan un algoritmo aleatorio para el caso no ponderado y no removible. Es 2-competitivo, lo cual es lo mejor posible. Para el caso ponderado y removible, presentan un algoritmo 2-competitivo, demuestran una cota inferior de ~1,368 para algoritmos aleatorios y prueban que ningún algoritmo determinista puede tener una razón competitiva constante. Para el caso no ponderado y removible, presentan un algoritmo con una razón competitiva de 10/7 y demuestran una cota inferior de 1,25.

Hay varios otros artículos sobre el problema de la mochila en línea. ^{[ 41 ] [ 42 ] [ 43 ]}