Ajustement n nombre de rectangles de n L & W en n nombre de rectangles probablement grands

Question

J'ai n nombre de rectangles (petits) de longueur et de largeur n et n nombres grands rectangles de longueur et de largeur n. En bref, il y a une liste de rectangles à installer et une autre liste de rectangles dans laquelle ces rectangles seront ajustés. J'étudie à propos de divers algorithmes d'ajustement de paquet et je sais que diverses questions ont été posées pour la même chose mais ne peuvent pas m'aider avec ce type de problème.

Ma question est comment choisir de façon optimale le grand rectangle à choisir en premier et comment remplir de petits rectangles sans chevauchement et zone de gaspillage minimum, jusqu'à ce que tous les petits rectangles soient ajustés dans les grands rectangles. C'est OK, si les grands rectangles restent vides quand tous les petits rectangles sont ajustés.

S'il vous plaît aidez-moi par où commencer et si la question ne donne pas beaucoup de clarté alors s'il vous plaît faites le moi savoir. Mon but est d'écrire un algorithme pour le même problème.

Answer 1

Pour répondre à la question en partie, le problème à l'étude est NP-hard car il contient le problème Partition comme sous-problème.