Problem stopnia satysfakcji - programowanie zachłanne

Jakiś pomysł na następujący problem?

Mamy N zabawek, które należy rozdać N dzieciom. Każde dziecko ocenia każdą z zabawek w skali od 1 do N. Jeśli dziecko na przykład dostanie zabawkę, której dało ocenę N, to jego stopień zadowolenia wynosi N. Opracuj taki algorytm zachłanny żeby suma stopni zadowolenia była optymalna.

-1 za mylący tytuł. Myślałem, że będą tutaj jakieś filozoficzne rozważania.

:/

Problem można sprowadzić do problemu wyznaczania maksymalnego przepływu w grafie, jednak otrzymana złożoność będzie średnio satysfakcjonująca (nawet przy wydajnym push and relabel, który działa ze złożonością O(V²*E), gdzie u nas E byłoby rzędu V ²).

Edit: Ok, nie przeczytałem, że to ma być algorytm zachłanny. W takim razie przechodzisz po prostu po kolejnych dzieciach i każdemu z nich próbujesz dać jak najlepszy dla niego prezent (o ile nie został wcześniej przyznany).

Pseudokod:

int[] prezenty = new int[N];
int[,] oceny = new int[N,N];

inicjalizacjaTablicyOceny(oceny); //pierwszy indeks numer dziecka, drugi numer prezentu
inicjalizacjaTablicyPrezenty(prezenty); //wypelnij wartosciami -1, ew. nullable i wtedy null
foreach (dziecko d)
{
      znajdz nieprzyznany prezent p o najwyzszej ocenie dziecka d
      prezenty[p]=d; //przyznaj prezent p dziecku d
}
return prezenty; //tablica zawierająca numer dziecka, ktore otrzymalo prezent

Oczywiście algorytm zachłanny może zwrócić rozwiązanie nieoptymalne w przeciwieństwie do push and relabel.

W porządku, dzięki wielkie. Podoba mi się ten algorytm przepływowy. Co do zachłannego, to sam na niego z początku wpadłem, ale myślałem, że jest jeszcze jakiś bardziej optymalny.

Problem w tym, że oba rozwiązania nie spełniają warunku zadania:

Opracuj taki algorytm zachłanny żeby suma stopni zadowolenia była optymalna.

@mateusz2813 podał dwa algorytmy:

• jeden optymalny, ale niezachłanny,
• drugi zachłanny, ale nieoptymalny,
  ;]
  No chyba, że jednak ten zachłanny jest optymalny (optymalny w sensie jakości wyniku, a nie złożoności obliczeniowej).

Abstrahując od zachłanności, co byście powiedzieli na sprowadzenie zadania do problemu kojarzenia małżeństw?