Il tuo problema è, credo, NP-completo, quindi a meno che il numero di set con cui hai a che fare sia piccolo, non esiste una soluzione accurata garantita che verrà eseguita in un tempo realistico. Potresti essere in grado plausibilmente di ottenere risultati accurati con una ricerca globale (in pratica elencando tutte le possibili combinazioni di insiemi e controllando quale dà i migliori risultati) per un massimo di circa 20 insiemi, ma non problemi molto più grandi di quello.
Il tuo requisito di ridurre al minimo la duplicazione lo rende leggermente diverso dal problema di copertina impostato come collegato nei commenti, e può essere che la soluzione approssimativa descritta in quell'articolo (essenzialmente iterando il processo di scegliere la scelta che ti porta più vicino ad un soluzione fino a quando non hai una copertura completa) non funziona abbastanza bene per te in quanto ignora completamente il tuo requisito extra.
Se questo è il caso, adotterei un approccio per utilizzare questo algoritmo per generare una prima soluzione candidata, e quindi usando ricottura simulata in modo simile a come viene applicata al problema del commesso viaggiatore come fase di ottimizzazione finale. Penso che questo dovrebbe portare a qualcosa di simile a una soluzione ottimale per la maggior parte del tempo.