Algorithmique : Remplissage d'un conteneur de manière optimi

[blitz37]

Bonsoir,

J'aurais besoin de votre aide pour résoudre un problème pour l'une de mes applications android.
Je vous rassure, j'ai juste besoin d'un algorithme en pseudo-code (ou du moins de pistes) et je me charge des détails.



En entrée :
- un cadre (en noir) de dimension variable
- un nombre défini de cadres carrés (en rouge) dont la dimension idéale est à définir.

En sortie (à déterminer) :
- dimensions des cadres rouges (tous identiques)
- nombre de cadres rouges en hauteur et en largeur.

Le but est donc de placer tous les cadres de manière idéale dans le conteneur en jouant sur leur dimensions et le nombre de cadres que l'on place en largeur et hauteur. Comme sur l'image, si le nombre de cadres ne tombe pas rond, il se peut qu'il manque un (ou plusieurs) cadre(s) pour remplir le conteneur.

Donc la partie complexe est de trouver le nombre de cadres carrés à placer en hauteur/largeur de manière à laisser le moins de vide possible.
Puis en suite en déduire la largeur d'un cadre.


Merci d'avance pour vos avis.
Si vous avez besoin de précisions, je reste à votre disposition.

[Valentin03]

Bonsoir,
J'aurais besoin de votre aide pour résoudre un problème pour l'une de mes applications android.
Je vous rassure, j'ai juste besoin d'un algorithme en pseudo-code (ou du moins de pistes) et je me charge des détails.

En entrée :
- un cadre (en noir) de dimension variable
- un nombre défini de cadres carrés (en rouge) dont la dimension idéale est à définir.
En sortie (à déterminer) :
- dimensions des cadres rouges (tous identiques)
- nombre de cadres rouges en hauteur et en largeur.
Le but est donc de placer tous les cadres de manière idéale dans le conteneur en jouant sur leur dimensions et le nombre de cadres que l'on place en largeur et hauteur. Comme sur l'image, si le nombre de cadres ne tombe pas rond, il se peut qu'il manque un (ou plusieurs) cadre(s) pour remplir le conteneur.
Donc la partie complexe est de trouver le nombre de cadres carrés à placer en hauteur/largeur de manière à laisser le moins de vide possible.
Puis en suite en déduire la largeur d'un cadre.

Merci d'avance pour vos avis.
Si vous avez besoin de précisions, je reste à votre disposition.

Juste une remarque: pour remplir de cadre au maxi, il faut réduire l'espacement au maxi: Soit 1 pixel
Mais si tu espace que d'un pixel sur un petit écran (mobile), tes cadres risquent d'apparaîtres se touchants.
Tu devrais peut-être faire un essai avec deux cadres pour voir l'espacement mini acceptable

[blitz37]

Juste une remarque: pour remplir de cadre au maxi, il faut réduire l'espacement au maxi: Soit 1 pixel
Mais si tu espace que d'un pixel sur un petit écran (mobile), tes cadres risquent d'apparaîtres se touchants.
Tu devrais peut-être faire un essai avec deux cadres pour voir l'espacement mini acceptable

Comme je l'ai dis, je m'occupe des détails, les cadres sont en réalités d'autres conteneurs avec des padding etc. Pas de soucis là dessus.
Là j'ai juste simplifié le problème pour que chacun puisse comprendre.

[blitz37]

Si on essaye de modéliser mathématiquement, ça donnerais qqch comme ça :

Variables connues :
Soient l et h respectivement la largeur et hauteur du conteneur.
Soit n le nombre de cadres.

Variables à déterminer :
Soient x et y respectivement le nombre de cadres en largeur et hauteur.
Soit c la largeur/hauteur d'un cadre.

On aurait donc le système suivant :
x * y >= n
x * c bon en réfléchissant, j'aurais pu l'obtenir direct ça ><

Donc la avec un calcul de dérivé, on a la valeur de c. Mais le problème il faudrait prendre en compte le faite que x, y et n sont des entiers. et je sais pas comment faire ça

[blitz37]

Anyone ?...

[leon1789]

On cherche donc à minimiser la valeur :
A = (l - x*c) * h + (h - y*c) * (x*c) + (x*y - n) * c²
= (l*h - n*c²) -> bon en réfléchissant, j'aurais pu l'obtenir direct ça ><

Je ne pense pas que cela soit la bonne piste car ton n (le nombre de carrés rouge) est idéalement un produit de deux entiers qui ne sont pas n'importe comment.

Personnellement, j'ai pensé à des calculs
soit d'un pgcd (si les dimensions du cadre noir sont des entiers, voire des rationnels, et là, il n'y aurait pas de perte),
soit d'un développement en fraction continue (si les dimensions du cadre noir sont des irrationnels, et là, en augmentant le nombre de carré rouge, on pourrait rendre la perte aussi petite que l'on veut, sans pouvoir l'annuler),
mais je n'ai pas trop réfléchi.

Veux-tu qu'on prenne un exemple pour voir ? On se donne quoi pour les dimensions du cadre noir ?
Il y a-t-il des contraintes supplémentaires sur les cartons rouges ?

