Resolución del problema de la mochila en varias estrategias, algoritmos voraces

Resolución del problema de la mochila en varias estrategias, algoritmos voraces

En algoritmia, el problema de la mochila, comúnmente abreviado por KP (del inglés Knapsack problem) es un problema de optimización combinatoria, es decir, que busca la mejor solución entre un conjunto de posibles soluciones a un problema. Modela una situación análoga al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de un conjunto de objetos, cada uno con un peso y valor específicos. Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso máximo

Estrategias para resolverlo, llenar la mochila:
1) Con los elementos más costosos
2) Con los elementos menos pesados
3) Con los elementos que tenga mayor beneficio por unidad de peso ( coeficiente entre valor y peso)
4) Algoritmo Backtracking (o vuelta atrás):

     Es  un recorrido en profundidad dentro de un grafo dirigido. El grafo en cuestión suele ser un árbol. El objetivo del recorrido es encontrar soluciones para algún problema. Esto se consigue construyendo soluciones parciales a medida que progresa el recorrido; estas soluciones parciales limitan las regiones en las que se puede encontrar una solución completa. El recorrido tiene éxito si, procediendo de esta forma, se puede definir por completo una solución. En este caso el algoritmo puede, o bien detenerse (si lo único que se necesita es una solución del problema) o bien seguir buscando soluciones alternativas (si deseamos examinarlas todas). Por otra parte, el recorrido no tiene éxito si en alguna etapa la solución parcial construida hasta el momento no se puede completar. En tal caso, el recorrido vuelve atrás exactamente igual que en un recorrido en profundidad, eliminando sobre la marcha los elementos que se hubieran añadido en cada fase. Cuando vuelve a un nodo que tiene uno o más vecinos sin explorar, prosigue el recorrido de una solución.

A continuación, este problema resueldo aplicando las distintas estrategias, usando Gambas3
Estructura del Proyecto:

Clase Elemento:
--


Clase ProblemaMochila:
--

Programa Principal:
-
-


Resultados:

.......................................
Estrategia: mayor_valor
Nombre: TV Valor:300 Peso:15
Nombre: VideoBeam Valor:200 Peso:4
Nombre: ipod Valor:150 Peso:1
-------------
Peso:   20
Valor:  650
.......................................
Estrategia: menos_peso
Nombre: DVD Valor:5 Peso:0.5
Nombre: Blu-Ray Valor:50 Peso:0.5
Nombre: Balon Valor:30 Peso:0.5
Nombre: BlackBerry Valor:150 Peso:0.5
Nombre: Libro Java Valor:10 Peso:1
Nombre: ipod Valor:150 Peso:1
Nombre: ipad Valor:150 Peso:2
Nombre: PS3 Valor:100 Peso:3
Nombre: Laptop Valor:20 Peso:3
Nombre: Printer Valor:20 Peso:4
Nombre: VideoBeam Valor:200 Peso:4
-------------
Peso:   18
Valor:  885
.......................................
Estrategia: coeficiente_valor/peso
Nombre: BlackBerry Valor:150 Peso:0.5
Nombre: ipod Valor:150 Peso:1
Nombre: Blu-Ray Valor:50 Peso:0.5
Nombre: ipad Valor:150 Peso:2
Nombre: Balon Valor:30 Peso:0.5
Nombre: VideoBeam Valor:200 Peso:4
Nombre: PS3 Valor:100 Peso:3
Nombre: PC Valor:100 Peso:5
Nombre: Libro Java Valor:10 Peso:1
Nombre: DVD Valor:5 Peso:0.5
-------------
Peso:   16
Valor:  945
.......................................
Algoritmo Backtracking
Nombre: VideoBeam Valor:200 Peso:4
Nombre: ipod Valor:150 Peso:1
Nombre: ipad Valor:150 Peso:2
Nombre: BlackBerry Valor:150 Peso:0.5
Nombre: PS3 Valor:100 Peso:3
Nombre: PC Valor:100 Peso:5
Nombre: Blu-Ray Valor:50 Peso:0.5
Nombre: Balon Valor:30 Peso:0.5
Nombre: Laptop Valor:20 Peso:3
Nombre: DVD Valor:5 Peso:0.5
-------------
Peso:   18
Valor:  955

Enlace de descarga del código fuente: enlace a box.com

Fuentes:

http://es.wikipedia.org/wiki/Problema_de_la_mochila
http://es.wikipedia.org/wiki/Vuelta_atr%C3%A1s
http://cala.unex.es/cala/epistemowikia/index.php?title=Backtracking
http://jorgep.blogspot.com.es/2010/11/problema-de-la-mochila.html
http://jorgep.blogspot.com.es/2010/11/problema-de-la-mochila-algoritmos.html
http://jorgep.blogspot.com.es/2010/11/problema-de-la-mochila-backtracking.html