Hem de pagar 2,75 euros en el caixer automàtic del pàrquing. Tenim una moneda de dos euros, una d’un euro, dues de deu cèntims i tres monedes de 5 cèntims. Cóm hem d’introduir les monedes per tal de quedar-nos al final amb el mínim de monedes a la butxaca?

És clar que no podem pagar l’import exacte. D’altra banda, el total de les nostres monedes és de 3,35 euros. Ens sobren diners i la màquina ens haurà de tornar canvi.

El problema té la seva gràcia, perquè volem dues coses a l’hora. Volem desfer-nos del màxim de monedes, i volem que la màquina ens en torni el mínim nombre possible. Si ho pensem bé, veurem que som davant d’un problema d’optimització combinatòria, no gens fàcil.

El millor és utilitzar un mètode heurístic, que no sempre dona el millor resultat possible però que és raonablement fàcil d’usar i memoritzar, a la vegada que ens pot servir per exercitar la ment en situacions quotidianes. Es tracta de desacoblar les dues parts del problema i primer pensar només en el canvi que ens donarà el caixer.

És fàcil veure que com a mínim hem d’introduir tres euros. I és clar que hem de posar-hi tant la moneda d’un euro com la de dos euros, perquè si no ho fem, no hi ha manera que arribem als 2,75 euros.

També sabem que el màxim que hi podem posar són 3,35 euros, que és tot el que tenim. Per tant, el valor de les monedes que hi posarem segur que es trobarà entre 3 i 3,35 euros. Hi ha alguna quantitat que ens minimitzi el nombre de monedes que la màquina ens tornarà en el canvi?  La resposta és senzilla i permet pensar-la in situ, quan som al caixer: si el valor del total de monedes que hi posem és de 3,25 euros, el canvi consistirà (segurament) en una única moneda de 50 cèntims.

Ja tenim resolta la primera part del problema. Podem minimitzar el nombre de monedes del canvi si aconseguim posar-hi 3,25 euros. Passem a la segona part: cóm podem desfer-nos del màxim de monedes i acabar introduint 3,25 euros abans que la màquina ens retorni el canvi?  Una solució és utilitzar el màxim de monedes (de les que tenim) per a fer un total de 3,25 euros, i, a continuació, anar-les posant al caixer ordenadament, començant per les de poc valor i acabant per les més grans. En el nostre cas, decidirem introduir les tres de cinc cèntims, una de deu cèntims, la d’un euro i la de dos euros perquè tot plegat suma 3,25 euros i així només ens quedarem amb una moneda de deu cèntims. Tenim força llibertat pel que fa a l’ordre en que posem les monedes, però és clar que hem de deixar pel final o bé la moneda d’un euro o bé la de dos euros si volem evitar que la màquina ens doni el canvi abans d’hora.

En resum: hi hem d’introduir 3,25 euros, i això ho podem fer de manera que aconseguim treure’ns totes les monedes que teníem menys una. A més, podem minimitzar el nombre de monedes que ens tornarà la màquina. Al final, ens quedarem amb dues monedes a la butxaca i pensarem que hem resolt bé el problema.

Quina és la simplificació que hem fet i que no sempre funciona?:  La de desacoblar el problema. No és aquest el cas, però podria passar que tinguéssim una solució en que la màquina ens retorna dues (no una) moneda, i que fa que ens puguem desfer de bastantes més monedes. Per això, si volem estar segurs d’haver arribat a la solució òptima, a la millor de totes, hem de fer una anàlisi exhaustiva de totes les possibilitats (vegeu la nota al final). Us veieu amb cor de pensar un exemple en el que la heurística que us he proposat no arriba a la millor solució?

Encara que sembli estrany, pagar en un caixer no és massa diferent que jugar a escacs. Tenim un objectiu (en el nostre cas, quedar-nos amb el mínim de monedes), i hem de dissenyar una estratègia (que no és més que un algorisme) per arribar-hi o, al menys, per anar-hi a prop. Aquesta estratègia, però, depèn “d’un altre”, que en aquest cas és l’algorisme que algú ha programat en el caixer. El nostre algorisme serà millor si entenem i tenim en compte l’algorisme “de l’altre”. I a més, tenim la dificultat afegida que la solució òptima d’aquests problemes requereix analitzar una munió de possibilitats. Per això, és bo pensar en heurístiques, que no són més que algorismes ràpids que habitualment donen solucions raonablement acceptables. D’això en parla la teoria de jocs. En escacs, per exemple, un algorisme òptim hauria d’analitzar totes les possibles evolucions futures del joc, tenint en compte totes les possibles estratègies tant les nostres com les de l’altre; com que això és intractable, els jocs per ordinador sempre utilitzen heurístiques, ràpides però subòptimes.

