Je cherche un algo (en code direct si vous êtes plus à l’aise) qui permet d’optimiser le remplissage d’un carton (sur 3 dimensions bien sur) à partir de produit (on considère qu’ils sont tous carré mais de tailles différentes), sans contraintes de masse.
Quelqu’un a déjà fait ça ? J’ai trouvé des exemples en 2D mais c’est pas transposable en 3D
Au cas où ça t’aiderait, ton problème porte un nom : Bin-packing (en 3D dans ton cas). C’est un problème manifestement NP-Complet pour lequel il existe de bonnes heuristiques.
Bon courage 
Que ça s’appelle du bin-packing je le sais 
Mais je ne trouve pas de modèle 3D tous les algo sur le net sont en 2D
Hum, des recherches sur mon moteur de recherche préféré me donnent pas mal de résultats. Par exemple :
cs.ukzn.ac.za/publications/e … 07-034.pdf (anglais)
en.wikipedia.org/wiki/Bin_packing_problem (anglais)
github.com/dvdoug/BoxPacker (anglais)
sourceforge.net/projects/boxpacking3d/ (en polonais ^^)
Quelques idées ici : programmers.stackexchange.com/qu … s-shipping (anglais)
C’est un problème très compliqué (ça tu l’avais compris), il faut savoir si le facteur limitant c’est la masse, ou la taille ou les deux. Çä te donne une quantité C qui diminue au fur et à mesure que tu remplis ton colis. Il faut savoir si tu as un paquet devant toi ou plusieurs.
Si tu as plusieurs paquets tu as plusieurs stratégies:
- Mettre l’objet dans le premier colis possible (stratégie du flemmard)
- Mettre le colis dans le premier colis capable de l’accepter classés par C décroissant (en clair le plus rempli)
- Mettre le colis non pas dans le premier colis capable de l’accepter comme ci dessus mais le second (bizarrement ce serait la meilleure)
- Mettre le colis dans le dernier colis capable de l’accepter (c’est nul comme efficacité!)
Si il y a un seul colis, la stratégie gloutonne consistant à classer les objets par taille décroissante et à les mettre dans le colis au fur et à mesure est excellente même si certaine amélioration sont possibles. À noter que le premier ordinateur en France a été acheté par la SNCF pour optimiser la découpe de pièces dans des plaques métalliques, elle a eu un gain de 10%…
Personnellement je résoudrais ça par un programme linéaire en nombre entier.
C’est à dire que je modéliserais ton problème sous forme d’un système d’équation (une qui représente ton objectif (minimiser le nombre de carton utilisé), les autres pour représenter tes contraintes (que tous tes objets soient dans un carton, qu’un carton ne pas une place infinie,…)) et je donnerais ça à manger à un outil de PLNE.
C’est pas la façon la plus simple de l’envisager, mais tu as une garantie que la solution est la meilleure.
Par contre la modélisation devient de plus en plus compliquée quand tu ajoute des contraintes (ne pas mettre les objets à l’envers, etc).
Il me semble avoir lu que quelqu’un avait résolu des sudoku en utilisant l’algo de “apt” qui est très fort question dépendances (donc contraintes) ça vous semble réalisable ?
Alors pour MisterFreeze, il y a un algorithme qui garantit une solution à epsilon relatif près et polynomiale (j’en ai fait un DS), ça évite de faire le problème discret particulièrement gourmand en mémoire. Par contre pour apt, je ne vois pas. Il est clair que ce pbm ne peut être résolu de manière ewacte (il y a même un code fondé sur ce pbm)