Problema de la mochila

Eixemple del problema de la mochila: donada una mochila en una capacitat de 15 kg que puc omplir en caixes de distint pes i valor, ¿quines caixes elegixc de modo d'maximizar els meus guanys i no excedir els 15 kg de pes permesos?

En algoritmia, el problema de la mochila, comunament abreviat per KP (del anglés Knapsack problem) és un problema d'optimisació combinatòria, és dir, que busca la millor solució entre un conjunt finito de possibles solucions a un problema. Modela una situació anàloga en omplir una mochila, incapaç de soportar més d'un pes determinat, en tot o part d'un conjunt d'objectes, cada u en un pes i valor específics. Els objectes colocats en la mochila deuen maximizar el valor total sense excedir el pes màxim.

Història

El problema de la mochila és un dels 21 problemes NP-complets de Richard Karp, establits pel informàtic teòric en un famós artícul de 1972. Ha segut intensament estudiat des de mediats del sigle XX i es fa referència a ell en l'any 1897, en un artícul de George Mathews Ballard.

Si be la formulació del problema és senzilla, la seua resolució és més complexa. Alguns algoritmes existents poden resoldre-ho en la pràctica per a casos d'un gran tamany. No obstant, l'estructura única del problema, i el fet de que es presente com un subproblema d'atres problemes més generals, ho convertixen en un problema freqüent en l'investigació d'operacions.

Definició

A continuació es definix formalment el problema. Supongam que tenim $n$ distints tipos de ítems, que van de l'1 a el $n$. De cada tipo de ítem es tenen $q_i$ ítems disponibles, a on $q_i$ és un sancer positiu que complix $1\le q_i<\mathrm{\infty }$.

Cada tipo de ítem i té un benefici associat dau per v_i i un pes (o volum) w_i. Usualment s'assumix que el benefici i el pes no són negatius. Per a simplificar la representació, se sol assumir que els ítems estan llistats en orde creixent segons el pes (o volum).

Per un atre costat es té una mochila, a on es poden introduir els ítems, que soporta un pes màxim (o volum màxim) W.

El problema consistix en ficar en la mochila ítems de tal forma que es maximizar el valor dels ítems que conté i sempre que no se supere el pes (o volum) màxim que pot soportar la mateixa. La solució al problema vindrà dau per la seqüència de variables x₁, x₂, ..., x_n a on el valor de x_i indica quantes còpies es ficaran en la mochila del tipo de ítem i.

El problema es pot expressar matemàticament per mig del següent programa llineal:

$\begin{array}{cc}\text{maximizar }& \sum _{i=1}^n{v}_i{x}_i\\ \text{tal que }& \sum _{i=1}^n{w}_i{x}_i\le W\\ \text{y}& 0\le x_i\le q_i.\end{array}$

Si $q_i=1$ per a $i=1,2,\mathrm{...},n$ es diu que es tracta del problema de la mochila 0-1. Si un o més $q_i$ és infinit llavors es diu que es tracta del problema de la mochila no acotat també cridat a voltes problema de la mochila sancera. En un atre cas es diu que es tracta del problema de la mochila acotat