Problema de la mochila o knapsack problem

Funcionamiento del problema de la mochila

1. A lgoritmos Voraces Problema de la Mochila M.C.C. Jessica Elena González San Martín

2. Problema de la mochila Este problema consiste en: Dada una mochila que soporta un peso máximo . Se tienen objetos con un peso , y un valor para . Llenar la mochila con los objetos que maximicen el valor total y sin sobrepasar su capacidad de carga.  

3. Problema de la mochila fraccionada Este problema consiste en: Dada una mochila que soporta un peso máximo . Se tienen objetos con un peso , y un valor para . Llenar la mochila con los objetos que maximicen el valor total y sin sobrepasar su capacidad de carga. Los objetos se pueden fraccionar en trozos pequeños (como: líquidos, arena kinética , paquete de monedas).   w 1 =10 v 1 =60 w 2 =20 v 2 =100 w 3 =30 v 3 =120 Mochila fraccionada ( ejemplo ) Capacidad W =50 Seleccionar A, B y 2/3 de C Peso total = 10+20+30*2/3=50 Valor total = 60+100+120*2/3=240 completo completo 2/3

4. Problema de la mochila fraccionada Los objetos se pueden fraccionar en trozos pequeños . Al multiplicar por una fracción , de tal manera que cada objeto contribuye: al peso total de la mochila y en el valor total de la carga. Por ejemplo: Si =1 el objeto va en la mochila; si =0 el objeto no va en la mochila; si =1/2 va la mitad del objeto.   w 1 =10 v 1 =60 w 2 =20 v 2 =100 w 3 =30 v 3 =120 Mochila fraccionada ( ejemplo ) Capacidad W =50 Seleccionar A, B y 2/3 de C Peso total = 10+20+30*2/3=50 Valor total = 60+100+120*2/3=240 completo completo 2/3

5. Problema de la mochila fraccionada Función objetivo: maximizar valor total Restricciones: capacidad y fracciones de objetos Sujeto a : Donde: Solución: ; en se asignan objetos a la mochila Mochila llena:  

6. Alternativas de solución voraz Heurísticas voraces H1 : seleccionar el objeto más ligero H2 : Seleccionar el objeto más valioso H3 : Seleccionar el objeto con mayor relación valor/peso

7. Ejemplo 1: Resolver el problema de la mochila fraccionada con las diferentes heurísticas voraces, considerando y   ¿Cuál es la mejor estrategia? Objetos   1 2 3 4 5 Pesos 10 20 30 40 50 Valores 20 30 66 40 60 Valor/peso 2 1.5 2.2 1.0 1.2 Objeto Peso Acumulado Valor Acumulado x =[0,0,0,0,0] 1 10 (10+0) 20 (20+0) x[1]= 1 2 30 (20+10) 50 (30+20) x[2]= 1 3 60 (30+30) 116 (66+50) x[3]= 1 4 100 (40+60) 156 (40+116) x[4]= 1 Peso Acumulado Valor Acumulado x =[0,0,0,0,0] 1 10 (10+0) 20 (20+0) x[1]= 1 2 30 (20+10) 50 (30+20) x[2]= 1 3 60 (30+30) 116 (66+50) x[3]= 1 4 100 (40+60) 156 (40+116) x[4]= 1 H1: seleccionar el objeto más ligero Solución:  

8. Ejemplo 1: Resolver el problema de la mochila fraccionada con las diferentes heurísticas voraces, considerando y   ¿Cuál es la mejor estrategia? Objetos   1 2 3 4 5 Pesos 10 20 30 40 50 Valores 20 30 66 40 60 Valor/peso 2 1.5 2.2 1.0 1.2 Objeto Peso Acumulado Valor Acumulado 3 30 (30+0) 66 (66+0) 1 5 80 (50+30) 126 (60+66) 1 4 100 (*20+80) 146 (20+126) 0.5 Peso Acumulado Valor Acumulado 3 30 (30+0) 66 (66+0) 1 5 80 (50+30) 126 (60+66) 1 4 100 (*20+80) 146 (20+126) 0.5 H2: seleccionar el objeto más valioso  Se toma s olo la mitad parar llegar a 100 Solución:    

