Remplir son sac à dos : un problème mathématique complexe

Pour vos vacances, êtes-vous plutôt valise, ou plutôt sac à dos ? De toute façon, vous devrez affronter l’éternel problème du remplissage optimal de votre bagage, qui vous permettra à la fois d’emporter tout ce dont vous avez besoin, sans dépasser un volume et un poids raisonnables.

Heureusement, vous avez droit à une séance d’entraînement sur le web. Rendez-vous sur Interstices , blog dédié à la recherche en informatique, animé par des chercheurs, enseignants et journalistes scientifiques, qui n’hésitent pas à aborder les problèmes les plus complexes au travers d’applications très ludiques.

Le billet intitulé Le problème du sac à dos propose un petit jeu beaucoup plus difficile qu’il n’y paraît : il s’agit de remplir un sac avec des objets sans dépasser le poids autorisé, et en atteignant la valeur demandée. Si le niveau « débutant » peut faire ricaner les amateurs de calcul mental, tout se complique dès que l’on passe au niveau « maître ». Quant au niveau « expert », je n’ai même pas essayé.

Mais le jeu n’était qu’une mise en jambe. L’article se poursuit par un exposé de haut niveau sur les problèmes d’optimisation combinatoire. Les auteurs savent manifestement de quoi ils parlent.

La lecture intégrale de l’article nous permettra t-elle de remplir notre bagage de façon idéale ? Peut-être pas Mais nous aurons largement élargi notre culture mathématique. Et rien ne nous empêchera de revenir au jeu du sac à dos au retour des vacances

Le problème du sac à dos , sur le blog Interstices