Conseils avec l'algorithme d'empaquetage des mêmes rectangles dans le rectangle avec limitation de la guillotine?

Question

J'ai été chargé de construire un programme pour une connaissance, qui calcule la meilleure façon d'ajuster les pages du livre sur un grand papier à imprimer et à couper. En pratique, cela signifie que je dois trouver le meilleur moyen de disposer des rectangles de dimensions identiques (les pages) dans un rectangle donné (le papier d'impression) de telle sorte que les découpes de guillotine puissent être utilisées pour séparer toutes les pages sans ruiner tout.

Si l'un d'entre vous peut orienter mes recherches vers une meilleure direction, soit en me donnant des liens ou une formulation plus précise du nom du problème (terminologie), ce serait génial. J'ai réduit la terminologie à un problème d'empaquetage 2D avec des rectangles identiques dans un rectangle et des limites de guillotine.

Answer 1

Je faisais face à un problème similaire et finalement obtenu la réponse à mon problème par moi-même. En supposant que la longueur est supérieure à la largeur pour les deux rectangles (plus petits et plus grands), voici les possibilités lorsque vous essayez d'emballer des rectangles plus petits sur le plus grand. Laisser la longueur du rectangle le plus grand être L, sa largeur doit être B et la longueur et la largeur des plus petits rectangles doivent être respectivement l et b. Cas 1: emballez les plus petits rectangles de manière à ce que leurs longueurs soient parallèles à la largeur du plus grand rectangle jusqu'à ce que vous manquiez d'espace. Ensuite, essayez l'inverse (longueur du plus grand rectangle parallèle aux longueurs du plus petit) sur l'espace disponible. Cas 2: emballez les plus petits rectangles de sorte que leurs longueurs soient parallèles à la longueur du plus grand rectangle jusqu'à ce que vous manquiez d'espace. Ensuite, essayez l'inverse (longueur du rectangle le plus grand parallèle aux largeurs du plus petit) sur l'espace disponible.

Prenez le maximum des cas 1 et 2 pour obtenir le nombre maximum de rectangles plus petits qui peuvent être empaquetés sur un plus grand. Trouvez le code python 3 de la mise en œuvre ici: http://geekzonelive.blogspot.in/2016/06/packing-similar-small-rectangles-into.html

Answer 2

Ceci est un classique packing problem réductible à knapsack problem. La version populaire est appelée Cutting stock problem car elle implique des procédés industriels de découpe de papiers (comme votre problème). Le problème est NP dur, et on utilise des méthodes de programmation en nombres entiers (optimisation combinatoire) pour les résoudre. Il y a des problèmes d'emballage plus généraux sur l'article d'emballage. Je pense que vous trouverez plus de rectangles here.