Sto cercando di ridurre il mio problema a un problema di flusso massimo in modo da poter eseguire l'algoritmo di flusso massimo su questo problema. Ma ci sono alcune cose che mi mancano mentre trasformo il mio problema.
Il mio problema è:
- ci sono classi con una capacità massima
- ci sono studenti e la loro lista dei desideri che include 5 classi che vogliono
- gli studenti possono selezionare al massimo 5 classi.
E l'obiettivo è:
- per massimizzare il numero di classi iscritte agli studenti.
Se metto studenti e classi come vertici (vedi immagine sopra), poi metti un nodo sorgente s che ha un margine per ogni studente e un nodo sink t che ha un margine per ogni classe, cosa sarà essere i costi di bordo?
- costo di bordo tra le classi e sink node t o
- costo del bordo tra i nodi di origine e gli studenti
Le seguenti ipotesi sono corrette?
Penso che il margine tra gli studenti e il costo delle classi dovrebbe essere 1. Perché uno studente può iscriversi solo una volta a una classe in un termine. Penso che il costo marginale tra le classi e il nodo sink t sarà la capacità massima di una classe.
Non ho un'idea dei costi dei bordi tra il nodo di origine s e i nodi degli studenti.
E alla fine, dopo aver organizzato, dobbiamo solo eseguire l'algoritmo di flusso massimo?