algorithme conbinatoire

[invite2db87db1]

Bonjour à tous,
Votre aide me sera bien précieuse pour trouver une solution à mon probléme .Je galère depuis des heures en essayant de faire ce petit algorithme de réservation qui donne des propositions de reservation selon les types d'hebergement existant
La problématique qui se pose est la suivante :
Lors de la réservation d’un hôtel, selon le nombre de participants, le moteur de réservation doit proposer à l’internaute toutes les répartitions possibles.

Exemple : un hôtel contient 2 types de logement
Type logement 1 : chambre single : maximum 1 personne
Type logement 1 : chambre double : maximum 2 personnes
L’internaute réserve pour 3 personnes :

Le moteur de réservation doit lui indiquer les répartitions suivantes :
Proposition 1 : 1 double + 1 single
Proposition 2 : 3 single

Alors pour un hôtel contenant (n) types de logement (type 1, type 2, …type n) caractérisés par les capacités (C1, C2,…..Cn)

L’internaute demande une réservation dans cet hôtel pour X personnes.
Alors,je devrais developper un petit programme intelligent en PHP qui donne tout les cas possible de reservation en fonction des capacité des chambres C1, C2, ... , Cn et le nombre de personne à heberger X.

Alors comme 1er idée, j'ai pensé a produire toutes les combinaisons possibles de C1 à Cn telque la somme de cette combinaison = X

Comment alors resoudre ce problème et trouver les (ai):

X= Somme(ai . Ci) {i=1 a n} j'ai essayé avec la methode de Gauss mais toujours rien!
Si vous avez des idées, j'en serai reconnaissant.
Merci d'avance.
-----

[taladris]

Salut,

Je n'ai pas essayer mais un programme récursif devrait marcher, non?

Par contre, ton exemple me dérange: dans ton exemple, est-ce que ton programme doit proposer comme solution 3 chambres doubles quand il y a 3 clients? Dit autrement, est-ce que les chambres doivent être remplies au maximum ou laisse-tu le choix au client?

Cordialement

[invite2db87db1]

Bonjour taladris,
Merci pour votre reponse.
Pour plus de precision sur la capacité des chambre, celles-ci doivent être remplies au max et vous avez n chambre ayant chacune n capacité.
Alors, L'idée qui m'est venue c'est de diviser le nombre de places par deux et vous aurez le nombre de chambres doubles à proposer au max.
Si votre division vous donne un reste, il faut ajouter un chambre single.
Si vous voulez toutes les possibilité, vous devrez jouer avec une boucle correspondant aux nombres max de chambres . vous commencez par le plus de chambres doubles possible puis vous en enlevez une tout en ajoutant deux singles et ainsi de suite vous aurez toutes les possibilités.mais le probleme j'ai encore du mal à valider mon raisonnement logique.

[invite2db87db1]

Bonjour tout le monde,
J'ai réellement un grand souci,je perd pied,je n'arrive toujours pas à resoudre cet algorithme!
Merci d'avance pour votre précieuse aide!

[A voir en vidéo sur Futura]

[invite2db87db1]

Bonjour à tous ,j'ai tout essayé et je n'arrive toujours pas à faire fonctionner mon Algorithme,j'ai également essayé en utilisant le graphe de Ferrer mais sans succès..
Si quelqu'un a une suggestion, merci d'avance !

[invite765732342432]

Pourquoi travailles-tu directement avec les chambres "réelles" plutôt que simplement avec des chambres virtuelles ?
Je m'explique: dans ton exemple, tu as 2 chambres: single et double.
Tu fais ta combinatoire pour trouver toutes les possibilités sans tenir compte du nombre de chambres disponibles "réellement"

Une fois que tu as ça, tu vires les solutions impossibles (il me faut 3 chambres single, mais je n'en ai que 2 dispo, ...)
Et tu refais ta combinatoire avec les chambres réelles...

Si je ne suis pas clair ou à coté de la plaque, n'hésite pas à me le dire.