Problema continuo de la mochila

En informática teórica, el problema continuo de la mochila (también conocido como problema fraccional de la mochila) es un problema algorítmico de optimización combinatoria en el que el objetivo es llenar un contenedor (la "mochila") con cantidades fraccionarias de diferentes materiales elegidos para maximizar el valor de los materiales seleccionados. Se parece al problema clásico de la mochila, en el que los elementos que se colocan en el contenedor son indivisibles; sin embargo, el problema continuo de la mochila se puede resolver en tiempo polinómico, mientras que el problema clásico de la mochila es NP-hard. 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.

Una instancia de los problemas de knapsack continuos o clásicos puede ser especificada por la capacidad numérica W de la mochila, junto con una colección de materiales, cada uno de los cuales tiene dos números asociados con ella: el peso w_i de material disponible para ser seleccionado y el valor total v_i de ese material. El objetivo es elegir una cantidad x_i ≤ w_i de cada material, sujeto a la limitación de la capacidad $${\displaystyle \sum _{i}x_{i}\leq W.$$y maximización del beneficio total $${\displaystyle \sum _{i}x_{i}v_{i}$$En el problema de la mochila clásica, cada una de las cantidades x_i debe ser cero o w_i; el problema de knapsack continuo difiere permitiendo x_i para variar continuamente de cero a w_i.

Algunas formulaciones de este problema reescalan las variables x_i a estar en el rango de 0 a 1. En este caso, la limitación de la capacidad se convierte en $${\displaystyle \sum ¿Por qué? W,}$$y el objetivo es maximizar el beneficio total $${\displaystyle \sum _{i}x_{i}v_{i}$$

El problema de la mochila continua se puede resolver mediante un algoritmo voraz, publicado por primera vez en 1957 por George Dantzig, que considera los materiales en orden ordenado por sus valores por unidad de peso. Para cada material, se elige la cantidad x_i lo más grande posible:

• Si la suma de las decisiones adoptadas hasta ahora es igual a la capacidad W, entonces el algoritmo establece x_i = 0.
• Si la diferencia d entre la suma de las decisiones adoptadas hasta ahora W es más pequeño que w_i, entonces el algoritmo establece x_i = d.
• En el caso restante, el algoritmo elige x_i = w_i.

Debido a la necesidad de ordenar los materiales, este algoritmo requiere un tiempo O(n log n) en entradas con n materiales. Sin embargo, al adaptar un algoritmo para encontrar medianas ponderadas, es posible resolver el problema en un tiempo O(n).