DAA - Mochila fraccionada

El algoritmo Greedy podría entenderse muy bien con un problema bien conocido denominado problema de mochila. Aunque el mismo problema podría resolverse empleando otros enfoques algorítmicos, el enfoque codicioso resuelve el problema de la mochila fraccionada razonablemente en un buen momento. Discutamos el problema de la mochila en detalle.

Problema de la mochila

Dado un conjunto de elementos, cada uno con un peso y un valor, determine un subconjunto de elementos para incluir en una colección de modo que el peso total sea menor o igual a un límite dado y el valor total sea lo más grande posible.

El problema de la mochila está en el problema de la optimización combinatoria. Aparece como un subproblema en muchos modelos matemáticos más complejos de problemas del mundo real. Un enfoque general para los problemas difíciles es identificar la restricción más restrictiva, ignorar las otras, resolver un problema de mochila y, de alguna manera, ajustar la solución para satisfacer las restricciones ignoradas.

Aplicaciones

En muchos casos de asignación de recursos junto con alguna restricción, el problema puede derivarse de una manera similar al problema de la mochila. A continuación se muestra un conjunto de ejemplos.

• Encontrar la forma menos derrochadora de cortar materias primas
• optimización de cartera
• Problemas de stock de corte

Escenario de problemas

Un ladrón está robando una tienda y puede llevar un peso máximo de Wen su mochila. Hay n artículos disponibles en la tienda y el peso dei^th el artículo es w_i y su beneficio es p_i. ¿Qué objetos debe llevarse el ladrón?

En este contexto, los artículos deben seleccionarse de tal manera que el ladrón lleve aquellos artículos por los que obtendrá el máximo beneficio. Por tanto, el objetivo del ladrón es maximizar la ganancia.

Según la naturaleza de los elementos, los problemas de mochila se clasifican como

• Mochila fraccionada
• Knapsack

Mochila fraccionada

En este caso, los artículos se pueden romper en pedazos más pequeños, por lo que el ladrón puede seleccionar fracciones de artículos.

Según el planteamiento del problema,

• Existen n artículos en la tienda

• Peso de i^th artículo $ w_ {i}> 0 $

• Beneficio para i^th artículo $ p_ {i}> 0 $ y

• La capacidad de la mochila es W

En esta versión del problema de la mochila, los artículos se pueden romper en pedazos más pequeños. Entonces, el ladrón puede tomar solo una fracciónx_i de i^th articulo.

$$ 0 \ leqslant x_ {i} \ leqslant 1 $$

los i^th artículo aporta el peso $ x_ {i} .w_ {i} $ al peso total en la mochila y el beneficio $ x_ {i} .p_ {i} $ al beneficio total.

Por tanto, el objetivo de este algoritmo es

$$ maximizar \: \ estilo de visualización \ suma \ límites_ {n = 1} ^ n (x_ {i} .p _ {} i) $$

sujeto a restricciones,

$$ \ Displaystyle \ sum \ límites_ {n = 1} ^ n (x_ {i} .w _ {} i) \ leqslant W $$

Está claro que una solución óptima debe llenar la mochila exactamente, de lo contrario podríamos agregar una fracción de uno de los elementos restantes y aumentar la ganancia general.

Por tanto, se puede obtener una solución óptima

$$ \ Displaystyle \ sum \ límites_ {n = 1} ^ n (x_ {i} .w _ {} i) = W $$

En este contexto, primero debemos ordenar esos elementos de acuerdo con el valor de $ \ frac {p_ {i}} {w_ {i}} $, de modo que $ \ frac {p_ {i} +1} {w_ {i } +1} $ ≤ $ \ frac {p_ {i}} {w_ {i}} $. Aquí,x es una matriz para almacenar la fracción de elementos.

Algorithm: Greedy-Fractional-Knapsack (w[1..n], p[1..n], W) 
for i = 1 to n 
   do x[i] = 0 
weight = 0 
for i = 1 to n 
   if weight + w[i] ≤ W then  
      x[i] = 1 
      weight = weight + w[i] 
   else 
      x[i] = (W - weight) / w[i] 
      weight = W 
      break 
return x

Análisis

Si los elementos proporcionados ya están ordenados en orden decreciente de $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $, el whileloop tarda un tiempo en O(n); Por lo tanto, el tiempo total que incluye la ordenación está enO(n logn).

Ejemplo

Consideremos que la capacidad de la mochila W = 60 y la lista de elementos proporcionados se muestran en la siguiente tabla:

Articulo	UN	segundo	C	re
Lucro	280	100	120	120
Peso	40	10	20	24
Proporción $ (\ frac {p_ {i}} {w_ {i}}) $	7	10	6	5

Como los elementos proporcionados no se ordenan en función de $ \ mathbf {\ frac {p_ {i}} {w_ {i}}} $. Después de ordenar, los elementos se muestran en la siguiente tabla.

Articulo	segundo	UN	C	re
Lucro	100	280	120	120
Peso	10	40	20	24
Proporción $ (\ frac {p_ {i}} {w_ {i}}) $	10	7	6	5

Solución

Después de ordenar todos los elementos según $ \ frac {p_ {i}} {w_ {i}} $. Primero todo deB se elige como peso de Bes menor que la capacidad de la mochila. Proximo articuloA se elige, ya que la capacidad disponible de la mochila es mayor que el peso de A. Ahora,Cse elige como el siguiente elemento. Sin embargo, no se puede elegir todo el artículo ya que la capacidad restante de la mochila es menor que el peso deC.

Por tanto, fracción de C (es decir, (60 - 50) / 20) se elige.

Ahora, la capacidad de la mochila es igual a los elementos seleccionados. Por tanto, no se pueden seleccionar más elementos.

El peso total de los elementos seleccionados es 10 + 40 + 20 * (10/20) = 60

Y la ganancia total es 100 + 280 + 120 * (10/20) = 380 + 60 = 440

Ésta es la solución óptima. No podemos obtener más ganancias seleccionando una combinación diferente de artículos.