Problema de la Mochila

PROBLEMA DE LA MOCHILA
(KNAPSACK PROBLEM)

1. INTRODUCCIÓN

El problema de la mochila es un problema simple de entender: hay una persona que tiene una mochila con una cierta capacidad y tiene que elegir qué elementos pondrá en ella. Cada uno de los elementos tiene un peso y aporta un beneficio. El objetivo de la persona es elegir los elementos que le permitan maximizar el beneficio sinexcederse de la capacidad permitida.
A la vez es un problema complejo, si por complejidad nos referimos a la computacional. “Un problema se cataloga como inherentemente difícil si su solución requiere de una cantidad significativa de recursos computacionales, sin importar el algoritmo utilizado.” El problema de la mochila forma parte de una lista histórica de problemas NP − Completos elaborada porRichard Karp en 1972.
En el caso del problema de la mochila, si contáramos con 4 productos, para saber cuál es la mejor solución podríamos probar las 24 = 16 posibilidades. El 2 se desprende del hecho de que cada decisión es incluir o no al producto y el 4 de la cantidad de productos. 16 posibilidades es un número manejable, sin embargo, si la cantidad de elementos por ejemplo ascendiera a 20,tendríamos que analizar nada más y nada menos que 220 = 1,048,576 posibilidades.

2. DEFINICIÓN FORMAL DEL PROBLEMA

Supongamos que tenemos n distintos tipos de ítems, que van del 1 al n. De cada tipo de ítem se tienen qi ítems disponibles, donde qi es un entero positivo que cumple:
Cada tipo de ítem i tiene un beneficio asociado dado por vi y un peso (o volumen) wi. Usualmente se asume que elbeneficio y el peso no son negativos. Para simplificar la representación, se suele asumir que los ítems están listados en orden creciente según el peso (o volumen).
Por otro lado se tiene una mochila, donde se pueden introducir los ítems, que soporta un peso máximo (o volumen máximo) W.
El problema consiste en meter en la mochila ítems de tal forma que se maximice el valor de los ítems que contieney siempre que no se supere el peso máximo que puede soportar la misma. La solución al problema vendrá dado por la secuencia de variables x1, x2, ..., xn donde el valor de xi indica cuantas copias se meterán en la mochila del tipo de ítem i.
El problema se puede expresar matemáticamente por medio del siguiente programa lineal:
Maximizar
Tal que
Y
Si  para i=1,2,...,n se dice que setrata del problema de la mochilla 0-1. Si uno o más  es infinito entonces se dice que se trata del problema de la mochila no acotado también llamado a veces problema de la mochila entera. En otro caso se dice que se trata del problema de la mochila acotado.

3. ALGORITMO (PARADIGMA: DIVIDE AND CONQUER)

Para que el algoritmo propuesto funcione correctamente los elementos a insertar en la mochilase han de ordenar en función de la relación peso/beneficio:


El Quicksort trabaja particionando el conjunto a ordenar en dos partes, para después ordenar dichas partes independientemente. El punto clave del algoritmo está en el procedimiento que divide el conjunto. El proceso de división del conjunto debe cumplir las siguientes tres condiciones:

a. El elemento pivote=a[i] está en suposición final en el array para algún índice i.
b. Todos los elementos en a[first], ..., a[i-1] son menores o iguales a a[i].
c. Todos los elementos en a[i+1], ..., a[last] son mayores que a[i].
En este punto se aplica el mismo método recursivamente a los dos subproblemas generados: a[first], ... , a[i-1] y a[i+1], ... , a[last]. El resultado final será una matriz completamente ordenada, y portanto no hace falta un paso subsiguiente de combinación.
4. EL ALGORITMO

A. ANÁLISIS DEL PROBLEMA

Para el análisis tomaremos un caso en particular.
Sea el conjunto de elementos (6) con las siguientes características:


0
1
2
3
4
5
VALOR
50
40
30
66
20
60
PESO
60
40
20
30
10
50

Y una mochila con capacidad de 100.

a. VORAZ SIN ORDENAMIENTO

Si tomamos los...