Enigme
Cette année, le Père Noël est bien embêté. Les enfants, mais aussi les parents, lui ont demandé beaucoup trop de cadeaux et sa hotte est trop petite car elle ne peut contenir que 28 cadeaux. Heureusement, les cadeaux restants seront envoyés par La Poste.
– M. et Mme Fulkerson et leurs 2 enfants ont commandé 10 cadeaux
– M. et Mme Dijkstra et leurs 3 enfants ont commandé 8 cadeaux
– M. et Mme Benders qui n’ont pas d’enfant ont commandé 5 cadeaux
– M. et Mme Dantzig et leur enfant ont commandé 5 cadeaux
– M. et Mme König et leurs 5 enfants ont commandé 15 cadeaux
Le Père Noël voudrait satisfaire le maximum de personnes malheureusement son lutin matheux n’est pas là.
Pouvez-vous lui indiquer les familles qu’il doit livrer et celles qui recevront leurs cadeaux par la Poste ?
Solution : C’est un problème de « sac-à-dos » !
Mettons tous d’abord ces données sous forme de tableau :
Certains d’entre vous auront reconnu le problème de « sac à dos ». La meilleure solution consiste à dire au Père Noël de livrer les familles Dijkstra, Dantzig et König, soit 15 personnes et 28 cadeaux.
Méthode de résolution n°1 : par algorithme glouton
Cette méthode consiste à trier les familles selon le rapport personnes/cadeaux par ordre décroissant, puis à choisir dans cet ordre les familles jusqu’à remplir la hotte.
Méthode de résolution n°2 : par énumération
Il y a en tout 32 combinaisons possibles de choix de familles. Il est donc assez facile de les énumérer toutes avec par exemple un tableur.
Méthode de résolution n°2 : par PLNE
Mathématiquement, ce problème peut s’écrire sous la forme d’un problème linéaire en nombres entiers :
