problema de la mochila ejemplo

Algoritmos Genéticos (AG)


Práctico Nº 1: Problema de la Mochila


Consiste en elegir, de entre un conjunto de n elementos de un negocio, (cada uno con un valor vi , y un peso pi ), aquellosque puedan ser cargados en la mochila de un individuo, que decide hacer una visita nocturna al negocio. La mochila resiste un peso máximo P y se debe tener en cuenta que el visitante pretendeacumular el mayor valor posible, entre todos los objetos que recoge.


Este es un claro ejemplo de la presentación de un problema, en el que hay dificultad para hallar una solución óptima exacta,principalmente por el tiempo que llevaría recorrer y combinar todas las posibilidades en forma exhaustiva.

Para 20 elementos  se definen 220=1.048.580 subconjuntos o soluciones
Para 60 elementos  senecesitan 365 siglos para resolver el problema, a 1 millón de soluciones por segundo


Existen entonces, métodos heurísticos que proporcionan soluciones factibles (que satisfacen las restriccionesdel problema), que aunque no optimicen la función objetivo, se acercan al valor óptimo en un tiempo de cálculo razonable.
Una clase de algoritmos heurísticos son los métodos constructivos, queconsisten en ir agregando componentes individuales a la solución hasta que se obtiene una solución factible.
Un representante de éstos son los algoritmos greedy (golosos o devoradores). Estos algoritmosvan construyendo paso a paso la solución, buscando el máximo beneficio en cada paso.
En el problema de la mochila, debemos ir escogiendo los elementos que aporten el mayor valor en proporción a supeso ( vi / pi ).








Ejercicios

1. Desarrollar un algoritmo goloso que brinde una solución para el siguiente conjunto de datos:

Objeto
Peso (grs.)
Valor ($)
1
150
20
2
32540
3
600
50
4
805
36
5
430
25
6
1200
64
7
770
54
8
60
18
9
930
46
10
353
28



2. Dados 3 elementos, cuyos pesos son: 1800 grs., 600 grs. Y 1200 grs. y cuyos valores son:...