Lister les combinaisons possibles...
nicosob
Messages postés
3
Date d'inscription
Statut
Membre
Dernière intervention
-
Flachy Joe Messages postés 2102 Date d'inscription Statut Membre Dernière intervention -
Flachy Joe Messages postés 2102 Date d'inscription Statut Membre Dernière intervention -
Bonjour,
Je vais aller directement dans le coeur de mon problème.
Je voudrais afficher une liste de combinaisons possibles.
Pour illustrer ma requête, je vais prendre un exemple concret : dans un hôtel, j'ai 3 chambres différentes : R1, R2 et R3. Chaque chambre peut contenir un nombre maximum de personnes. Ici, admettons que R1 peut accueillir 3 personnes maximum, R2 peut en accueillir 4 max et R3 peut en accueillir 15 max.
Je voudrais avoir un algorithme qui me permette de lister les combinaisons de chambre en fonction d'un nombre de personnes annoncés.
Dans mon exemple, si j'ai 10 personnes annoncées, les combinaisons que je veux sont :
1 x R3
3 x R2
2 x R2 + 1 x R1
1 x R2 + 2 x R1
4 x R1
Je cherche donc un algorithme qui aurait en entrée les données suivantes :
- nombre de personnes attendues
- Liste des chambres et de leur contenance max
et du coup en sortie :
- combinaisons des chambres pour faire rentrer tout ce petit monde !
Je me casse un peu les dents dessus... Toute aide serait appréciée ;)
Merci d'avance !
Je vais aller directement dans le coeur de mon problème.
Je voudrais afficher une liste de combinaisons possibles.
Pour illustrer ma requête, je vais prendre un exemple concret : dans un hôtel, j'ai 3 chambres différentes : R1, R2 et R3. Chaque chambre peut contenir un nombre maximum de personnes. Ici, admettons que R1 peut accueillir 3 personnes maximum, R2 peut en accueillir 4 max et R3 peut en accueillir 15 max.
Je voudrais avoir un algorithme qui me permette de lister les combinaisons de chambre en fonction d'un nombre de personnes annoncés.
Dans mon exemple, si j'ai 10 personnes annoncées, les combinaisons que je veux sont :
1 x R3
3 x R2
2 x R2 + 1 x R1
1 x R2 + 2 x R1
4 x R1
Je cherche donc un algorithme qui aurait en entrée les données suivantes :
- nombre de personnes attendues
- Liste des chambres et de leur contenance max
et du coup en sortie :
- combinaisons des chambres pour faire rentrer tout ce petit monde !
Je me casse un peu les dents dessus... Toute aide serait appréciée ;)
Merci d'avance !
A voir également:
- Lister les combinaisons possibles...
- Lister les disques cmd - Guide
- CMD - Lister les disques ✓ - Forum Windows
- Toutes les combinaisons possibles avec 4 chiffres - Forum Programmation
- Sql lister les tables ✓ - Forum Programmation
- Comment lister sous dos ses lecteurs de disk - Forum Windows
2 réponses
Bonjour
selon le langage cible, la solution sera sensiblement différente.
Peux tu préciser ce langage?
selon le langage cible, la solution sera sensiblement différente.
Peux tu préciser ce langage?
La solution est un arbre, expl pour 10 clients et les chambre [R1:3, R2:4, R3:15] :
https://pix.toile-libre.org/upload/original/1446204851.jpg
A partir de la liste des places dans les chambres, on peut construire l'arbre de tous les remplissages possibles avec des imbrications de boucles ou une fonction récursive.
A partir de cet arbre, on coupe les branches qui contiennent plus de personnes placées que de places demandées et on obtient toutes les solutions pour un nombre donné.
https://pix.toile-libre.org/upload/original/1446204851.jpg
A partir de la liste des places dans les chambres, on peut construire l'arbre de tous les remplissages possibles avec des imbrications de boucles ou une fonction récursive.
A partir de cet arbre, on coupe les branches qui contiennent plus de personnes placées que de places demandées et on obtient toutes les solutions pour un nombre donné.
Ok, je viens de comprendre que R1, R2 et R3 sont des types de chambre.
Il suffit de faire une liste qui contient plusieurs occurrence de chaque type en entrée pour que ça revienne au même.
expl : 3 chambre R1, 4 R2 et 2 R3 donne une liste [ 3, 3, 3, 4, 4, 4, 4, 15, 15 ]
Mais ton arbre contiendra alors des branches équivalente du genre
(3 dans R1a , 2 dans R1b, 5 dans R3) = (2 dans R1a , 3 dans R1b, 5 dans R3)
Si tu ne cherche qu'avec des remplissages optimisés pour un max de personnes par chambre, ça devrait pouvoir se simplifier.
Il suffit de faire une liste qui contient plusieurs occurrence de chaque type en entrée pour que ça revienne au même.
expl : 3 chambre R1, 4 R2 et 2 R3 donne une liste [ 3, 3, 3, 4, 4, 4, 4, 15, 15 ]
Mais ton arbre contiendra alors des branches équivalente du genre
(3 dans R1a , 2 dans R1b, 5 dans R3) = (2 dans R1a , 3 dans R1b, 5 dans R3)
Si tu ne cherche qu'avec des remplissages optimisés pour un max de personnes par chambre, ça devrait pouvoir se simplifier.
Merci pour l'intérêt porté à ma question.
A priori, le code finale est en php, mais honnêtement, je suis preneur d'une solution algorithmique pure, ou même d'une solution sur Excel ! :)