9. Ejemplo 1: Resolver el problema de la mochila con las diferentes heurísticas voraces, considerando y   ¿Cuál es la mejor estrategia? Objetos   1 2 3 4 5 Pesos 10 20 30 40 50 Valores 20 30 66 40 60 Valor/peso 2 1.5 2.2 1.0 1.2 Objeto Peso Acumulado Valor Acumulado 3 30 66 1 1 40 86 1 2 60 116 1 5 100 164 0.8 Peso Acumulado Valor Acumulado 3 30 66 1 1 40 86 1 2 60 116 1 5 100 164 0.8 H3: Seleccionar objeto con mayor valor/peso Solución:   H3 mejor que H1 mejor que H2  

10. Ejemplo 2: Resolver el problema de la mochila fraccionada con las diferentes estrategias. Considere .   ¿Cuál es la mejor estrategia? Objetos  i 1 2 3 4 5 Peso 50 100 150 200 250 Valores 20 24 55 40 70 Valor/peso 0.40 0.24 0.33 0.20 0.28 H1: seleccionar el objeto más ligero Solución:   Objeto Peso Acumulado Valor Acumulado 1 50 20 1 2 150 44 1 3 300 99 1 4 500 139 1 5 600 167 0.4 Peso Acumulado Valor Acumulado 1 50 20 1 2 150 44 1 3 300 99 1 4 500 139 1 5 600 167 0.4

11. Ejemplo 2: Resolver el problema de la mochila fraccionada con las diferentes estrategias. Considere .   ¿Cuál es la mejor estrategia? H2: seleccionar el objeto más valioso Objeto Peso Ac. Valor Ac. 5 250 70 1 3 400 125 1 4 600 165 1 Peso Ac. Valor Ac. 5 250 70 1 3 400 125 1 4 600 165 1 Solución:   Objetos  i 1 2 3 4 5 Peso 50 100 150 200 250 Valores 20 24 55 40 70 Valor/peso 0.40 0.24 0.33 0.20 0.28

12. Ejemplo 2: Resolver el problema de la mochila fraccionada con las diferentes estrategias. Considere .   ¿Cuál es la mejor estrategia? H3: Seleccionar objeto con mayor valor/peso Solución:   Objeto Peso Ac. Valor Ac. 1 50 20 1 3 200 75 1 5 450 145 1 2 550 169 1 4 600 179 0.25 Peso Ac. Valor Ac. 1 50 20 1 3 200 75 1 5 450 145 1 2 550 169 1 4 600 179 0.25 Objetos  i 1 2 3 4 5 Peso 50 100 150 200 250 Valores 20 24 55 40 70 Valor/peso 0.40 0.24 0.33 0.20 0.28 H3 mejor que H1 mejor que H2

13. Algoritmo mochilaVoraz Entrada: Salida: vector de objetos seleccionados 1   2   Para hasta 3     4   Mientras //repite si caben objetos 5     6     Si //objeto completo 7       8       9   Si no //fracción del objeto 10       11       //asegura terminación del ciclo 12   Regresar 1 2   3     4   5     6     7       8       9   Si no //fracción del objeto 10       11       12   Selección voraz ( h,x,pesos,valores ) h =1 : seleccionar el objeto más ligero h =2 : Seleccionar el objeto más valioso h =3 : Seleccionar el objeto con mayor relación valor/peso

14. Algoritmo mochilaVoraz H3: Seleccionar objeto con mayor valor/peso Solución:   ENTRADA:   Objetos   1 2 3 4 5 Pesos 10 20 30 40 50 Valores 20 30 66 40 60 Valor/peso 2 1.5 2.2 1.0 1.2 Objeto seleccionado Peso Acumulado sumap Valor Acumulado x =[0.0…] 3 30 66 x [3]=1 1 40 86 x [1]=1 2 60 116 x [2]=1 5 100 164 x [5]= 0.8 Peso Acumulado sumap Valor Acumulado x =[0.0…] 3 30 66 x [3]=1 1 40 86 x [1]=1 2 60 116 x [2]=1 5 100 164 x [5]= 0.8 Entrada: Salida: vector de objetos seleccionados 1   2   Para hasta 3     4   Mientras //repite si caben objetos 5     6     Si //objeto completo 7       8   9   Si no //fracción del objeto 10       11       //asegura terminación del ciclo 12   Regresar 1 2   3     4   5     6     7       8   9   Si no //fracción del objeto 10       11       12