Algoritmo ungherese con assegnazioni multiple

Question

Diciamo che ci sono dati N lavori e K lavoratori per fare quei lavori. Ma per alcuni posti di lavoro abbiamo bisogno di 2 dipendenti, mentre per alcuni abbiamo bisogno di uno solo. Anche i dipendenti non possono fare tutti i lavori. Ad esempio, il lavoratore 1 può eseguire lavori 1,2 e 5, mentre non lavori 3 e 4. Inoltre, se assumiamo 1 lavoratore per svolgere il lavoro 1, vogliamo che faccia lavori 2 e 5, poiché l'abbiamo già pagato.

Quindi per esempio diciamo che abbiamo 5 posti di lavoro e 6 lavoratori. Per i posti di lavoro 1,2 e 4 abbiamo bisogno di 2 uomini, mentre per i lavori 3 e 5 ne abbiamo bisogno solo uno. Ed ecco l'elenco dei lavori che ogni lavoratore può fare e il salario che richiede.

Worker 1 can do jobs 1,3,5 and he requires 1000 dollars. 
Worker 2 can do jobs 1,5 and he requires 2000 dollars. 
Worker 3 can do jobs 1,2 and he requires 1500 dollars. 
Worker 4 can do jobs 2,4 and he requires 2500 dollars. 
Worker 5 can do jobs 4,5 and he requires 1500 dollars. 
Worker 6 can do jobs 3,5 and he requires 1000 dollars. 

Dopo piccolo calcolo e il pensiero logico possiamo concludere che dobbiamo assumere lavoratori 1,3,4 e 5, il che significa che il salario minimo che dobbiamo pagare è: 1000 + 1500 + 2500 + 1500 = 5500 dollari.

Ma come possiamo trovare un algoritmo efficiente che produrrà tale importo? Questo mi ricorda in qualche modo l'Algoritmo Ungherese, ma tutti questi vincoli aggiuntivi mi impediscono di applicarlo.

Answer 1

Possiamo rappresentare uno stato di tutti i lavori come un numero in un sistema ternario (2-due persone rimanenti, 1 persona rimanente e 0 se già fatto). Ora possiamo calcolare f (maschera, k) = il costo più piccolo per assumere alcuni lavoratori tra i primi k in modo tale che lo stato dei lavori rimanenti sia la maschera. Le transizioni sono le seguenti: o andiamo a (maschera, k + 1) (non assumendo il lavoratore attuale) o andiamo a (new_mask, k + 1) (in questo caso paghiamo a questo lavoratore il suo stipendio e gli permettiamo di fare tutto il lavori che può). La risposta è f (0, K).

La complessità del tempo è O (3^N * K * N).

Ecco un'idea su come ottimizzarlo ulteriormente (ed eliminare il fattore N). Supponiamo che la maschera corrente sia mask e che l'uomo possa eseguire lavori da un altro mask'. Potremmo semplicemente aggiungere mask a mask', ma c'è un problema: le posizioni in cui era 2 nello mask e nello 1 in mask' verranno interrotte. Ma possiamo aggiustare: per ogni maschera, precompiliamo una maschera binaria allowed_mask che contiene tutte le posizioni in cui la cifra non è 2. Per ogni uomo e per ogni allowed_mask possiamo precalorizzare il valore mask'. Ora ogni transizione è solo un'aggiunta:

for i = 0 ... k - 1 
    for mask = 0 ... 3^n - 1 
     allowed_mask = precomputed_allowed_mask[mask] 
     // make a transition to (i + 1, mask + add_for_allowed_mask[i][allowed_mask]) 
     // make a transition to (i + 1, mask) 

Nota che ci sono solo 2^n maschere consentite. Quindi la complessità temporale di questa soluzione è O(3^N * N + T * 2^N * K * N + T * 3^N * K) (il primo termine è per il precalcolo di maschere consentite per tutte le maschere ternarie, il secondo è per il precalcolo mask' per tutte le maschere e le persone consentite e l'ultimo è per dp stesso).