mam około 1000 zestawów wielkości < = 5 o numerach od 1 do 100.Stała wielkość zestaw zawiera maksymalną liczbę podanych zestawów
{1}, {4}, {1,3}, {3,5,6}, {4,5,6,7}, {5,25,42,67,100} ...
jest to możliwe, dla znalezienia zbioru o rozmiarze 20, który zawiera maksymalna liczba podanych zestawów?
Sprawdzanie każdego zestawu 100!/(80!*20!) jest nieefektywne.
Nie jestem pewien, czy NP jest kompletny.
Rozważmy związany z tym problem, gdy otrzymujemy nagrodę w wysokości x za każdy zestaw, ale musimy zapłacić cenę y za każdy numer, który chcemy dopuścić. (Zestaw płaci tylko nagrodę, jeśli wszystkie numery to zawiera zostały opłacone.)
można rozwiązać tego typu problem przy użyciu max flow algorithm przez:
rozwiązując problem maksymalnego przepływu na wykresie (od źródła do węzła docelowego) znajduje minimalny koszt cięcia c.
Kwota netto, którą moglibyśmy zarobić, to N.x-c (gdzie N to liczba zestawów).
Jeśli możemy wybrać y (np. Przez bisection) tak, że wybraliśmy dokładnie 20 liczb, to udało nam się rozwiązać dla maksymalnej liczby zestawów z 20 liczbami.
Dziękuję. Sprawdzę maksymalny przepływ i przyjmuję odpowiedź. – albert
Mógłbyś powiedzieć, że [Set cover problem] (https://pl.wikipedia.org/wiki/Set_cover_problem) czy to tylko ja nie rozumiem twojego sformułowania? – ThreeFx
@ThreeFx Nawet mocno odczuwam, że problem leży w zakresie NP pełnych problemów, ale to nie jest dokładnie to samo, co dobrze znany problem z okładką zestawu. –
W zestawie pokrywy chcemy minimalną liczbę zestawów, których związek ma 100 elementów. Chcę maksymalną liczbę zestawów, których związek ma 20 elementów. – albert