Java: Comment dessiner des images sur la plus petite surface possible?

Question

Disons que j'ai 256 images avec une taille moyenne de 70x150 (Donc, taille si variable). Et j'ai une instance Graphic (créée à partir d'une image tamponnée avec une taille donnée) sur laquelle je veux dessiner les images. Mais je veux les dessiner à la surface la plus basse possible. Donc, pas simplement dans une grille, mais vraiment perplexe l'un dans l'autre. Mais !: ils ne peuvent pas se chevaucher.

Peut-être que c'est quelque chose qu'un cerveau humain peut gérer.
Il vaut la peine de lui demander, je pense ....

Merci à l'avance,
Martijn

Par exemple:

+------++------+ 
|  ||  | 
| img1 || img2 | 
|  |+------+ 
|  |+-----------------+ 
+------+|     | 
+---+ |     | 
| 3 | |     | 
| | | img 4  | 
+---+ |     | 
     |     | 
     +-----------------+ 

Answer 1

Cette question a été posée: What algorithm can be used for packing rectangles of different sizes into the smallest rectangle possible in a fairly optimal way?

Une bonne enquête, d'une réponse précédente, est disponible à: http://www.csc.liv.ac.uk/~epa/surveyhtml.html

Answer 2

Fondamentalement, vous demandez une solution à un knapsack problem.

Il n'y a aucun algorithme optimal pour un problème de taille Knapsack arbitraire, car il est le problème NP-dur.

Il y a abondance d'algorithmes sous-optimaux:

• algorithmes de recherche Greedy.
• espace de recherche Heuristique algorithmes de voyage, comme A* famille
• algorithmes de recherche, tels que Stochastic simmulated annealing, genetic algorithms