Problema de mochila

Ejemplo de un problema de knapsack unidimensional (constructor): ¿qué cajas deben elegirse para maximizar la cantidad de dinero mientras mantiene el peso total bajo o igual a 15 kg? Un problema con restricciones múltiples podría considerar tanto el peso como el volumen de las cajas.
(Solución: si hay algún número de cada caja disponible, entonces tres cajas amarillas y tres cajas grises; si sólo las cajas mostradas están disponibles, entonces todas excepto la caja verde).

El problema de la mochila es un problema de optimización combinatoria: dado un conjunto de elementos, cada uno con un peso y un valor, determine el número de cada elemento que se incluirá en una colección para que el peso total es menor o igual a un límite dado y el valor total es lo más grande posible. Deriva su nombre 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 surge a menudo en la asignación de recursos, donde los responsables 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 datan de 1897. El nombre "problema de la mochila" se remonta a los primeros trabajos del matemático Tobias Dantzig (1884-1956) y se refiere al problema común de empacar los artículos más valiosos o útiles sin sobrecargar el equipaje.

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 reducir las materias primas, seleccionar inversiones y carteras, seleccionar activos para la titulización respaldada por activos y generar claves para Merkle-Hellman y otros criptosistemas de mochila.

Una de las primeras aplicaciones de los algoritmos de mochila fue en la construcción y calificación de pruebas en las que los examinados pueden elegir qué preguntas responder. Para pequeños ejemplos, 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 un puntaje máximo posible de 100 puntos. Sin embargo, en pruebas 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 a los estudiantes se les da una prueba heterogénea 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 otorga a cada estudiante la puntuación más alta posible.

Un estudio de 1999 del repositorio de algoritmos de la Universidad de Stony Brook mostró que, de 75 problemas algorítmicos, 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 en contenedores.

Definición

