Problema continuo de la mochila

En la ciencia de la computación teórica , el problema de la mochila continua (también conocido como problema de la mochila fraccionaria ) es un problema algorítmico de optimización combinatoria cuyo objetivo es llenar un contenedor (de capacidad fija) con cantidades fraccionarias de diferentes materiales elegidos para maximizar el valor de los materiales seleccionados. ^{[ 1 ] [ 2 ]} Es una variación del problema de la mochila clásica , en el que los artículos que se colocan en el contenedor son indivisibles; sin embargo, el problema de la mochila continua puede resolverse en tiempo polinomial, mientras que el problema de la mochila clásica es NP-difícil . ^{[ 1 ]} Es un ejemplo clásico de cómo un cambio aparentemente pequeño en la formulación de un problema puede tener un gran impacto en su complejidad computacional .

Un ejemplo del problema de la mochila, ya sea continuo o clásico, puede especificarse mediante la capacidad numérica W de la mochila, junto con una colección de materiales, cada uno de los cuales tiene dos valores asociados: el peso w _i del material disponible para ser seleccionado y el valor total v _i de dicho material. El objetivo es elegir una cantidad x _i ≤ w _i de cada material, sujeta a la restricción de capacidad. $${\displaystyle \sum _{i}x_{i}\leq W}$$ y maximizar el beneficio total $${\displaystyle \sum _{i}\left({\frac {x_{i}}{w_{i}}}\right)v_{i}.}$$ En el problema clásico de la mochila, cada una de las cantidades x _i debe ser cero o w _i ; el problema continuo de la mochila se diferencia en que permite que x _i varíe continuamente de cero a w _i . ^{[ 1 ]}

Algunas formulaciones de este problema reescalan las variables x _i para que estén en el rango de 0 a 1. En este caso, la restricción de capacidad se convierte en $${\displaystyle \sum _{i}x_{i}w_{i}\leq W,}$$ y el objetivo es maximizar el beneficio total. $${\displaystyle \sum _{i}x_{i}v_{i}.}$$

El problema continuo de la mochila admite una solución voraz publicada por primera vez en 1957 por George Dantzig . ^{[ 3 ] [ 4 ]} A cada material se le asigna la razón${\displaystyle v_{i}/w_{i}}$y luego los materiales se clasifican en orden descendente de esta proporción.

Mientras el peso total de los materiales elegidos sea menor que W , el algoritmo toma la mayor fracción posible del primer elemento de la lista ordenada. Por ejemplo, supongamos que tenemos 4 elementos con pesos${\displaystyle (10,20,20,10)}$, valores${\displaystyle (50,80,60,20)}$y que la capacidad de la mochila es${\displaystyle W=34}$Se calcula la relación valor-peso de cada artículo, lo que da como resultado:${\displaystyle (5,4,3,2)}$. En este caso, los elementos ya están ordenados en orden descendente de proporción. El algoritmo luego toma todos los elementos 1, todos los elementos 2 y${\displaystyle 0.2}$del artículo 3.

Si se utiliza la ordenación basada en comparaciones , este algoritmo se ejecuta en${\displaystyle O(n\log n)}$con respecto a${\displaystyle n}$materiales. ^{[ 1 ] [ 2 ]} Sin embargo, adaptando un algoritmo para encontrar medianas ponderadas , es posible resolver el problema en tiempo${\displaystyle O(n)}$. ^{[ 2 ]}

La prueba de corrección se deduce de un argumento de intercambio estándar. Supongamos que tenemos una solución que no es la solución voraz. Tomemos el primer caso en el que la nueva solución y la solución voraz difieren. Por ejemplo, si la solución voraz toma fracciones${\displaystyle (1,1,0.2,0)}$de 4 elementos (ordenados por la relación valor-peso) y la nueva solución toma fracciones${\displaystyle (1,1,0,0.4)}$Si son los mismos 4 elementos, entonces difieren en la tercera entrada.

En general, la solución voraz toma los pesos de los elementos ordenados por proporción, por lo que asigna mayor peso a los elementos con mayor proporción. Dado que ambas soluciones asignan el mismo peso total a todos los elementos, la nueva solución se ve obligada a asignar peso a los elementos con menor proporción. Por lo tanto, la nueva asignación tiene un valor no mayor que el valor asignado por la solución voraz.