No es pot tenir tot. Els algorismes de càlcul i raonament mental són molt útils, però no sempre ens donen la millor solució. Els algorismes de cerca exhaustiva i optimització combinatòria troben la millor solució possible, però millor que no penseu en usar-los quan sou davant del caixer perquè de ràpids no en tenen res.

Nota final: Si volem estudiar bé el problema i estar segurs que hem trobat una bona solució, sobretot en casos en què tenim més monedes, ens cal una mica de paper i llapis. Pensem en la primera part del problema, la que intenta minimitzar el nombre de monedes que esperem que ens torni la màquina. Hem vist que el valor de les monedes que hi posarem estarà sempre entre 3 euros i 3,35 euros. Combinant adequadament les monedes que tenim, podem aconseguir introduir al caixer (abans que ens comenci a donar el canvi) qualsevol d’aquestes quantitats:

• 3 euros (amb les dues monedes de un i dos euros)
• 3,05 euros (amb les monedes d’un i dos euros i una de 5 cèntims)
• 3,10 euros (amb les monedes d’un i dos euros i dues de 5 cèntims, per exemple)
• 3,15 euros (amb les monedes d’un i dos euros i les tres de 5 cèntims, per exemple)
• 3,20 euros (amb les monedes d’un i dos euros, una de 10 cèntims i dues de 5 cèntims, per exemple)
• 3,25 euros (amb les monedes d’un i dos euros, les tres de 5 cèntims i una de 10 cèntims, per exemple)
• 3,30 euros (amb les monedes d’un i dos euros, dues de 5 cèntims i dues de 10 cèntims)
• 3,35 euros (amb les monedes d’un i dos euros, les tres de 5 cèntims i dues de 10 cèntims)

I, en cada un d’aquests casos, què ens tornarà la màquina?

• En el cas de 3 euros, el més probable és que ens torni dues monedes, de 20 i 5 cèntims
• En el cas de 3,05 euros, el més probable és que ens torni dues monedes, de 10 i 20 cèntims
• En el cas de 3,10 euros, el més probable és que ens torni tres monedes, de 5, 10 i 20 cèntims
• En el cas de 3,15 euros, el més probable és que ens torni dues monedes de 20 cèntims
• En el cas de 3,20 euros, el més probable és que ens torni tres monedes, una de 5 i dues de 20 cèntims
• En el cas de 3,25 euros, el més probable és que ens torni una moneda de 50 cèntims
• En el cas de 3,30 euros, el més probable és que ens torni dues monedes, de 5 i 50 cèntims
• En el cas de 3,35 euros, el més probable és que ens torni tres monedes de 20 cèntims

Dic que això és el més probable, perquè el caixer funciona en base a un algorisme, i no sabem exactament quines opcions ha considerat la persona que l’ha programat. El lògic seria que ens tornés el canvi amb el mínim possible de monedes, però això no és sempre així. Si us hi heu fixat, els caixers moltes vegades donen dues monedes de 50 cèntims enlloc d’una d’un euro. I, com indiquem en el darrer cas dels que hem vist, per tornar 60 cèntims, és força habitual que ens torni 3 monedes de 20 cèntims encara que seria més òptim si ens retornés una de 10 i una de 50. De fet en el nostre cas, fixeu-vos que els 3,35 euros també serien una solució òptima si sabem que la màquina ens tornarà dues monedes (de 50 i 10) enlloc de tres de 20.

Però si haguéssim de pagar 2,90 euros i tinguéssim tres monedes d’un euro i tres de deu cèntims, és fàcil veure que l’heurística que abans us he proposat no és òptima. En aquest cas, el millor és desfer-nos de totes les monedes tot forçant que la màquina ens torni dues monedes de vint cèntims, perquè si fem que ens torni només una moneda de canvi, acabarem amb més de dues monedes a la butxaca.

Per tal d’estar segurs que hem trobat la solució òptima, no tenim altra sortida que analitzar totes les possibilitats i utilitzar tècniques d’optimització combinatòria. Tenim moltes maneres d’anar introduint les monedes al caixer (de fet és un problema de permutacions amb repetició en que algunes permutacions són idèntiques perquè, arribat un cert punt, generen el mateix canvi per part de la màquina). Per a cada una de les possibilitats sabem el nombre total de monedes: les que ens tornarà més les que no hi posem. L’anàlisi exhaustiu de totes elles ens porta a la solució òptima.