Węgierski algorytm z wieloma zadaniami

Question

Załóżmy, że otrzymaliśmy N zadań i pracowników K do wykonywania tych zadań. Ale do niektórych prac potrzebujemy 2 pracowników, podczas gdy dla niektórych potrzebujemy tylko jednego. Również pracownicy nie mogą wykonywać wszystkich zadań. Na przykład pracownik 1 może wykonywać zadania 1,2 i 5, a nie zadania 3 i 4. Także jeśli zatrudniamy pracownika 1 do wykonania zadania 1, to chcemy, aby wykonał zadania 2 i 5, ponieważ już mu zapłaciliśmy.

Załóżmy na przykład, że mamy 5 stanowisk pracy i 6 pracowników. Do zadań 1,2 i 4 potrzebujemy 2 mężczyzn, natomiast do zadań 3 i 5 potrzebujemy tylko jednego. A oto lista zadań, które może wykonać każdy pracownik, i płaca, której potrzebuje.

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. 

Po trochę obliczeń i logicznego myślenia, możemy stwierdzić, że mamy do zatrudniania pracowników 1,3,4 i 5, co oznacza, że ​​płaca minimalna musimy zapłacić to: 1000 + 1500 + 2500 + 1500 = 5500 dolarów.

Ale jak możemy znaleźć skuteczny algorytm, który wyprowadzi tę kwotę? To jakoś przypomina mi węgierski algorytm, ale wszystkie te dodatkowe ograniczenia uniemożliwiają zastosowanie go.

Answer 1

Możemy reprezentować stan wszystkich zleceń jako liczbę w systemie trójskładnikowym (2-dwie osoby pozostały, pozostała 1-osoba i 0, jeśli jest już wykonana). Teraz możemy obliczyć f (maska, k) = najmniejszy koszt zatrudnienia niektórych pracowników spośród pierwszych k w taki sposób, że stan pozostałych zadań jest maskowany. Przejścia są następujące: albo przechodzimy do (maska, k + 1) (nie zatrudniamy obecnego pracownika) lub przechodzimy do (new_mask, k + 1) (w tym przypadku płacimy temu pracownikowi jego pensję i pozwalamy mu wykonywać wszystkie miejsca pracy, które może). Odpowiedź brzmi f (0, K).

Złożoność czasu wynosi O (3^N * K * N).

Oto pomysł na dalszą optymalizację (i pozbycie się współczynnika N). Załóżmy, że obecna maska ​​to mask, a człowiek może wykonywać zadania od innego mask'. Moglibyśmy po prostu dodać mask do mask', ale jest jeden problem: pozycje, w których był 2 w mask i 1 w mask' zostaną zerwane. Ale możemy naprawić: dla każdej maski, wstępnie obliczmy binarną maskę allowed_mask, która zawiera wszystkie pozycje, w których cyfra nie jest 2. Dla każdego mężczyzny i dla każdego allowed_mask możemy wstępnie obliczyć wartość tego mask'. Teraz każde przejście jest tylko jeden dodatek:

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) 

Należy pamiętać, że istnieją tylko 2^n masek. Tak więc czas złożoności tego rozwiązania to O(3^N * N + T * 2^N * K * N + T * 3^N * K) (pierwszy termin jest przeznaczony do wstępnego obliczania dozwolonych_masek dla wszystkich trójskładnikowej maski, drugi do wstępnego obliczenia mask' dla wszystkich dozwolonych_masek i ludzi, a ostatni dotyczy samego dp).