Ciao a tutti, in un recente concorso pubblico che ho fatto è uscito come traccia la progettazione dell'algoritmo con la traccia che posterò di seguito. Avevo pensato ad un approccio brute force enumerando tutte le soluzioni valide per poi raffinarlo tramite soluzione approssimata ma più efficiente. Il problema è che non sono riuscito proprio a trovare la soluzione per nessuno dei punti elencati. Idee di risoluzione?
Traccia:
Una coppia invita al ricevimento N persone da distribuire su K tavoli nel modo migliore possibile, tenendo conto della reciproca affinità. Assumendo che a ciascun tavolo possano sedersi un numero minimo e massimo di invitati e che l'affinità reciproca tra due invitati sia nota ed espressa da un numero intero (anche negativo), il candidato:
1 - Descriva l'algoritmo più appropriato a determinare la disposizione che massimizza l'affinità complessiva, intesa come somma delle affinità presenti allo stesso tavolo.
2 - Indichi la struttura dati più adeguata ad eseguire l'algoritmo.
3 - Esprima la complessità dell'algoritmo, motivandola
4 - Descriva un algoritmo a complessità inferiore che consenta di determinare una soluzione sub ottimale in tempo minore.