El problema de la mochila

Con la inflaci¨®n disparada, es posible que una de las mejores opciones vacacionales, para algunas/os de mis amables lectoras/es, sea la de lanzarse a la aventura con una mochila al hombro, con lo que se les plantear¨ªa un problema de optimizaci¨®n de recursos, ya que se tratar¨ªa de llevar un m¨¢ximo de cosas ¨²tiles con un m¨ªnimo de peso. Una cuesti¨®n en apariencia sencilla, pero que entra?a la suficiente complejidad potencial como para dar nombre a un importante cap¨ªtulo de la optimizaci¨®n combinatoria, conocido precisamente como ¡°problema de la mochila¡±, a menudo designado con las iniciales KP (...

Con la inflaci¨®n disparada, es posible que una de las mejores opciones vacacionales, para algunas/os de mis amables lectoras/es, sea la de lanzarse a la aventura con una mochila al hombro, con lo que se les plantear¨ªa un problema de optimizaci¨®n de recursos, ya que se tratar¨ªa de llevar un m¨¢ximo de cosas ¨²tiles con un m¨ªnimo de peso. Una cuesti¨®n en apariencia sencilla, pero que entra?a la suficiente complejidad potencial como para dar nombre a un importante cap¨ªtulo de la optimizaci¨®n combinatoria, conocido precisamente como ¡°problema de la mochila¡±, a menudo designado con las iniciales KP (del ingl¨¦s Knapsack Problem).

Imagina que tienes a tu disposici¨®n un abundante suministro de paquetes de los siguientes pesos y precios:

12 kilos, 4 euros

4 kilos, 10 euros

2 kilos, 2 euros

1 kilo, 2 euros

1 kilo, 1 euro

?C¨®mo llenar¨ªas tu mochila, en la que no puedes cargar m¨¢s de 15 kilos, para maximizar el valor de su contenido?

Y el metaproblema de rigor: ?por qu¨¦ he puesto este ejemplo tan aparentemente banal? Pues porque, navegando por la red en busca de datos curiosos y an¨¦cdotas sobre el tema, continuamente aparece esta mochila de 15 kilos con sus paquetes o cajas de los cinco tipos enumerados (generalmente con los precios en d¨®lares). ?Por qu¨¦ ser¨¢?

El problema de la mochila est¨¢ directamente relacionado con el problema de la suma de subconjuntos, de gran importancia en criptograf¨ªa y en teor¨ªa de la complejidad:

Dado un conjunto de n¨²meros enteros, determinar si existe alg¨²n subconjunto no vac¨ªo tal que la suma de sus elementos sea cero.

Para un conjunto con pocos elementos, la cuesti¨®n es trivial. Por ejemplo, en el caso {2, 3, 4, 7, 10} la respuesta es obviamente ¡°no¡±, pues todos los n¨²meros son positivos, y en el caso {-3, -2, 2, 5, 6} la respuesta es ¡°s¨ª¡±, porque en el subconjunto {-3, -2, 5}, 5-3-2 = 0. Pero para conjuntos grandes la cosa se complica extraordinariamente, dada la dificultad computacional de examinar uno por uno todos los casos posibles, lo que lleva a aplicar distintos tipos de algoritmos tendentes a simplificar los c¨¢lculos a la vez que se minimiza el margen de error.

El problema del cambio de monedas

Retomando el tema monetario, al que dedicamos varias entregas hace unas semanas, es evidente el paralelismo entre el problema de la mochila y el denominado ¡°problema del cambio de monedas¡±, que consiste en hallar el menor n¨²mero de monedas (de diversos valores previamente especificados) que sumen una determinada cantidad.

Una forma de abordar el problema del cambio es aplicar un ¡°algoritmo voraz¡± (ver Voracidad y optimizaci¨®n), que consiste en ir restando del valor buscado, una tras otra, las monedas de mayor valor posible. Por ejemplo, si he de devolver 80 c¨¦ntimos, primero doy una moneda de 50 c¨¦ntimos (que es la mayor que puedo restar de 80), luego una de 20 (que es la mayor que puedo restar de 30) y luego una de 10 (que es la mayor que puedo restar de 10). En este caso, la soluci¨®n es ¨®ptima, pues no puedo dar 80 c¨¦ntimos con menos de tres monedas (80 = 50 + 20 + 10). ?Ser¨¢ siempre as¨ª, o habr¨¢ casos en los que el algoritmo voraz no reducir¨¢ al m¨ªnimo el n¨²mero de monedas?

Y una cuesti¨®n pr¨¢ctica directamente relacionada con lo anterior: ?est¨¢ bien dise?ado nuestro sistema monetario (el del euro) o es mejorable? Dicho de otro modo: ?convendr¨ªa a?adir o eliminar alg¨²n valor para facilitar o simplificar las transacciones monetarias? Siempre he pensado que la moneda de 2 euros no tiene mucho sentido, pero¡­

Puedes seguir a MATERIA en Facebook, Twitter e Instagram, o apuntarte aqu¨ª para recibir nuestra newsletter semanal.