[php] Calculer le nombre de combinaison

Bonjour,
je suis à la recherche d'une fonction qui puisse me permettre de calculer un nombre de combinaison possible.

Je m'explique :
j'ai 9.56m de mur à faire, et j'ai plusieurs types de panneaux pour le réaliser.
4 panneaux de 2.5m,
3 de 1.25m
2 de 0.625m

Je souhaite calculer le nombre de possibilité avec ces panneaux sachant que je peux dépasser que de 50cm la longueur du mur, soit 10.06m.

Merci pour ceux qui auront le courage de répondre, je suis à l’affût de la moindre idée !

JE pense que le plus simple est de partir sur un algorithme glouton: tu commences par prendre un maximum de grands panneaux, et tu finis avec des plus petits quand tu n'as plus de grands ou si ajouter un grand de plus te fait dépasser la limite.

Une fois que tu as une solution, à priori tu vas trouver celle qui utilise le moins de panneaux, tu peux en dériver d'autres en remplaçant un panneau de 2.5 par deux de 1.25 et continuer tant que tu as du stock.

Après avoir fait suffisament de remplacements, dans ton cas terminer avec les 1.25 en 2*0.625, essayer de voir ce qui se passe si tu enlèves le dernier panneau de 0.625. Y a-t-il des subdivisions encore plus petites ? Est-ce que la longueur est encore suffisante ? Dans cet exemple la réponse est non, alors on s'arrête.

Cette idée me semble pas mal si l'ordre n'a pas d'importance. Après il faut aussi que tu détermines si c'est vraiment le cas. Est-ce que 2.5+2.5+2.5+1.25+1.25 est la même chose que 1.25+2.5+2.5+2.5+1.25 par exemple ? Si non, il faudra aussi calculer des permutations à partir d'une solution de départ.

On pourrait aussi se demander si on cherche vraiment toutes les possibilités, ou si certaines sont meilleures ou plus intéressantes que d'autres, par exemple la solution est peut-être meilleure s'il y a moins de gaspillage, i.e. >=9.56 mais le plus proche possible. Dans ce cas, on retrouve une variante du problème ultra-classique du sac à dos, en fait.

Si on exécute ce genre d'algorithme sur ton cas d'exemple, on commence par trouver 2.5+2.5+2.5+2.5.
A partir de là on doit trouver 2.5+2.5+2.5+1.25+1.25, puis 2.5+2.5+2.5+1.25+0.625+0.625 et 2.5+2.5+1.25+1.25+0.625+0.625.
Ensuite on doit arriver sur 2.5+2.5+2.5+1.25+0.625 et ce faisant on arrête, puisque ce n'est plus suffisant.

Bref, je pense que tu dois avoir compris l'idée.
Modifié par QuentinC (25 Jul 2014 - 08:16)