El problema más común que se está solucionando es el 0-1 knapsack problem, que restringe el número xi{displaystyle x_{i}} de copias de cada tipo de artículo a cero o uno. Dado un conjunto de n{displaystyle n} números de 1 a 1 n{displaystyle n}, cada uno con un peso wi{displaystyle ¿Qué? y un valor vi{displaystyle V_{i}, junto con una capacidad máxima de peso W{displaystyle W.,

maximizar .. i=1nvixi{displaystyle sum ¿Qué?

sujeto a .. i=1nwixi≤ ≤ W{displaystyle sum ¿Por qué? W. y xi▪ ▪ {}0,1}{displaystyle x_{i}in {0,1}.

Aquí. xi{displaystyle x_{i}} representa el número de casos de tema i{displaystyle i} para incluir en la mochila. Informalmente, el problema es maximizar la suma de los valores de los elementos en el knapsack para que la suma de los pesos sea inferior o igual a la capacidad del knapsack.

El problema de knapsack ()BKP) elimina la restricción de que sólo hay uno de cada artículo, pero restringe el número xi{displaystyle x_{i}} de copias de cada tipo de artículo a un valor máximo no negativo c{displaystyle c}:

maximizar .. i=1nvixi{displaystyle sum ¿Qué?

sujeto a .. i=1nwixi≤ ≤ W{displaystyle sum ¿Por qué? W. y xi▪ ▪ {}0,1,2,...... ,c}.{displaystyle x_{i}in {0,1,2,dotsc}

El problema knapsack sin límites ()UKP) no coloca ningún límite superior en el número de copias de cada tipo de artículo y puede ser formulado como arriba excepto que la única restricción en xi{displaystyle x_{i}} es que es un entero no negativo.

maximizar .. i=1nvixi{displaystyle sum ¿Qué?

sujeto a .. i=1nwixi≤ ≤ W{displaystyle sum ¿Por qué? W. y xi▪ ▪ Z,xi≥ ≥ 0.{displaystyle x_{i}in mathbb {Z} x_{i}geq 0.}

Se proporciona un ejemplo del problema de la mochila ilimitada utilizando la figura que se muestra al principio de este artículo y el texto "si hay algún número disponible de cada caja" en la leyenda de esa figura.

Complejidad computacional

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

• El problema de la decisión forma del problema de la mochila (Puede un valor al menos V ser alcanzado sin exceder el peso W?) es NP-completo, por lo tanto no hay algoritmo conocido que sea correcto y rápido (polynomial-time) en todos los casos.
• Si bien el problema de la decisión es completo, el problema de la optimización no es, su resolución es al menos tan difícil como el problema de la decisión, y no hay un algoritmo polinomio conocido que pueda decir, dada una solución, si es óptima (lo que significaría que no hay solución con un algoritmo más grande V, resolviendo así el problema de la decisión completa del PNP).
• Hay un algoritmo de tiempo pseudo-polynomial usando programación dinámica.
• Hay un esquema de aproximación de tiempo totalmente polinomio, que utiliza el algoritmo de tiempo pseudo-polynomial como una subrutina, descrito a continuación.
• Muchos casos que surgen en la práctica, y "experiencias raras" de algunas distribuciones, no obstante pueden resolverse exactamente.

Existe un vínculo entre la "decisión" y "optimización" problemas en que si existe un algoritmo polinomial que resuelve la "decisión" problema, entonces uno puede encontrar el valor máximo para el problema de optimización en tiempo polinomial aplicando este algoritmo iterativamente mientras se incrementa 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 salida de solución de 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 qué es lo "difícil" Las instancias del problema de la mochila parecen, o se ven de otra manera, para identificar qué propiedades de las instancias en la práctica podrían hacerlas más susceptibles de lo que sugiere su comportamiento NP-completo en el peor de los casos. El objetivo de encontrar estos "difíciles" Las instancias son para su uso en sistemas de criptografía de clave pública, como el criptosistema de mochila Merkle-Hellman.

Además, destaca el hecho de que la dureza 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. Sin embargo, en el caso de pesos y beneficios racionales aún admite un esquema de aproximación en tiempo totalmente polinomial.

Resolver

Hay varios algoritmos disponibles para resolver problemas de mochila, basados en el enfoque de programación dinámica, el enfoque de ramificación y límite o hibridaciones de ambos enfoques.

Algoritmo avanzado de programación dinámica

El problema knapsack sin límites ()UKP) no coloca ninguna restricción en el número de copias de cada tipo de artículo. Además, aquí suponemos que 0}" xmlns="http://www.w3.org/1998/Math/MathML">xi■0{displaystyle x_{i}0} 0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d7ca010976c6eb10a9e66a4ec495766452bfe828" style="vertical-align: -0.671ex; width:6.39ex; height:2.509ex;"/>

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

sujeto a .. i=1nwixi≤ ≤ w.{displaystyle sum ¿Por qué? ♪ y 0}" xmlns="http://www.w3.org/1998/Math/MathML">xi■0{displaystyle x_{i}0} 0" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d7ca010976c6eb10a9e66a4ec495766452bfe828" style="vertical-align: -0.671ex; width:6.39ex; height:2.509ex;"/>

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

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

2. m[w]=max()v1+m[w− − w1],v2+m[w− − w2],...,vn+m[w− − wn]){displaystyle m[w]=max(v_{1}+m[w-w_{1}],v_{2}+m[w-w_{2}],...,v_{n}+m[w-w_{n})}, wi≤ ≤ w{displaystyle ¿Qué?, donde vi{displaystyle V_{i} es el valor del i{displaystyle i}- el tipo de artículo.

La segunda propiedad debe explicarse detalladamente. Durante el proceso de funcionamiento de este método, ¿cómo obtenemos el peso w{displaystyle w}? Sólo hay i{displaystyle i} formas y los pesos anteriores son w− − w1,w− − w2,...,w− − wi{displaystyle ¿Qué? donde hay total i{displaystyle i} tipos de artículo diferente (por decir diferente, queremos decir que el peso y el valor no son completamente iguales). Si conocemos cada valor de estos i{displaystyle i} ítems y el valor máximo relacionado anteriormente, simplemente los comparamos entre sí y obtenemos el valor máximo en última instancia y se hace.

Aquí el máximo del conjunto vacío se toma como cero. Tabulación de los resultados m[0]{displaystyle m[0] arriba m[W]{displaystyle m[W] da la solución. Desde el cálculo de cada uno m[w]{displaystyle m[w]} implica examinar en la mayoría n{displaystyle n} artículos, y hay en la mayoría W{displaystyle W. valores de m[w]{displaystyle m[w]} para calcular, el tiempo de funcionamiento de la solución de programación dinámica es O()nW){displaystyle O(nW)}. Dividir w1,w2,...... ,wn,W{displaystyle ¿Qué? por su mayor divisor común es una manera de mejorar el tiempo de funcionamiento.

Incluso si PieraNP, el O()nW){displaystyle O(nW)} la complejidad no contradice el hecho de que el problema knapsack es completo NP, ya que W{displaystyle W., a diferencia n{displaystyle n}, no es polinomio en la longitud de la entrada al problema. La longitud de la W{displaystyle W. la entrada al problema es proporcional al número de bits en W{displaystyle W., log⁡ ⁡ W{displaystyle log W}, no a W{displaystyle W. en sí mismo. Sin embargo, dado que este tiempo de ejecución es pseudopolítico, esto hace que el (versión de decisión del) problema de la mochila un problema débilmente completo NP.

Problema de mochila 0-1

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

Una solución de programación dinámica similar para el problema de 0-1 knapsack también se ejecuta en tiempo pseudo-polynomial. Assume w1,w2,...... ,wn,W{displaystyle ¿Qué? son enteros estrictamente positivos. Define m[i,w]{displaystyle m[i,w]} ser el valor máximo que se puede alcanzar con peso inferior o igual a w{displaystyle w} utilizar elementos hasta i{displaystyle i} (primero) i{displaystyle i} ítems).

Podemos definir m[i,w]{displaystyle m[i,w]} recursivamente como sigue: (Definición A)

• m[0,w]=0{displaystyle m[0,,w]=0}
• m[i,w]=m[i− − 1,w]{displaystyle m[i,,w]=m[i-1,,w] si w,!}" xmlns="http://www.w3.org/1998/Math/MathML">wi■w{displaystyle ¡No!w,!" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/9135ba545782f152ca4c833311af638b13cc6aee" style="vertical-align: -0.671ex; margin-right: -0.387ex; width:7.614ex; height:2.176ex;"/> (el nuevo elemento es más que el límite de peso actual)
• m[i,w]=max()m[i− − 1,w],m[i− − 1,w− − wi]+vi){displaystyle m[i,,w]=max(m[i-1,,w],,m[i-1,w-w_{i}]+v_{i}) } si wi⩽ ⩽ w{displaystyle ¿Qué?.

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

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

// Entrada:// Valores (establecidos en array v)// Pesos (establecido en array w)// Número de artículos distintos (n)// Capacidad de Knapsack (W)// NOTA: Se supone que el array "v" y el array "w" almacenan todos los valores relevantes comenzando en el índice 1.array m[0..n, 0..W];para j desde 0 a W do: m[0, j] := 0para i desde 1 a n do: m[i, 0] := 0para i desde 1 a n do: para j desde 0 a W do: si w[i] ■ j entonces: m[i, j] := m[i-1, j] más: m[i, j] := max()m[i-1, j] m[i-1, j-w[i]] + v[i])

Por lo tanto, esta solución funcionará O()nW){displaystyle O(nW)} tiempo y tiempo O()nW){displaystyle O(nW)} espacio. (Si sólo 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 lo damos un paso o dos más, deberíamos saber que el método funcionará en el tiempo entre O()nW){displaystyle O(nW)} y O()2n){displaystyle O(2^{n}}. Desde Definición A, sabemos que no hay necesidad de calcular todos los pesos cuando el número de artículos y los artículos que elegimos están fijos. Es decir, el programa arriba calcula más que necesario porque el peso cambia de 0 a W a menudo. Desde esta perspectiva, podemos programar este método para que funcione recursivamente.

// Entrada:// Valores (establecidos en array v)// Pesos (establecido en array w)// Número de artículos distintos (n)// Capacidad de Knapsack (W)// NOTA: Se supone que el array "v" y el array "w" almacenan todos los valores relevantes comenzando en el índice 1.Define valor[n, W]Inicializar Todos valor[i, j] = -1Define m:=()i,j) // Definir función m para que represente el valor máximo que podemos obtener bajo la condición: utilizar primero i elementos, límite de peso total es j{} si i == 0 o j . 0 entonces: valor[i, j] = 0 retorno 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: // artículo no puede caber en la bolsa valor[i, j] = valor[i-1, j] más:  si ()valor[i-1, j-w[i]] == -1) entonces: // m[i-1,j-w[i]] no se ha calculado, tenemos que llamar a la función m m()i-1, j-w[i]) valor[i, j] = max()valor[i-1,j] valor[i-1, j-w[i]] + v[i])}Corre m()n, W)

Por ejemplo, hay 10 artículos diferentes y el límite de peso es 67. Entonces,

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]=27v[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[54]=30,w[10]=27\vign=505,v[2]=354]

Si utiliza el método anterior para calcular m()10,67){displaystyle m(10,67)}Usted recibirá esto, excluyendo las llamadas que producen m()i,j)=0{displaystyle m(i,j)=0}:

m()10,67)=1270m()9,67)=1270,m()9,40)=678m()8,67)=1270,m()8,40)=678,m()8,37)=545m()7,67)=1183,m()7,41)=725,m()7,40)=678,m()7,37)=505m()6,67)=1183,m()6,41)=725,m()6,40)=678,m()6,38)=678,m()6,37)=505m()5,67)=1183,m()5,41)=725,m()5,40)=678,m()5,38)=678,m()5,37)=505m()4,67)=1183,m()4,41)=725,m()4,40)=678,m()4,38)=678,m()4,37)=505,m()4,35)=505m()3,67)=963 - 963,m()3,49)=963 - 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)=458m()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)=505m()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)=5050,40 = 0,75 m

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 elementos de la mochila óptima. * i: Podemos incluir los elementos 1 a i en el knapsack * j: peso máximo de la mochila */función knapsack()i: int, j: int): Set.int■ {} si i == 0 entonces: retorno {} si m[i, j] ■ m[i-1, j] entonces: retorno {}i} ∪ knapsack()i-1, j-w[i]) más: retorno knapsack()i-1, j)}knapsack()n, W)

