J'ai une boîte avec une certaine longueur, largeur, hauteur.Algorithme de volume de remplissage
J'ai des articles avec différentes longueur, largeur, hauteur.
Existe-t-il un algorithme permettant de déterminer les meilleurs éléments à utiliser dans la boîte?
Ceci est appelé un problème d'empaquetage/coupure de stock/sac à dos, et il est NP dur. En général, vous ne pouvez obtenir une solution approchée en utilisant heuristiques, voir par exemple
http://en.wikipedia.org/wiki/Knapsack_problem
Ce n'est pas le cas. Pouvez-vous expliquer une approximation pour cela? –
Tous ces algorithmes vous aident à optimiser l'espace illimité, au moins dans une dimension. Ce qui est requis est de choisir le meilleur ajustement parmi les articles disponibles en fonction des dimensions de la boîte finie. –
Il ne correspond probablement à aucun d'entre eux exactement. Mais ils sont tous étroitement liés. Par exemple. un emballage avec une poubelle devient un autre problème. Dans la littérature, ce type de problème semble généralement appelé "problème d'emballage tridimensionnel". Une recherche savante donne beaucoup de résultats http://scholar.google.com/scholar?q=box+packing+problem –
Cette une est peut-être pas vraiment de réponse, mais je crois que la réponse est que le problème est sans réponse. Oui, c'est une version d'un problème d'emballage. Mais jetez un oeil à la recherche d'Erich Friedma en 2 dimensions: Il semble que le problème pour les rectangles de taille égale dans le carré n'est toujours pas résolu - Regardez la complexité de certaines de ces solutions!
http://www2.stetson.edu/~efriedma/squinsqu/
http://www2.stetson.edu/~efriedma/rigidrect/
(Le problème se pose un peu différemment, à savoir comment organiser mieux un certain nombre d'éléments à occuper le moins d'espace, par opposition à choisir quels articles. Mais j'attends votre problème réduit à itérer ce type de calcul sur plusieurs combinaisons d'objets)
et une variante 3-d qui semble que très partiellement résolu:.
Vraisemblablement, votre meilleur pari est une heuristique comme Anders le suggère, même si elle sera presque certainement sous-optimale pour presque tous les problèmes. Fait intéressant, la plupart des solutions optimales semblent être fortement irrégulière, donc vous ne les trouverez probablement pas.
Sac à dos Problème sous forme de boîte? –
C'était l'un des problèmes de Maraton Match d'un TCO, si vous vous êtes inscrit dans TCO vous pouvez trouver une bonne solution pour cela (je ne sais pas exactement quand mais je pense qu'il y a environ un an). Non de la solution est la réponse exacte, ils essaient tous d'utiliser un recuit simulé et sth comme ça. –