Existe-t-il un algorithme glouton pour résoudre ce problème: Je n'ai pas de télévision, chaque téléviseur a une hauteur et une largeur. r acheteurs viennent en même temps à mon magasin. Chacun veut une télévision avec une hauteur minimale connue et une largeur minimale.Trouver une solution optimale gourmande
Quel est le nombre maximum de commandes que je peux remplir?
Le problème est lié à la correspondance maximale des graphes. Vous créez un graphique avec des noeuds côté gauche représentant des clients et des noeuds côté droit représentant des téléviseurs. Un bord entre le nœud du côté gauche et le nœud du côté droit représente le fait que le client peut acheter la télévision (ce qui signifie que la télévision satisfait à l'exigence de largeur de largeur minimale du client). Vous devez maintenant trouver la correspondance maximale dans le graphique.
Et chaque téléviseur a un prix? Et vous voulez maximiser les revenus? Sinon, vous pouvez simplement vendre à n'importe quel client TV avec des exigences minimales. – ipoteka
@ipoteka Le problème est qu'il n'y a pas de commande sur les téléviseurs car les proportions ne sont pas fixes. Considérez que vous avez un téléviseur 5x3 et un téléviseur 3x4. Le client 1 veut un téléviseur avec minWidth = 3 et minHeight = 0. Vous lui donneriez probablement le téléviseur 3x4. Mais si le client 2 veut un minWidth = 0 et minHeight = 4 TV, vous êtes coincé. Si vous aviez donné l'autre téléviseur au client 1, vous auriez pu exécuter les deux commandes. Et c'est exactement la raison pour laquelle je doute qu'il existe un algorithme glouton pour cela. –