DAA - 0-1 Mochila

En este tutorial, hemos discutido anteriormente el problema de la mochila fraccionada usando el enfoque Greedy. Hemos demostrado que el enfoque codicioso ofrece una solución óptima para la mochila fraccionada. Sin embargo, este capítulo cubrirá el problema de la mochila 0-1 y su análisis.

En 0-1 Mochila, los artículos no se pueden romper, lo que significa que el ladrón debe tomar el artículo como un todo o dejarlo. Esta es la razón detrás de llamarlo 0-1 Mochila.

Por tanto, en el caso de 0-1 Mochila, el valor de x_i pueden ser cualquiera de los dos 0 o 1, donde otras restricciones siguen siendo las mismas.

0-1 Mochila no se puede resolver con un enfoque codicioso. El enfoque codicioso no garantiza una solución óptima. En muchos casos, el enfoque Codicioso puede brindar una solución óptima.

Los siguientes ejemplos establecerán nuestra declaración.

Ejemplo 1

Consideremos que la capacidad de la mochila es W = 25 y los elementos son los que se muestran en la siguiente tabla.

Articulo	UN	segundo	C	re
Lucro	24	18	18	10
Peso	24	10	10	7

Sin considerar la ganancia por unidad de peso (p_i/w_i), si aplicamos el enfoque Greedy para resolver este problema, el primer elemento Aserán seleccionados, ya que contribuirá max _i ganancias madre entre todos los elementos.

Después de seleccionar el artículo A, no se seleccionarán más elementos. Por tanto, para este conjunto dado de elementos, la ganancia total es24. Considerando que, la solución óptima se puede lograr seleccionando elementos,B y C, donde la ganancia total es 18 + 18 = 36.

Ejemplo 2

En lugar de seleccionar los elementos en función del beneficio general, en este ejemplo los elementos se seleccionan en función de la relación p _i / w _i . Consideremos que la capacidad de la mochila es W = 60 y los ítems son los que se muestran en la siguiente tabla.

Articulo	UN	segundo	C
Precio	100	280	120
Peso	10	40	20
Proporción	10	7	6

Usando el enfoque codicioso, primer elemento Aestá seleccionado. Luego, el siguiente elementoBesta elegido. Por tanto, la ganancia total es100 + 280 = 380. Sin embargo, la solución óptima de esta instancia se puede lograr seleccionando elementos,B y C, donde el beneficio total es 280 + 120 = 400.

Por lo tanto, se puede concluir que el enfoque codicioso puede no dar una solución óptima.

Para resolver 0-1 Mochila, se requiere un enfoque de Programación Dinámica.

Planteamiento del problema

Un ladrón está robando una tienda y puede transportar un máximo _i peso del malWen su mochila. Existenn artículos y peso de i^th el artículo es w_i y el beneficio de seleccionar este artículo es p_i. ¿Qué objetos debe llevarse el ladrón?

Enfoque de programación dinámica

Dejar i ser el elemento con el número más alto en una solución óptima S para Wdolares LuegoS^' = S - {i} es una solución óptima para W - w_i dólares y el valor de la solución S es V_i más el valor del subproblema.

Podemos expresar este hecho en la siguiente fórmula: definir c[i, w] ser la solución para los artículos 1,2, … , iy la max _i peso mamáw.

El algoritmo toma las siguientes entradas

El max _i peso mamáW
La cantidad de elementos n
Las dos secuencias v = <v₁, v₂, …, v_n> y w = <w₁, w₂, …, w_n>

Dynamic-0-1-knapsack (v, w, n, W) 
for w = 0 to W do 
   c[0, w] = 0 
for i = 1 to n do 
   c[i, 0] = 0 
   for w = 1 to W do 
      if w_i ≤ w then 
         if v_i + c[i-1, w-w_i] then 
            c[i, w] = v_i + c[i-1, w-w_i] 
         else c[i, w] = c[i-1, w] 
      else 
         c[i, w] = c[i-1, w]

El conjunto de elementos a llevar se puede deducir de la tabla, comenzando en c[n, w] y rastrear hacia atrás de dónde provienen los valores óptimos.

Si c [i, w] = c [i-1, w] , entonces el elementoi no es parte de la solución, y seguimos rastreando con c[i-1, w]. De lo contrario, artículoi es parte de la solución, y seguimos rastreando con c[i-1, w-W].

Análisis

Este algoritmo toma θ ( n , w ) veces, ya que la tabla c tiene ( n + 1). ( W + 1) entradas, donde cada entrada requiere θ (1) tiempo para calcular.

↰ Previous page Next page ↱