J'ai des groupes d'élèves qui doivent être répartis dans des salles de classe à capacité fixe (disons, 100 chaises chacune).Algorithme efficace pour créer une distribution idéale de groupes dans des conteneurs avec un dépassement potentiel?
Chaque groupe ne doit être affecté à une seule classe, même si elle est supérieure à la capacité (c.-il peut y avoir un trop-plein, avec des étudiants debout)
je besoin d'un algorithme pour faire les allocations avec minimum débordements et salles de classe sous-capacité.
Un algorithme naïf pour faire cette allocation est horriblement lent quand il y a environ 200 groupes, avec une distribution d'environ la moitié d'entre eux étant inférieure à 20% de la taille de la classe.
Des idées où je peux trouver au moins un bon point de départ pour faire de cet algorithme un éclair rapide?
Merci!
La différence dans mon cas est qu'il n'y a pas de limite supérieure stricte de la capacité, ce qui signifie que je peux décider pour autoriser un dépassement de capacité de 5% si cela permet une simplification et une accélération de l'algorithme. pensées? –
J'ajouterais que cet algorithme glouton donnera une approximation avec un facteur de 2. –