Siguiente: Implementación de FANS Anterior: Ejemplos de Aplicación Arriba: Ejemplos de Aplicación

Mochila Clásica

El problema de la mochila se formula de la siguiente manera:

$$\sum\limits_{j=1}^{n} p_j * x_j$$ (5)

$$\sum\limits_{j=1}^{n} w_j * x_j \leq C, x_j \in \{0,1\}, j=1,\ldots,n$$

donde $n$ es el número de items, $x_j$ indica si el ítem $j$ está incluido o no en la mochila, $p_j$ es el beneficio asociado al ítem $j$, $w_j \in [0,\ldots,r]$ es el peso del ítem $j$, y $C$ es la capacidad de la mochila. Además, se asume que cada ítem cabe en la mochila ( $w_j < C, \: \forall j$), y que el conjunto completo no cabe ( $\sum_{j=1}^{n} w_j > C$).

A continuación se describen resultados presentados en [5].