## 2.2.4 EL PROBLEMA DE LA MOCHILA ENTERA

El Problema de la Mochila (conocido también como Knapsack Problem o simplemente KP) es un problema clásico de la Investigación de Operaciones y en particular de la Programación Entera. Consiste en un excursionista que debe preparar su mochila, la cual tiene una capacidad limitada y por tanto no le permite llevar todos los artículos que quisiera tener en la excursión.

Cada artículo que el excursionista puede incluir en la mochila le reporta una determinada utilidad. Luego el problema consiste en seleccionar un subconjunto de objetos de forma tal que se maximice la utilidad que el excursionista obtiene, pero sin sobrepasar la capacidad de acarrear objetos.

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 por Richard Karp en 1972.

Tenemos un conjunto S de n objetos, en el que cada objeto i tiene un beneficio objeto i tiene un beneficio bi y un peso wi positivos.

Objetivo: Seleccionar los elementos que nos garantizan un beneficio máximo pero con un peso global menor o igual que W.

Dado el conjunto S de n objetos, sea Sk el conjunto de los k primeros objetos (de 1 a k): Podemos definir B[k,w] como la ganancia de la mejor solución obtenida a partir de los elementos de Sk para una mochila de capacidad w. Ahora bien, la mejor selección de elementos del conjunto conjunto Sk para una mochila de tamaño w se puede definir en función de selecciones de elementos de Sk-1 para mochilas de menor capacidad.

¿Cómo calculamos B? ¿Cómo calculamos B[k,w]? O bien la mejor opción para Sk coincide con la mejor selección de elementos de Sk-1 con peso máximo w (el beneficio máximo para Sk coincide con el de Sk-1 (el beneficio máximo para S ), k coincide con el de Sk-1, o bien es es el resultado de añadir el objeto k a la mejor selección de elementos de Sk-1 con peso máximo w−wk (el beneficio para Sk será el beneficio que se obtenía en Sk-1 para una mochila de w−wk más el beneficio bk asociado al objeto k).

Definición recursiva de B[k,w]:

B[k,w] = B[k-1,w] si xk=0;

B[k-1,w-wk] + bk si xk=1.

Para resolver el problema de la mochila nos quedaremos con el máximo de ambos valores:

B[k,w] = máx {B[k-1,w],B[k-1,w-wk] + bk

Cálculo ascendente de B ( Cálculo ascendente de B(k,w) usando una matriz B de tamaño (n+1) x (W+1):

int[][] knapsack (W, w[1..n], b[1..n])

{

for (p=0; p<=W; p++)

B[0][p]=0;

for (k=1; k<=n; k++) {

(k=1; k<=n; k++) {

for (p=0; p<=W; w++) (p=w[k]; p<=W; w++)

B[k][p] = B[k][p] = max ( B[k-1][p−w[k]]+b[k], B[k 1][p−w[k]]+b[k], B[k-1][p] ); 1][p] );

}

return B;

}

¿Cómo calculamos la solución óptima a partir de B(k,w)?

Calculamos la solución para B[k][w] utilizando el siguiente algoritmo:

Si B[k][w] == B[k-1][w],

entonces el objeto k no se selecciona y se seleccionan los objetos correspondientes

a la solución óptima para k-1 objetos y una mochila de capacidad w: 1 objetos y una

mochila de capacidad w: la solución para B[k la solución para B[k-1][w].

Si B[k][w] != B[k Si B[k][w] != B[k-1][w], se selecciona el objeto k y

los objetos correspondientes a la solución óptima para k-1 objetos y una

mochila de capacidad w 1 objetos y una mochila de capacidad w-w[k]:

la solución para B[k la solución para B[k-1][w-w[k]].

Eficiencia del algoritmo

Tiempo de ejecución: Θ(n W) “Pseudopolinómico” (no es polinómico sobre el tamaño de la entrada entrada; esto es, sobre el número de objetos objetos).

###