Reunión en el medio

Otro algoritmo para 0-1 knapsack, descubierto en 1974 y a veces llamado "meet-in-the-middle" debido a paralelos a un algoritmo similarmente llamado en la criptografía, es exponencial en el número de elementos diferentes pero puede ser preferible al algoritmo DP cuando W{displaystyle W. es grande en comparación con n. En particular, si wi{displaystyle ¿Qué? son no negativos pero no enteros, todavía podríamos utilizar el algoritmo de programación dinámica escalando y redondeando (es decir, usando aritmética de punto fijo), pero si el problema requiere d{displaystyle d} dígitos fraccionados de precisión para llegar a la respuesta correcta, W{displaystyle W. tendrá que ser escalada por 10d{displaystyle 10^{d}, y el algoritmo DP necesitará O()W10d){displaystyle O(W10^{d}} espacio y O()nW10d){displaystyle O(nW10^{d}} tiempo.

algoritmo Conocer al medio es entrada: Un conjunto de elementos con pesos y valores.
 Producto: El mayor valor combinado de un subconjunto.

partición el set {1...n} en dos sets A y B de aproximadamente igual tamaño
computar los pesos y valores de todos los subconjuntos de cada conjunto

 para cada uno subset de A doencontrar el subconjunto B de mayor valor tal que el peso combinado es menos que Wrealizar un seguimiento del mayor valor combinado visto hasta ahora

El algoritmo toma O()2n/2){displaystyle O(2^{n/2}} espacio, e implementaciones eficientes del paso 3 (por ejemplo, clasificando los subconjuntos de B por peso, descartando subconjuntos de B que pesan más que otros subconjuntos de B de mayor o igual valor, y utilizando búsqueda binaria para encontrar el mejor partido) resultan en un tiempo de ejecución de O()n2n/2){displaystyle O(n2^{n/2}}. Como con la reunión en el ataque medio en la criptografía, esto mejora en la O()n2n){displaystyle O(n2^{n}} tiempo de ejecución de un enfoque de fuerza bruta ingenua (examinando todos los subconjuntos de {}1...n}{displaystyle {1...n}), a costa de utilizar espacio exponencial en lugar de constante (ver también paso gigante del paso del bebé).

Algoritmos de aproximación

En cuanto a 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.

Al igual que con muchos algoritmos útiles pero computacionalmente complejos, ha habido una investigación sustancial sobre la creación y el análisis de algoritmos que se aproximan a una solución. El problema de la mochila, aunque NP-Hard, es uno de una colección de algoritmos que aún se pueden aproximar en 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).

Algoritmo de aproximación codiciosa

George Dantzig propuso un algoritmo de aproximación codicioso para resolver el problema de la mochila sin límites. Su versión clasifica los elementos en orden decreciente de valor por unidad de peso, v1/w1≥ ≥ ⋯ ⋯ ≥ ≥ vn/wn{displaystyle v_{1}/w_{1}geq cdots geq ¿Qué?. Luego procede a insertarlos 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 m{displaystyle m} es el valor máximo de los artículos que encajan en el saco, entonces el algoritmo codicioso está garantizado para alcanzar al menos un valor de m/2{displaystyle m/2}.

Para el problema ligado, donde el suministro de cada tipo de elemento es limitado, el algoritmo anterior puede estar lejos de ser óptimo. Sin embargo, una simple modificación nos permite resolver este caso: Asumo para la simplicidad que todos los artículos caben individualmente en el saco (wi≤ ≤ W{displaystyle w_{i}leq W. para todos i{displaystyle i}). Construir una solución S1{displaystyle S_{1} por empaquetar los artículos con avidez el mayor tiempo posible, es decir, S1={}1,...... ,k}{displaystyle S_{1}=left{1,ldotskright} Donde k=max1≤ ≤ k.≤ ≤ n.. i=1k.wi≤ ≤ W{displaystyle k=textstyle max _{1leq k'leq n}textstyle sum ¿Qué? W.. Además, construir una segunda solución S2={}k+1}{displaystyle S_{2}=left{k+1right} conteniendo el primer artículo que no encajaba. Desde S1∪ ∪ S2{displaystyle S_{1}cup S_{2} proporciona un límite superior para la relajación del LP del problema, uno de los conjuntos debe tener valor al menos m/2{displaystyle m/2}; así regresamos lo que sea S1{displaystyle S_{1} y S2{displaystyle S_{2} tiene mejor valor para obtener 1/2{displaystyle 1/2}- Aproximación.

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

Esquema de aproximación de tiempo completamente polinomial

El esquema de aproximación de tiempo polinomial completo (FPTAS) para el problema de la mochila aprovecha el hecho de que el problema no tiene soluciones de tiempo polinomial conocidas 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 beneficio, entonces estarán limitados por un polinomio y 1/ε donde ε es un límite en la corrección de la solución. Entonces, esta restricción significa 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.

algoritmo FPTAS es entrada: ε latitud (0,1]
a lista A de n elementos, especificados por sus valores,      v  i     {displaystyle V_{i} , y pesos
 Producto: S' la solución FPTAS

P:= max     {}  v  i   ▪ ▪  1 ≤ ≤  i ≤ ≤  n }   {displaystyle {v_{i}mid 1leq ileq n}  // el valor del artículo más alto
K:= ε       P n     {displaystyle {frac {fn}}}  para i desde 1 a n do      v  i  .    {displaystyle vs. :=      ⌊    v  i   K   ⌋    {displaystyle leftlfloor {frac Está bien.  final for retorno la solución, S', usando la      v  i  .    {displaystyle vs.  valores en el programa dinámico descrito arriba

Teorema: El set S.{displaystyle S' computed by the algoritmo above satisfies profit()S.)≥ ≥ ()1− − ε ε )⋅ ⋅ profit()SAlternativa Alternativa ){displaystyle mathrm {profit} (S')geq (1-varepsilon)cdot mathrm {profit} (S^{*})}, donde SAlternativa Alternativa {displaystyle S^{*} es una solución óptima.

Relaciones de dominación

Resolver el problema knapsack sin límites puede ser más fácil tirando artículos que nunca serán necesarios. Para un artículo determinado i{displaystyle i}, supongamos que podríamos encontrar un conjunto de elementos J{displaystyle J} tal que su peso total es menor que el peso i{displaystyle i}, y su valor total es mayor que el valor i{displaystyle i}. Entonces... i{displaystyle i} no puede aparecer en la solución óptima, porque siempre podríamos mejorar cualquier solución potencial que contenga i{displaystyle i} reemplazando i{displaystyle i} con el conjunto J{displaystyle J}. Por lo tanto, podemos ignorar el i{displaystyle i}- todo. En esos casos, J{displaystyle J} se dice que dominar i{displaystyle i}. (Nota que esto no se aplica a problemas de knapsack ligados, ya que podemos haber utilizado ya los elementos en J{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, que satisfacen una desigualdad de la forma:

.. j▪ ▪ Jwjxj≤ ≤ α α wi{displaystyle qquad sum _{jin J}w_{j},x_{j}leq alpha #, y .. j▪ ▪ Jvjxj≥ ≥ α α vi{displaystyle sum _{jin J}v_{j},x_{j} geq alpha ,v_{i},} para algunos x▪ ▪ Z+n{displaystyle xin Z_{+} {n}}

Donde α α ▪ ▪ Z+,J⊊ ⊊ N{displaystyle alpha in Z_{+},Jsubsetneq N} y i∉J{displaystyle inot in J}. El vector x{displaystyle x} denota el número de copias de cada miembro J{displaystyle J}.

Predominio colectivo

El i{displaystyle i}- el tema es dominado colectivamente por J{displaystyle J}, escrito como i≪ ≪ J{displaystyle ill J}, si el peso total de alguna combinación de elementos en J{displaystyle J} es menos que w_i y su valor total es mayor que v_i. Formalmente, .. j▪ ▪ Jwjxj≤ ≤ wi{displaystyle sum _{jin J}w_{j},x_{j}leq w_{i} y .. j▪ ▪ Jvjxj≥ ≥ vi{displaystyle sum _{jin J}v_{j},x_{j}geq v_{i} para algunos x▪ ▪ Z+n{displaystyle xin Z_{+} {n}}, es decir. α α =1{displaystyle alpha =1}. Verificar este dominio es computacionalmente duro, por lo que sólo se puede utilizar con un enfoque dinámico de programación. De hecho, esto es equivalente a resolver un problema de decisión más pequeño knapsack donde V=vi{displaystyle V=v_{i}, W=wi{displaystyle W=w_{i}, y los artículos están restringidos J{displaystyle J}.

Predominio de la Umbral

El i{displaystyle i}- el tema es umbral dominado por J{displaystyle J}, escrito como i≺ ≺ ≺ ≺ J{displaystyle iprec prec J}, si algún número de copias de i{displaystyle i} están dominados J{displaystyle J}. Formalmente, .. j▪ ▪ Jwjxj≤ ≤ α α wi{displaystyle sum _{jin J}w_{j},x_{j}leq alpha #, y .. j▪ ▪ Jvjxj≥ ≥ α α vi{displaystyle sum _{jin J}v_{j},x_{j} geq alpha ,v_{i},} para algunos x▪ ▪ Z+n{displaystyle xin Z_{+} {n}} y α α ≥ ≥ 1{displaystyle alpha geq 1}. Esta es una generalización de la dominación colectiva, introducida y utilizada por primera vez en el algoritmo EDUK. El más pequeño tal α α {displaystyle alpha } define el umbral del tema i{displaystyle i}, escrito ti=()α α − − 1)wi{displaystyle ¿Qué?. En este caso, la solución óptima podría contener al máximo α α − − 1{displaystyle alpha -1} copias de i{displaystyle i}.

Predominio múltiple

El i{displaystyle i}- el tema es multiplicación dominada por un solo artículo j{displaystyle j}, escrito como i≪ ≪ mj{displaystyle ill _{m}j}, si i{displaystyle i} está dominado por algún número de copias de j{displaystyle j}. Formalmente, wjxj≤ ≤ wi{displaystyle ¿Qué? ¿Qué?, y vjxj≥ ≥ vi{displaystyle ¿Qué? para algunos xj▪ ▪ Z+{displaystyle x_{j}in Z_{+} i.e. J={}j},α α =1,xj=⌊ ⌊ wiwj⌋ ⌋ {displaystyle J={j},alpha =1,x_{j}=lfloor {frac {fnK} {fn}}rfloor. Este dominio podría ser utilizado eficientemente durante el preprocesamiento porque se puede detectar relativamente fácilmente.

Predominio modular

Vamos b{displaystyle b} ser el el mejor tema, es decir. vbwb≥ ≥ viwi{fnMicroc} {V_{b} {w_{b}}gq ¿Qué? para todos i{displaystyle i}. Este es el artículo con la mayor densidad de valor. El i{displaystyle i}- el tema es dominado modularmente por un solo artículo j{displaystyle j}, escrito como i≪ ≪ ↑ ↑ j{displaystyle ill _{equiv}j}, si i{displaystyle i} está dominado por j{displaystyle j} más varias copias de b{displaystyle b}. Formalmente, wj+twb≤ ≤ wi{displaystyle w_{j}+tw_{b}leq ¿Qué?, y vj+tvb≥ ≥ vi{displaystyle v_{j}+tv_{b}geq V_{i} i.e. J={}b,j},α α =1,xb=t,xj=1{displaystyle J={b,j},alpha =1,x_{b}=t,x_{j}=1}.

Variaciones

Hay muchas variaciones del problema de la mochila que han surgido a partir de la gran cantidad de aplicaciones del problema básico. Las principales variaciones ocurren 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 mochila multiobjetivo

Esta variación cambia el objetivo del individuo llenando 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 cartera y logística de transporte.

Como ejemplo, suponga que dirige un crucero. Tienes que decidir cuántos comediantes famosos contratar. Este barco no puede manejar más de una tonelada de pasajeros y los animadores deben pesar menos de 1000 lbs. 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 animadores y minimizar sus salarios. Además, desea tener tantos animadores como sea posible.

Problema de mochila multidimensional

En esta variación, el peso de knapsack elemento i{displaystyle i} es dado por un vector D-dimensional wī ̄ =()wi1,...... ,wiD){displaystyle {fnline {w_{i}=(w_{i1},ldotsw_{iD}} y el knapsack tiene un vector de capacidad D ()W1,...... ,WD){displaystyle (W_{1},ldotsW_{D}}. El objetivo es maximizar la suma de los valores de los elementos en el knapsack para que la suma de pesos en cada dimensión d{displaystyle d} no exceda Wd{displaystyle W_{d}.

Knapsack multidimensional es computacionalmente más duro que knapsack; incluso para D=2{displaystyle D=2}, el problema no tiene EPTAS a menos que P={displaystyle =}NP. Sin embargo, el algoritmo en se muestra para resolver casos escasos de manera eficiente. Una instancia de knapsack multidimensional es escasa si hay un conjunto J={}1,2,...... ,m}{displaystyle J={1,2,ldotsm}} para <math alttext="{displaystyle mm.D{displaystyle m won}<img alt="m tal que por cada knapsack artículo i{displaystyle i}, m}" xmlns="http://www.w3.org/1998/Math/MathML">∃ ∃ z■m{displaystyle exists z títulom}m" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/ca38ed867e171d564a0cb209375f85274015a534" style="vertical-align: -0.338ex; width:7.52ex; height:2.176ex;"/> tales que О О j▪ ▪ J∪ ∪ {}z},wij≥ ≥ 0{displaystyle forall jin Jcup {z} w_{ij}gq 0} y О О Sí.∉ ∉ J∪ ∪ {}z},wiSí.=0{displaystyle forall ynotin Jcup {fnMicrosoft Sans Serif}. Estos casos ocurren, por ejemplo, cuando se programan paquetes en una red inalámbrica con nodos de relé. El algoritmo también resuelve casos escasos de la variante de opción múltiple, knapsack multi-dimensional de selección múltiple.

El algoritmo IHS (estante de altura creciente) es óptimo para la mochila 2D (cuadrados de empaque en un cuadrado de tamaño de unidad bidimensional): cuando hay como máximo cinco cuadrados en un empaque óptimo.

Problema de múltiples mochilas

Esta variación es similar al problema de embalaje en contenedores. 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 contenedores determinados. 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 usa en muchos problemas de programación y carga en Investigación de operaciones y tiene un esquema de aproximación de tiempo polinomial.

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 lineales y binarias. El problema fue presentado por Gallo, Hammer y Simeone en 1980, sin embargo, el primer tratamiento del problema se remonta a Witzgall en 1975.

Problema de suma de subconjuntos

El problema de la suma del subconjunto es un caso especial de la decisión y 0-1 problemas donde cada tipo de artículo, el peso es igual al valor: wi=vi{displaystyle ¿Qué?. En el campo de la criptografía, el término knapsack problem a menudo se utiliza para referirse específicamente al problema de la suma del subconjunto y es comúnmente conocido como uno de los 21 problemas completos de Karp NP.

La generalización del problema de la 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 un FPTAS.

Problema de mochila geométrica

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