El problema de les maletes (o com empaquetar usant el nombre mínim de maletes)

 Els que algun cop hem agafat un vol de Ryanair (o similar), sabem que és molt important dividir l'equipatge en el mínim nombre de maletes (i que no passi d'un cert pes, o podem pagar una pasta!)

 En general, al fer la maleta, el més raonable és anar posant primer les coses "grans", i llavors les petites hi entren com per art de màgia...

 Un teorema diu que, si tenim unes quantes coses, amb uns determinats pesos, i cada maleta pot tenir un màxim de pes, l'estratègia d'ordenar tot el que hem de posar dintre les maletes de més pesat a menys, i anar omplint les maletes, des de la primera fins que ens hi càpiga tot, com a molt és un 22% pitjor que l'estratègia òptima (que suposaria provar totes les possibilitats, que per un conjunt de coses mitjà, com ara 20, és impossible de fer en un temps raonable...).

 Però aquesta estratègia pot tenir contradiccions, o coses que no s'entenen.

 Imaginem-nos que hem d'omplir maletes, que poden pesar un màxim de 524 Kg. Hem d'omplir-les amb 33 coses, que pesen: 442, 252, 252, 252, 252, 252, 252, 252, 127, 127, 127, 127, 127, 106, 106, 106, 106, 85, 84, 46, 37, 37, 12, 12 12, 10, 10, 10, 10, 10, 10, 9, 9.

 Anem omplint maletes, començant pel 442:

 Maleta 1: 442 (falten 82)

 Els següents 7 bultos, de 252 pesos, no es poden posar a la primera maleta. Però sí que es poden posar en parelles de 2 bultos per maleta. Per tant, hem d'omplir 4 maletes més:

 Maleta 1: 442 (82)
 Maleta 2: 252, 252 (20)
 Maleta 3: 252, 252 (20)
 Maleta 4: 252, 252 (20)
 Maleta 5: 252 (272)

 Seguim posant pesos. Els 5 de 127 només cabran a partir de la cinquena maleta:

 Maleta 1: 442 (82)
 Maleta 2: 252, 252 (20)
 Maleta 3: 252, 252 (20)
 Maleta 4: 252, 252 (20)
 Maleta 5: 252, 127, 127 (18)
 Maleta 6: 127, 127, 127 (143)

 Anem a posar ara els pesos de 106:

 Maleta 1: 442 (82)
 Maleta 2: 252, 252 (20)
 Maleta 3: 252, 252 (20)
 Maleta 4: 252, 252 (20)
 Maleta 5: 252, 127, 127 (18)
 Maleta 6: 127, 127, 127, 106 (37)
 Maleta 7: 106, 106, 106 (206)

 Col.loquem els 85, 84, 46, 37 i 37 per ordre, i sempre a la primera maleta on hi caben:

 Maleta 1: 442, 46 (36)
 Maleta 2: 252, 252 (20)
 Maleta 3: 252, 252 (20)
 Maleta 4: 252, 252 (20)
 Maleta 5: 252, 127, 127 (18)
 Maleta 6: 127, 127, 127, 106, 37 (0)
 Maleta 7: 106, 106, 106, 85, 84, 37 (0)

  Tres bultos de 12 Kg:




 Maleta 1: 442, 46, 12, 12, 12 (0)
 Maleta 2: 252, 252 (20)
 Maleta 3: 252, 252 (20)
 Maleta 4: 252, 252 (20)
 Maleta 5: 252, 127, 127 (18)
 Maleta 6: 127, 127, 127, 106, 37 (0)
 Maleta 7: 106, 106, 106, 85, 84, 37 (0)


  Sis bultos de 10 Kg:

 Maleta 1: 442, 46, 12, 12, 12 (0)
 Maleta 2: 252, 252, 10, 10 (0)
 Maleta 3: 252, 252, 10, 10 (0)
 Maleta 4: 252, 252, 10, 10 (0)
 Maleta 5: 252, 127, 127 (18)
 Maleta 6: 127, 127, 127, 106, 37 (0)
 Maleta 7: 106, 106, 106, 85, 84, 37 (0)

 I per últim, els dos bultos de 9 Kg:


 Maleta 1: 442, 46, 12, 12, 12 (0)
 Maleta 2: 252, 252, 10, 10 (0)
 Maleta 3: 252, 252, 10, 10 (0)
 Maleta 4: 252, 252, 10, 10 (0)
 Maleta 5: 252, 127, 127, 9, 9 (0)
 Maleta 6: 127, 127, 127, 106, 37 (0)
 Maleta 7: 106, 106, 106, 85, 84, 37 (0)




 Sembla que ens n'hem sortit bastant bé, veritat? 7 maletes, i totes al límit de pes!


 Però, just abans de fer els paquets amb les maletes, ens adonem que no necessitem el bulto de 46 Kg. Així que tornem a fer el mateix, però prescindint del bulto de 46 Kg.



 Un cop havíem posat els pesos de 106 teníem la següent distribució:


 Maleta 1: 442 (82)
 Maleta 2: 252, 252 (20)
 Maleta 3: 252, 252 (20)
 Maleta 4: 252, 252 (20)
 Maleta 5: 252, 127, 127 (18)
 Maleta 6: 127, 127, 127, 106 (37)
 Maleta 7: 106, 106, 106 (206)

 Ara només hem d'acabar d'omplir amb: 85, 84, 37, 37, 12, 12 12, 10, 10, 10, 10, 10, 10, 9, 9. Comencem amb els 85, 84, 37, 37:


 Maleta 1: 442, 37, 37 (8)
 Maleta 2: 252, 252 (20)
 Maleta 3: 252, 252 (20)
 Maleta 4: 252, 252 (20)
 Maleta 5: 252, 127, 127 (18)
 Maleta 6: 127, 127, 127, 106 (37)
 Maleta 7: 106, 106, 106, 85, 84 (37)


 Ara anem per les de 12:


 Maleta 1: 442, 37, 37 (8)
 Maleta 2: 252, 252, 12 (8)
 Maleta 3: 252, 252, 12 (8)
 Maleta 4: 252, 252, 12 (8)
 Maleta 5: 252, 127, 127 (18)
 Maleta 6: 127, 127, 127, 106 (37)
 Maleta 7: 106, 106, 106, 85, 84 (37)


 Les de 10...:

 Maleta 1: 442, 37, 37 (8)
 Maleta 2: 252, 252, 12 (8)
 Maleta 3: 252, 252, 12 (8)
 Maleta 4: 252, 252, 12 (8)
 Maleta 5: 252, 127, 127, 10 (8)
 Maleta 6: 127, 127, 127, 106, 10, 10, 10 (7)
 Maleta 7: 106, 106, 106, 85, 84, 10, 10 (17)


 I ara ens falten dos bultos de 9 Kg. Però quin desastre! A les 5 primeres maletes només tenim lloc per 8 Kg. A la sisena, per 7. I a la setena, només hi podem posar un dels dos bultos de 9 Kg que tenim.


 Per tant... necessitem una vuitena maleta, que anirà només amb un bulto de 9 Kg!!!


 O sigui: si afegim el bulto de 46 Kg, necessitem 7 maletes, i si el traiem... en necessitem 8!