[Algorytmika] Pokrycie zbioru podzbiorami

Problem jest następujący:

Należy w zbiorze liczb n i z określonym zestawem jego podzbiorów znaleźć jak najmniejszą ich grupę, żeby po zsumowaniu dały cały zbiór. Przykład, bo nie bardzo wiem jak to wytłumaczyć :)

np.

n = {1,2,3,4,5,6}
z1 = {1, 2, 3}
z2 = {2, 3, 4}
z3 = {1, 6}
z4 = {4, 5, 6}
z5 = {2, 5}

W tym przypadku optymalnym rozwiązaniem będą dwa podzbiory: z1 oraz z4, ponieważ po zsumowaniu dają cały zbiór n. Chodzi o minimalizację ilości tychże podzbiorów ;)

To raczej nie do inżynierii.

http://en.wikipedia.org/wiki/Set_cover_problem mówi że to jest problem NP-trudny.

Dzięki bardzo! Nie wiedziałem, gdzie i jak to na wiki znaleźć :). Powiedz tylko na przyszłość, do jakiego działu kierować pytania z algorytmiki.

Do działu Inne, albo Nietuzinkowe tematy raczej.