Idees pour resoudre un probleme

La question :

Bonjour,

Je recherche une ligne directrice pour trouver un algo efficace pour
resoudre le probleme suivant:

"Etant donne une liste de rectangles (decrit par leur longueur et leur
largeur), trouver un rectangle dont l'aire est la plus petite possible
et recouvrant tous les rectangles donnes en entree."

A part le methode basique d'enumerer toutes les combinaisons
possibles, je seche.

Est ce que quelqu'un aurait une bonne idee ?

Merci

Poser votre question sur le forum Programmation

Les 5 réponses :

Poser votre question sur le forum Programmation

Questions similaires :

Petit problème de géographie.

Bonjour. "dvanhee" a écrit dans le message de news J'avais ébauché un truc de ce genre il y a longtemps, à base de géométrie constructive... De mémoire: on parcours les points du contour (polygone) en considérant pour chaque nouveau point: - le triangle qu'il forme avec les...

Autre problème graphisme

Bonjour à tous Me revoilà avec un nouveau petit problème : J'ai une image couleur codée sur 24 bits (8 bits pour le Rouge, 8 bits pour le Vert et 8 bits pour le Bleu) Je dois arriver à réduire le nombre de couleurs dans l'image finale car chaque pixel est codé sur un nombre de bits variable de 1 bit...

Génération uniforme de solutions d'un problème NP-difficile

Bonjour, Je veux générer une solution d'un problème NP-difficile avec une probabilité uniforme. Le problème NP-difficile se présente sous la forme d'un vecteur booléen de longueur n vérifiant des contraintes de cardinalité de la forme (x_1 + x_3 + x_6 <= 2, respectivement ==, >=) Comme je ne vois...

problème de 3 couleurs

Bonjour messieurs, Voici un algorithme pour 3 couleurs : Soit G un graphe planaire qui a 3-clique comme clique maximum, on note chaque 3-clique par triangle. G contient plusieurs triangles, placer les un à coter des autres, ou séparer par des arrêts. 1) Zone de colorisation obligatoire simple : Si...

probleme d'emploi du temps.

Bonjour, Je m'intéresse à l'aspect théorique des algorithmes permettant d'obtenir un emploi du temps en fonction de contraintes. J'ai bien trouvé quelques références éparses sur google, le problème semble NP-complet, peut se résoudre par le coloriage d'un graphe (cela n'est pas clair pour...