Casse tête chinois

Bonjour à tous;
voilà je suis vraiment bloqué pour trouver un algorithme à mon problème.

Résumé:
Je dispose d'un nombre de commandes Nc, chaque commande contient un nombre variable d'objets No. Le but c'est de remplir un nombre maximal de de cavités-les cavités ayant des capacités égales- avec ces objets.
Les conditions sont:
1-Il faut remplir le maximum de cavités
2-Il faut que les cavités remplies soient pleines.
3-Il faut que pour une commande utilisée, tous ses objets soient utilisés.

L'idée c'est de jouer sur une combinaison de commandes de sortes que la somme de leurs objets soient divisible par la capacité des cavités.
Merci pour votre aide.

Si j'ai bien compris, une commande est dans une seule cavité.

Le problème est NP complet même s'il n'y a que 2 cavités: c'est le problème de PARTITION (en disant que la taille de la cavité est la moitié du onmbre total d'objets).

Il faut donc t'orienter vers les techniques d'optimisation exactes ou approchées selon tes besoins et les problèmes de type "bin packing".

Bonjour,

Une première idée, je ne sais pas ce qu'elle vaut :

On définit une notion de boites qui sont des "sous-cavités" dont le nombre d'objet sera compris entre la taille de la plus petite commande et la taille de la cavité.

On travaille par itération en augmentant par pas de 1 la taille des boites:
Une boite de taille N peut contenir toutes les combinaisons de boites de taille N1 et telles que N=N1+N2 et N1>N2>=0.

Lorsqu'on est arrivé à N=taille de la cavité, on envisage toutes les combinaisons possibles de boites :
on vérifie, lors de la décomposition progressives des boites en commandes, si une boite a déjà été utilisée : dans ce cas, on abandonne la décomposition.

Bonjour,

en général sur les problèmes NP complet, on ne peut tester toute les possbilités, c'est bien là le problème.

Une heuristique toute simple pour résoudre ce genre de problème est de trier les objets en fonction de leurs volume et de commencer à placer les plus gros. En procédant de cette sorte, on s'approche de la solution. Bien évidemment, comme toute heuristisque elle ne fonctionne pas tout le temps.
Pense peut etre au taboo.

Bon courage...