Mochila fraccionada en tiempo lineal

Sería bueno si dijera el problema. Supongo que tiene $ n $ elementos $ x_i $ , cada uno con ganancias $ p_i $ y peso $ w_i $ . Desea maximizar sus ganancias con la restricción de que el peso total sea como máximo $ W $ . Para cada elemento $ x_i $ , puedes poner cualquier fracción $ \ theta \ en [0,1] $ de él, lo que le dará ganancias $ \ theta p_i $ y peso $ \ theta w_i $ .

Aquí hay un ejemplo. Tiene oro en bruto, con una ganancia de $ 1000 $ y un peso $ 1 $ . También tienes plátanos, con una ganancia de $ 1 $ y un peso $ 10 $ . Suponga que puede llevar un peso de $ 2 $ . ¿Qué harías? Naturalmente, primero colocaría todo el oro que pueda, es decir, todo, y luego colocará tantos plátanos como pueda, es decir, una décima parte, para obtener una ganancia total de $ 1000.1 $ .

El algoritmo general es similar. Suponga que divide $ W $ en $ 1000 $ «espacios», que desea llenar con la mayor cantidad elementos rentables de peso $ W / 1000 $ . Para un artículo que pesa $ w_i $ , tenemos $ w_i / (W / 1000) $ piezas (supongamos por el momento que sea un número entero), y cada uno de ellos vale $ p_i / (w_i / (W / 1000)) $ . Al elegir qué poner en una ranura, nos gustaría maximizar nuestras ganancias, por lo que elegimos el artículo con el máximo $ p_i / w_i $ y lo colocamos como tantos piezas como sea posible. Si nos quedamos sin, elegimos el elemento con el siguiente $ p_i / w_i $ más grande, y así sucesivamente.

Puede implementar esto sin dividir $ W $ en un $ 1000 $ piezas: elija el elemento con $ p_i / w_i $ y coloque la mayor cantidad posible. Si se acaba, elija el siguiente y ponga la mayor cantidad posible. Etcétera. La implementación de este algoritmo requiere ordenar la lista $ p_i / w_i $ , lo que lleva tiempo $ O (n \ log n) $ . El algoritmo que describe utiliza el mismo truco en la selección rápida para reducir el tiempo de ejecución a $ O (n) $ , a costa de hacer que el algoritmo sea aleatorio.

Sugiero la siguiente ruta para comprender el algoritmo:

1. Comprender el algoritmo codicioso clásico para la mochila fraccionada.
2. Comprender la selección rápida.
3. Vea cómo el algoritmo que cita combina la técnica de selección rápida con el enfoque codicioso.

R es el conjunto de relaciones de beneficio / peso de cada objeto , donde se dan el beneficio y el peso de los objetos. Y W es la Capacidad de la mochila .
Ahora, en lugar de elegir un elemento aleatorio en un paso, podemos aplicar el algoritmo de búsqueda de la mediana a encuentra la mediana en O (n) veces.
Y luego podemos hacer el resto de todos los pasos.Por tanto, el análisis de la complejidad del tiempo será:
        T (n) = T (n / 2) + O (n).
Y obtendremos O (n) como solución. Dime si algo no está explicado correctamente y quieres saber algo más.

En tiempo lineal, puedes encontrar el artículo mediano en términos de valor por unidad de peso. Luego, también en tiempo lineal, puede averiguar si puede colocar todos los elementos que son al menos tan valiosos en la mochila o no. Si puede, hágalo y resuelva de forma recursiva este problema para los n / 2 elementos de menor valor dado que » ya llenó la mochila. Si no puede, puede tirar los n / 2 artículos de menor valor, y luego intente resolver el problema nuevamente con solo los n / 2 elementos de mayor valor.

La recurrencia aquí es T (n) = T (n / 2) + O (n) , y tenemos que T (n) = O (n) , como se desee.

En la solución que ha pegado: R es el conjunto de relaciones, beneficio / peso W es la suma del peso total de este conjunto , utilizado para comparar con la capacidad de su mochila. De manera similar, {pi / wi | pi / wi} representa el i-ésimo elemento que la ganancia está al i-ésimo valor de peso. Estamos comparando este valor con el valor r seleccionado al azar y luego lo segregamos según la comparación de la proporción. Los R1, R2, R3 son otros subconjuntos del conjunto de proporciones en función de que la proporción sea menor, igual o mayor que la de el elemento mediano.

De manera similar, W1, W2, W3 son la suma de los pesos de estos conjuntos.

Ahora elija el conjunto de solución adecuado en función de los valores de proporción como se explica al principio.