Aide pour une méthode

Bonjour

Si $p$ désigne le demi-périmètre de chaque rectangle, $l$ et $L$ les côtés de la feuille, le nombre maximal de rectangles découpables dans la feuille est, sauf erreur $$l \Big\lfloor \dfrac {L}{p-1} \Big\rfloor +L_{p-1} \Big\lfloor \dfrac {l}{p-1} \Big\rfloor+ \Big\lfloor \dfrac {\min (L_{p-1},l_{p-1})}{p-\max (L_{p-1},l_{p-1})} \Big\rfloor .

$$ (Pour tout $(a,b) \in \mathbb {N \times N^*},\ a:=b \lfloor \frac {a}{b} \rfloor + a_b$ avec $0 \leq a_b <b$).
Cordialement
Paul

Si Zakariyae était capable de comprendre tout ça il ne poserait pas une question comme celle qu'il a posée.
On veut avoir plein de rectangles, le plus possibles, et le périmètre de tous nos rectangles doit avoir une longueur fixée $P$.

Pour un rectangle, quand le périmètre est imposé, plus le rectangle se rapproche d'une forme carrée, plus la surface est grande, et à l'opposé, plus le rectangle se rapproche d'un long ruban, plus la surface est petite.
On va donc chercher au maximum à utiliser des rectangles de largeur 1. Dans l'exemple proposé, le périmètre est 10. Si la largeur vaut 1, la longueur vaut 4.
On va donc essayer de placer un maximum de rectangles 4x1 ( ou 1x4) dans notre feuille de 60x24.
Ici, on a de la chance, 60 et 24 sont tous les 2 des multiples de 4. On peut donc découper notre feuille de 60 bandes horizontales de largeur 1, et caser 6 rectangles 4x1 dans chacune des 60 bandes (60*6=360)
Ou bien, découper notre feuille en 24 bandes verticales de largeur 1, et caser 15 rectangles 1x4 dans chacune des bandes (24*15=360)

Bien évidemment, les 2 calculs donnent le même résultat.

Si on avait par exemple une feuille de 61x23, ce serait un peu plus compliqué, il faudrait envisager 2 scénarios :
- Scénario 1 : mettre plein de rectangles horizontaux 4x1, pour occuper une grande partie de la feuille, le plus possible. Et sur le reste de la feuille, mettre des rectangles verticaux 1x4.
- scénario 2 : inverser la verticale et l'horizontale, on essaye d'abord de mettre un maximum de rectangles verticaux, puis on remplit le reste avec des rectangles verticaux.
Et on compare le nombre de rectangles obtenus avec les 2 scénarios.

Si le périmètre proposé est grand, on va souvent avoir un dernier cas à gérer. Par exemple, on a un périmètre imposé de 100, et on a une feuille de 55x96. On va disposer plein de rectangles de taille 49x1 (ou 1x49) , et à un moment il va nous rester un morceau de la feuille de taille 6x47.
Impossible de placer des rectangles 1x49 ou 49x1 dans ce morceau de feuille.
Impossible également de placer des rectangles 2x48.
Par contre, on peut utiliser ce reste de feuille pour faire 2 rectangles 3x47