[blitz37]

Les dimensions du conteneur noir sont des entiers : c'est la taille de l'écran donc par exemple 1280 × 768 px.

Pour les cadres rouges, à part le faite qu'ils doivent être carrés, et que l'on doit en placer un nombre défini, rien.

Pour le PGCD ça m’intrigue, je ne vois pas trop comment tu compte faire (à vrai dire le PGCD ça remonte à loin pour moi :p) mais oui j'attends de voir.

[leon1789]

Les dimensions du conteneur noir sont des entiers : c'est la taille de l'écran donc par exemple 1280 × 768 px.

le pgcd, c'est le plus diviseur commun : ici le pgcd de 1280 et 768, c'est 256 ! (256, pas étonnant, c'est de l'informatique :ptdr: )
De nos jours, les calculettes propose ce calcul de pgcd. Je ne t'explique pas comment on le calcule efficacement "à la main", sauf si tu en as besoin...

Conclusion : si tes carrés rouges font de 256 px de coté, alors tu en mettras 1280 / 256 = 5 colonnes et 768 / 256 = 3 rangées (...et il n'y aura aucune perte, comme je te disais).

Tu comprends pourquoi il faut prendre un diviseur commun à 1280 et 768 ?

Tu ne pourras pas avoir des carrés plus gros que 256 px sans créer une perte (car on a pris le plus grand diviseur commun : pgcd)

[blitz37]

Ouai mais justement ça résout pas mon problème ça. Moi je DOIS en placer en nombre N tout en minimisant l'espace perdu.

[leon1789]

Ouai mais justement ça résout pas mon problème ça. Moi je DOIS en placer en nombre N tout en minimisant l'espace perdu.

ha, le nombre de carrés rouges est fixé (à N) ! Je n'avais pas compris (pourtant, tu l'as bien dit dans ton sujet :girl2: ). Et N vaut quoi par exemple ?

[blitz37]

Et N vaut quoi par exemple ?

ça dépend du contexte mais ça peut être 10, 77 ou même 1000 ... N peut vraiment prendre n'importe quelle valeur

[leon1789]

Vu que les carrés rouges vont être empilés horizontalement ou verticalement, il faut trouver deux entiers A, B tels que

et
soit le plus grand possible

(où 1280 / A désigne le quotient de la division euclidienne de 1280 par A, idem pour 768 / B) .

Exemples :

Code: Tout sélectionner

                     n = 1, A = 1, B = 1, c = 768


                     n = 2, A = 2, B = 1, c = 640


                     n = 3, A = 3, B = 1, c = 426


                     n = 4, A = 3, B = 2, c = 384


                     n = 5, A = 3, B = 2, c = 384


                     n = 6, A = 3, B = 2, c = 384


                     n = 7, A = 4, B = 2, c = 320


                     n = 8, A = 4, B = 2, c = 320


                     n = 9, A = 5, B = 2, c = 256


                    n = 10, A = 5, B = 2, c = 256


                    n = 11, A = 5, B = 3, c = 256


                    n = 12, A = 5, B = 3, c = 256


                    n = 13, A = 5, B = 3, c = 256


                    n = 14, A = 5, B = 3, c = 256


                    n = 15, A = 5, B = 3, c = 256


                    n = 16, A = 6, B = 3, c = 213


                    n = 17, A = 6, B = 3, c = 213


                    n = 18, A = 6, B = 3, c = 213


                    n = 19, A = 6, B = 4, c = 192


                    n = 20, A = 6, B = 4, c = 192


                    n = 21, A = 6, B = 4, c = 192


                    n = 22, A = 6, B = 4, c = 192


                    n = 23, A = 6, B = 4, c = 192


                    n = 24, A = 6, B = 4, c = 192


                    n = 25, A = 7, B = 4, c = 182


                    n = 26, A = 7, B = 4, c = 182


                    n = 27, A = 7, B = 4, c = 182


                    n = 28, A = 7, B = 4, c = 182


                    n = 29, A = 8, B = 4, c = 160


                    n = 30, A = 8, B = 4, c = 160


                    n = 31, A = 8, B = 4, c = 160


                    n = 32, A = 8, B = 4, c = 160


                    n = 33, A = 8, B = 5, c = 153


                    n = 34, A = 8, B = 5, c = 153


                    n = 35, A = 8, B = 5, c = 153


                    n = 36, A = 8, B = 5, c = 153


                    n = 37, A = 8, B = 5, c = 153


                    n = 38, A = 8, B = 5, c = 153


                    n = 39, A = 8, B = 5, c = 153


                    n = 40, A = 8, B = 5, c = 153


                    n = 41, A = 9, B = 5, c = 142


                    n = 42, A = 9, B = 5, c = 142


                    n = 43, A = 9, B = 5, c = 142


                    n = 44, A = 9, B = 5, c = 142


                    n = 45, A = 9, B = 5, c = 142


                    n = 46, A = 10, B = 5, c = 128


                    n = 47, A = 10, B = 5, c = 128


                    n = 48, A = 10, B = 5, c = 128


                    n = 49, A = 10, B = 5, c = 128


                    n = 50, A = 10, B = 5, c = 128



