Dimensione fissa impostata per contenere il numero massimo di determinati insiemi

Question

ho circa 1000 insiemi del formato < = 5 numeri contenenti da 1 a 100.

{1}, {4}, {1,3}, {3,5,6}, {4,5,6,7}, {5,25,42,67,100} ... 

È possibile trovare una serie di dimensioni 20 che contiene la numero massimo di set dati?

Il controllo di ciascuno dei set 100!/(80!*20!) non è efficiente.

Answer 1

Non sono sicuro che sia NP completo.

Consideriamo il problema correlato in cui otteniamo una ricompensa di x per ogni set, ma dobbiamo pagare un prezzo di y per ogni numero che vogliamo consentire. (Un insieme paga solo la ricompensa se tutti i numeri in esso contenuti sono stati pagati per.)

È possibile risolvere questo tipo di problema utilizzando la max flow algorithm da:

1. La creazione di un nodo di origine
2. Impostazione un nodo di destinazione
3. Impostazione di un nodo per ogni set
4. Impostazione di un nodo per ogni numero
5. Aggiungere bordo dalla sorgente ad ogni insieme con capacità x
012.
6. aggiungere un margine da ogni numero dest con capacità y
7. Per ciascun numero una in serie s, aggiungere un margine da s ad una con capacità infinita

Soluzione del problema di flusso massimo in questo grafico (dalla sorgente al nodo di destinazione) trova un costo di taglio minimo c.

L'importo netto di denaro che faremmo sarebbe N.x-c (dove N è il numero di serie).

Se possiamo scegliere y (ad esempio per bisezione) in modo tale che abbiamo selezionato esattamente 20 numeri, allora siamo riusciti a risolvere per il numero massimo di serie con 20 numeri.