Bonjour,

Peux tu donner quelques exemples rencontrés en pratique : taille du
panneau,
et liste des resctangles ?

PL

On 1 août, 23:02, "Bernard Bordja" <bern...@localhost.localdomain>
wrote:

Le Tue, 31 Jul 2007 00:08:13 +0200, Fabien LE LEZ a écrit:

Pour la résolution en elle-même : ce problème est proche de celui du
sac à dos. Il existe une méthode simple qui permet d'obtenir de très
bonnes solutions, et qui je crois s'appelle l'algorithme gourmand.
Commence par trier tes rectangles par ordre décroissant de surface.
Place le plus grand dans un coin (Note que tu as deux solutions, sauf
si c'est un carré). Puis essaie les différentes solutions pour le
deuxième, puis le troisième, etc.
Ça ressemble à une recherche exhaustive, et ça demande pas mal de
calculs et d'essais, mais vu le peu de rectangles en cause et la
puissance des processeurs actuels, en pratique, ça marche bien.

J'avais trouvé l'algo du sac à dos dans "Algorithmes en langage C" par
Robert Sedgewick et partant de là, j'avais commencé à réfléchir à une
solution qui se rapprochait de l'algorithme gourmand sans le savoir. Cette
solution me semblait par trop naïve. Apparemment, je vais devoir ressortir
mes notes et les reprendre dans le bon sens grâce à vos lumières et avec
google mon ami :-)

Encore merci à vous tous !

B. Bordja