Pour trouver c, tu veux une formule close ou un algorithme ?

[blitz37]

Je vois pas trop comment tu définis A et B là... car faut pas oublier que la dimension de l'écran est variable. Et je ne peux pas me permettre de tester tous les couples A * B <= n quand n est grand, il y en a une infinité.

[leon1789]

A est le nombre de carrés rouges mis horizontalement
B est le nombre de carrés rouges mis verticalement.
Il se peut que A.B soit strictement supérieur à n , cela signifie qu'il y aura des carrés "fantômes" (comme dans ton exemple présentant ton sujet où A = 4 et B = 5 , n= 19).

En ce qui concerne les couples (A,B), il y n'en a pas une infinité :
A ne dépasse pas 1280 et B ne dépasse pas 768.

[blitz37]

En ce qui concerne les couples (A,B), il y n'en a pas une infinité :
A ne dépasse pas 1280 et B ne dépasse pas 768.

1. cette résolution est un exemple on peut imaginer de la full HD ou même plus.
2. dans cette exemple, n pourrait donc valoir 1 million. Et il doit y avoir 1M * 1M / 2 = infini couples (A,B)

[leon1789]

Oui, c'est pour l'instant, très fastidieux.

Dit plus simplement, il faut trouver c le plus grand possible tel que

où 1280/c représente le quotient de la division euclidienne de 1280 par c, idem pour 768/c.

Ici, on a forcément .

Trouver un tel c est très rapide en machine, même en remplaçant 1280 et 768 par des nombres de l'ordre du million. Et plus n est grand, plus le calcul est rapide.

[leon1789]

Dit plus simplement, il faut trouver c le plus grand possible tel que

où 1280/c représente le quotient de la division euclidienne de 1280 par c, idem pour 768/c.

Ici, on a forcément .

Trouver un tel c est très rapide en machine (expérimentalement, il vaut mieux partir du majorant M, et chercher c à reculons(*)), même en remplaçant 1280 et 768 par des nombres de l'ordre du million. Et plus n est grand, plus le calcul est rapide.



(*) NE PAS OUBLIER que est une fonction décroissante . :lol3:

[leon1789]

Je pense que ma première proposition est meilleure en terme de complexité :

Vu que les carrés rouges vont être empilés horizontalement ou verticalement, il faut trouver deux entiers A, B tels que

et
soit le plus grand possible

où 1280 / A désigne le quotient de la division euclidienne de 1280 par A, idem pour 768 / B.

En effet, ce n'est pas tous les couples (A,B) qu'il faut tester, car :
- pour A donné, on prendra B = partie entière supérieure de n/A ;
- pour B donné, on prendra A = partie entière supérieure de n/B .

Ainsi, il suffit de concentrer la recherche sur A ou sur B. Et pour que la recherche soit efficace, il faut trouver des bornes adaptées sur A ou sur B...

[leon1789]

Dit plus simplement, il faut trouver c le plus grand possible tel que

où 1280/c représente le quotient de la division euclidienne de 1280 par c, idem pour 768/c.

Ici, on a forcément .

Trouver un tel c est très rapide en machine (expérimentalement, il vaut mieux partir du majorant M, et chercher c à reculons (*)), même en remplaçant 1280 et 768 par des nombres de l'ordre du million. Et plus n est grand, plus le calcul est rapide.


(*) NE PAS OUBLIER que est une fonction décroissante . Donc, quand on cherche c "à reculons" à partir de M, on s'arrête dès qu'on trouve le premier c vérifiant !



Cela dit, je pense que ma première proposition est meilleure en terme de complexité :

Vu que les carrés rouges vont être empilés horizontalement ou verticalement, il faut trouver deux entiers A, B tels que

et
soit le plus grand possible

où 1280 / A désigne le quotient de la division euclidienne de 1280 par A, idem pour 768 / B.

En effet, ce n'est pas tous les couples (A,B) qu'il faut tester, car :
- pour A donné, on prendra B = partie entière supérieure de n/A ;
- pour B donné, on prendra A = partie entière supérieure de n/B .

Ainsi, il suffit de concentrer la recherche sur A ou sur B. Et pour que la recherche soit efficace, il faut trouver des bornes adaptées sur A ou sur B...

[leon1789]

Ok, ça s'améliore encore : il n'y a plus besoin de boucle !

Je suppose que le rectangle noir a une largeur horizontale L une hauteur verticale H.
De doute manière, ce n'est pas gênant car il suffit d'échanger les dimensions du rectangle noir pour revenir à cette situation.

Alors,
B vaut la partie entière inférieure (choix 1)
ou la partie entière supérieure (choix 2) de ,
ensuite A = partie entière supérieure de
et enfin c = min( L/A, H/B ) (:!: ici, / désigne le quotient des divisions euclidiennes)

Il faut faire le choix 1 ou le choix 2 pour obtenir le c le plus grand possible, mais faire ce choix demande des calculs instantanés... même avec des nombres astronomiques :++: