[Algoritmo Java] combinazioni con ripetizioni dipendenti da score

[guylmaster]

Salve a tutti,
ho k intervalli temporali che da qui in poi chiamerò epoche (es. epoca1, epoca2,.., epocak).

Ho inoltre un insieme S di n elementi (e.s: A, B, C, D, E, F).

Ho bisongo di assegnare ad ogni epoca un elemento dell'insieme delle parti di S (powerset(S)). C'è però da aggiungere che ogni elemento di powerset(S) ha uno score, che dipende dall'epoca.

Per esempio A in Epoca1 ha score = 5, ma in Epoca2 ha score = 4.

Io ho bisogno quindi di assegnare per ogni epoca un elemento di powerset(S) però c'è un ulteriore problema. Ho un ulteriroe score, globale su tutte le epoche, che è la somma degli score di ogni epoca meno il numero di cambiamenti tra epoche continue moltiplicato per un parametro lambda. Io voglio effettuare gli assegnamenti in modo da massimizzare questo score globale.

Per capirci meglio facciamo un esempio, mettiamo caso che ho 3 epoche e che per ogni epoca faccio questa determinata scelta:

Epoca1 = AB ed ha score 5;
Epoca2 = A ed ha score 6;
Epoca3 = C ed ha score 4

Avro quindi un campio tra Epoca1 e Epoca2 (ovvero rimuovo B), due cambi tra Epoca3 ed Epoca2 (ovvero rimuovere A e aggiungere C), quindi lo score globale sarà: 6+5+4 - 3 * lambda.
Potrei anche avere la stessa assegnazione per ogni epoca se questa mi massimizza lo score (sono combinazioni con ripetizioni).

Il mio problema è quindi che ho bisogno di trovare l'assegnamento per ogni epoca che i dia il massimo score globale. Essendoci questo numero_di_cambi * lambda non posso semplicemente prendere il massimo locale ad ogni epoca.

Una soluzione, computazionalmente inattuabile, sarebbe di valutare tutte le possibili combinazioni, ma se |S| = 30, |powerset(30)| = 2^30, e credo che quindi avremmo C'(2^30, k) combinazioni con ripetizioni. Il che come già detto è computazionalmente inaccettabile.

Secondo voi c'è un metodo per riuscire comunque a trovare lo score miglire senza però calcolare tutte le combinazioni? cercando sempre di calcolare lo score ottimo e non una sua approsimazione.

Purtroppo non posso scendere di più nei dettagli su come è rappresentato questo score perchè riguarda un argomento troppo specifico che sarebbe quindi difficile da spiegare così sul forum.

Vi ringrazio in anticipo per l'attenzione,
Guylmaster.