Problema de la mochila

Análisis comparativo de la solución del Problema de la Mochila 0-1
mediante un algoritmo de fuerza bruta y un algoritmo voraz
Osvaldo Escobar Díaz
En la Figura 1 observamos un ejemplo delproblema a resolver, donde la mochila tiene una
capacidad de 15 kg. Se deben ingresar a la
mochila los objetos que maximicen el beneficio
(objetos que valen más en pesos “$”) sin rebasar
la capacidad dela mochila.

El problema de la mochila (knapsack problem
en inglés) es un problema típico que se resuelve
mediante un algoritmo de tipo combinatorio
(busca la mejor solución entre un conjunto deposibles soluciones a un problema).
Este 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.

Para cuando este problema tiene muchos objetos
a ingresara una mochila, el problema tiene
muchas combinaciones, siendo que entre más
objetos, su tamaño de combinaciones crece
exponencialmente. Esto porque el problema de la
mochila se resuelve evaluandolas combinaciones
de objetos tomando en cuenta si cada objeto está
o no está en dicha combinación, que se traduce en
si el objeto será añadido o no a la mochila,
respectivamente. Entonces lascombinaciones
pueden representarse por cadenas de caracteres de
0’s y 1’s, donde el 0 representa que el objeto no
forma parte de la combinación y el 1 que si forma
parte de la combinación, porejemplo, si existe
una combinación de 8 objetos a lo más que
deberán ingresarse a una mochila, la cadena de
caracteres 01101011 nos dice que si enumeramos
los 8 objetos, el objeto 1 no será añadido, elobjeto
2 será añadido, el objeto 3 será añadido, el objeto
4 no será añadido, etc. Otra combinación podría
ser 00000000, que representa que ningún objeto
será añadido, o 11111111 representa la...