Sur la base des souhaits de l'élève, résolvez le «problème de l'affectation des membres de la classe» comme un problème d'appariement.
Cette fois, nous allons le résoudre comme un problème de correspondance. Pour ce faire, lorsque le nombre requis de membres est n, il est nécessaire d'augmenter le nombre de nœuds pour ce membre à n. De plus, comme il est défini sur Problème de correspondance maximum du poids maximum, le poids w est converti en "40 --w".
import networkx as nx
lst = [['Taprice', 'Comité de discipline', 10], ['Aoba', 'Représentant de classe', 10], ['Kaguya', 'Comité de discipline', 10],
['Chino', 'Représentant de classe', 10], ['miroir', 'Comité de discipline', 10],
['Taprice', 'Représentant de classe', 30], ['Aoba', 'Commission de la bibliothèque', 30], ['Kaguya', 'Commission de la bibliothèque', 30],
['Chino', 'Comité de discipline', 30], ['miroir', 'Représentant de classe', 30]]
need = {"Représentant de classe": 1, "Commission de la bibliothèque": 2, "Comité de discipline": 2}
g = nx.Graph()
lst2 = [(s, f'{c}{i}', 40 - w) for s, c, w in lst for i in range(need[c])]
g.add_weighted_edges_from(lst2)
print(nx.max_weight_matching(g, maxcardinality=True))
production
{('Kaguya', 'Comité de la bibliothèque 1'),
('Chino', 'Représentant de classe 0'),
('Comité de la bibliothèque 0', 'Aoba'),
('Commissaire disciplinaire 0', 'miroir'),
('Commissaire disciplinaire 1', 'Taprice')}
J'ai eu la même solution que l'article original et ce qui précède.
L'appariement est utilisé dans de nombreuses parties de la société. Par exemple, il est introduit sur le site de l'enseignant qui étudie le matching suivant (Stable matching) (https :: //qiita.com/SaitoTsutomu/items/2ec5f7626054f4b4de63)).
Référence: https://www.nii.ac.jp/faculty/informatics/yokoi_yu/
Cette fois, je l'ai résolu avec networkx.max_weight_matching (méthode Edmonds), mais lors de la résolution d'un problème réel, le modèle d'optimisation mathématique peut créer le modèle de manière plus flexible et [peut calculer plus rapidement](https: / /qiita.com/SaitoTsutomu/items/7fd199a95d78a6f3b741).