Bonjour,
J’aimerais que vous m’aiguilliez sur un algo pouvant résoudre mon problème, voir de reformuler le problème plus simplement :
J'ai des boules de Couleurs différentes (une 20aine de couleurs possibles maxi). Pour chaque couleur, j’ai 10 boules de poids et valeurs différentes par exemple :
(pour toutes les couleurs, le poids croît avec les valeurs mais ne sont pas liés par une relation).
Code : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6 Bnoires : Valeurs : 2, 4, 6, 8, 10, 12, 14, 18, 20, 22. Poids : 1, 2, 3, 5, 7, 9, 11, 13, 15, 17. Brouges : Valeurs : 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Poids : 1, 5, 10, 15, 20, 25, 30, 35, 40, 45.
J’ai aussi n Conteneurs de 4 emplacements (n variant de 0 à 10 maxi), et pouvant supporter un POIDS_MAX (le même pour tous les conteneurs).
Le but de l’algo serait de remplir chaque Conteneur avec 4 boules sachant que :
1) les Conteneurs disposent d’un Tas de boules distinct, et tous les tas sont identiques ;
2) un Conteneur ne peut pas avoir 2 boules d’une même couleur ;
3) on doit maximiser la somme des Valeurs de tous les Conteneurs (une fonction g permet d'évaluer la valeur d'un Conteneur) ;
4) on doit répondre au mieux à des contraintes du type : ‘il faut une Valeur cumulée de Bnoires = x’ ET ‘il faut une Valeur cumulée de Bvertes = y’ etc…
Dans un 1er temps je comptais faire :
- pour chaque Tas d’un Conteneurs :
- lister toutes les combinaisons 4 Couleurs dans l’ensemble des nbCouleurs.
- pour chaque combinaison de 4 Couleurs, lister toutes les combinaisons de Poids possible en éliminant les combinaisons ou f(Poids) > POIDS_MAX (f étant une fonction qui évalue le poids de 4 boules).
A partir de là on a pour chaque Conteneur une liste de combinaison de couleurs/poids possible. Il faudrait lister toutes les combinaisons pour les n Conteneur, maximiser la somme des valeurs des conteneurs en répondant au mieux aux contraintes du 4).
Donc je me demandais si un algo particulier (j’imagine d’optimisation combinatoire) pouvait répondre plus simplement à mon problème sans avoir à lister des combinaisons de combinaisons qui vont me donner un nombre de solution énorme à évaluer.
Je pensais à un recuit simulé mais j’ai pas envi de m’y lancer pour me rendre compte à la fin qu’il y à plus adapté, ou qu'il ne répond pas à mon problème.
Partager