Biorąc pod uwagę zbiór wielu liczb naturalnych X, rozważ zestaw wszystkich możliwych sum:

$$\textrm{sums}(X)= \left\{ \sum_{i \in A} i \,|\, A \subseteq X \right\}$$

Na przykład podczas gdy .sumy ( { 1 , 1 } ) = { 0 , 1 , 2 $\textrm{sums}(\left\{1,5\right\}) = \left\{0, 1, 5, 6\right\}$$\textrm{sums}(\left\{1,1\right\}) = \left\{0, 1, 2\right\}$

Jaki jest najskuteczniejszy algorytm obliczania operacji odwrotnej (mierzonej wielkością wejściowego zestawu sum)? W szczególności można skutecznie obliczyć dowolne z poniższych:

1. Czy dany zestaw jest prawidłowym zestawem sum. (Na przykład jest prawidłowy, ale nie jest.){ 0 , 1 , 3 $\left\{0,1,2\right\}$$\left\{0,1,3\right\}$
2. Multiset sumujący się do podanego zestawu.
3. Najmniejszy MultiSet że kwoty do danego zestawu. (Na przykład i sumują się do ale poprzedni jest mniejszy.){ 1 , 1 , 1 } { 0 , 1 , 2 , 3 $\left\{1,2\right\}$$\left\{1,1,1\right\}$$\left\{0,1,2,3\right\}$

Rozwiązanie

Rozwiązanie składa się z dwóch części. Najpierw odkrywamy zbiór minimalny, a następnie udowadniamy, że może on reprezentować zbiór sum mocy. Rozwiązanie jest dostosowane do implementacji programowania.

Algorytm minimalnego zestawu

1. Znajdź maksymalny element z zestawu sumy (wielu). , potencjalny minimalny (wielokrotny) zestaw jest początkowo pusty.$a_{m}$$P$

2. O ile nie istnieje tylko jedna grupa, reprezentuj na wszystkie możliwe sposoby jako parę sum, które składają się na , a m S i j = { ( a i , a j ) | a i + a j = a m$a_{m}$$a_{m}$$S_{ij}=\{(a_{i},a_{j})|a_{i}+a_{j}=a_{m}\}$

3. Sprawdź, czy wszystkie elementy z zestawu sum są uwzględnione.

4. Znajdź maksymalny element ze wszystkich (czyli razem) z następującą właściwością: dla każdego , jest albo w , albo możemy znaleźć z zbiór sum, dzięki czemu znajduje się w . S i j S i j a s S i j a p a p + a s S i $a_{s}$$S_{ij}$$S_{ij}$$a_{s}$$S_{ij}$$a_{p}$$a_{p}+a_{s}$$S_{ij}$

5. Jeśli jest to tak, że nie zawiera a s , tylko suma s + a p , usuwanie a p + a S z S ı j (lub po prostu ustawić znacznik ignorowania) i włożyć i zamiast tego w .$S_{ij}$$a_{s}$$a_{s}+a_{p}$$a_{p}+a_{s}$$S_{ij}$ a s S i $a_{p}$$a_{s}$$S_{ij}$

6. Jeśli element jest obecny w każdym usunąć go ze wszystkich S í j raz (lub po prostu ustawić znak, aby go zignorować i nie dotykać go dłużej) i dodać go do listy elementów potencjalnej minimalny zbiór .$S_{ij}$$S_{ij}$$P$

7. Powtarzaj, aż wszystkie będą puste$S_{ij}$

8. Jeśli część pozostaje pusta i nie możemy kontynuować, spróbuj ponownie z maksymalną wartością ze wszystkich . S i $S_{ij}$$S_{ij}$

9. Odtworzenie cyklicznych czynności bez przeprowadzek i kontynuować algorytmu zestaw zasilający swym zasięgiem . (Wcześniej można bezpiecznie sprawdzić, czy obejmuje wszystkie elementy, których nie można przedstawić jako sumę dwóch elementów, więc na pewno muszą znajdować się w zestawie podstawowym. Na przykład minimalny element musi znajdować się w )P $P$$P$$P$

(10. Zauważ, że minimalne ustawione rozwiązanie, które jest celem algorytmu, nie może zawierać więcej niż jednego powtórzenia tej samej liczby.)

Przykład:

$$\{2,3,5,7,8,10,12,13,15\}$$

Reprezentuj 15 na wszystkie możliwe sposoby jako sumę dwóch liczb ze zbioru sum.

$$(13,2),(12,3),(10,5),(8,7)$$

Spróbuj znaleźć maksymalną liczbę, która jest we wszystkich grupach lub może być reprezentowana jako suma. Oczywiście możemy zacząć szukać od 8, nie ma sensu przekraczać tego.

13 z pierwszej grupy to 13 = 8 + 5, więc 13 jest w porządku, ale 12 z drugiej grupy nie jest w porządku, ponieważ nie ma 4, aby 12 = 8 + 4 w zbiorze sum. Następnie próbujemy z 7. Ale natychmiast 13 nie może być objętych, nie ma 6.

Następnie próbujemy 5. 13 = 5 + 8, 12 = 5 + 7, 10 = 5 + 5, a dla ostatnich 8 = 5 + 3 lub 7 = 5 + 2, ale nie oba. Grupy są teraz:

$$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$

5 powtarza się we wszystkich grupach, więc wyodrębniamy ją . Wyciągamy 5 tylko raz z każdej grupy.$P=\{5\}$

$$(8,2),(7,3),(5,5),(3,7)$$

Oczywiście nie ma sensu przekraczać 5, więc próbujemy ponownie 5. 8 = 5 + 3, 7 = 5 + 2, więc wszystko jest w porządku

$$((5,3),2),((5,2),3),(5,5),(3,(5,2))$$

Wyodrębnij jeden 5 ponownie ze wszystkich grup, ponieważ się powtarza. (To nie jest powszechne, ale nasza sprawa jest celowo tworzona, aby wyświetlać, co zrobić, jeśli mamy powtórzenia.)$P=\{5,5\}$

$$(3,2),(2,3),(5),(3,2)$$

Teraz próbujemy z 3 i mamy 5 = 3 + 2. Dodaj to do grupy.

$$(3,2),(2,3),(3,2),(3,2)$$

Teraz wyodrębnij 3 i 2, ponieważ powtarzają się wszędzie, a my mamy się dobrze a grupy są puste.$P=\{5,5,3,2\}$

$$(),(),(),()$$

Teraz musimy odtworzyć kroki rekurencyjne bez usuwania, oznacza to po prostu wykonanie powyższej czynności bez usuwania elementów z po prostu umieszczając je w i zaznaczając, aby nie zmieniać go.$S_{ij}$$P$

( ( 5 , 8 ) , 2 ) , ( ( 5 , 7 ) , 3 ) , ( ( 5 , 5 ) , 5 ) , ( ( 5 , 3 ) ,

$$(13,2),(12,3),(10,5),(8,7)$$ ( ( 5 , ( 5 , 3 ) ) , 2 ) , ( ( 5 , ( 5 , 2 ) ) , 3 ) , ( ( 5 , ( 3 , 2 ) ) , 5 ) , ( ( 5 , 3 ) , ( 5 , 2 ) $$((5,8),2),((5,7),3),((5,5),5),((5,3),7)$$ $$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$

Zasięg zestawu zasilania

Celem tej części jest sprawdzenie, czy znaleziony zestaw minimalny jest w stanie pokryć zestaw sumy mocy. Możliwe, że znalezione rozwiązanie może obejmować wszystkie podane sumy, ale nie są to sumy zestawu mocy. (Technicznie można po prostu utworzyć zestaw sum mocy na podstawie znalezionego zestawu minimalnego i sprawdzić, czy każda suma, jak nakazuje zestaw mocy, znajduje się w początkowym zestawie sum. To wszystko po prostu połączyło się z tym, co już mamy, więc nic się nie marnuje Możesz wykonać tę część podczas przewijania rekurencji.)

1. Zakoduj wszystkie elementy z zestawu minimalnego, stosując kolejne potęgi 2. Kolejność nie jest ważna. Zakoduj ten sam element nową wartością tyle razy, ile się powtarza. Zacznij od C = 1, każdy następny element ma C = 2C.

$$(2=[1],3=[2],5=[4],5=[8])$$

2. Zastąp elementy na przywróconej liście rekurencji,

$$((5,(5,3)),2),((5,(5,2)),3),((5,(3,2)),5),((5,3),(5,2))$$

z kodowaniem: 2 z 1, 3 z 2, 5 z 4, a kolejne 5 z 8. Zauważ, że każdy element ma inne kodowanie, nawet jeśli są one powtarzane.

$$((4,(8,2)),1),((4,(8,1)),2),((4,(2,1)),8),((8,2),(4,1))$$

3. Zbierz wszystkie kwoty pośrednie, w tej chwili mamy (1,2,4,8)

$$((4,(10)),1),((4,(9)),2),((4,(3)),8),((10),(5))$$

Suma pośrednia$(1,2,3,4,5,8,9,10)$

$$((14),1),((13),2),((7),8),(15)$$

Suma pośrednia$(1,2,3,4,5,8,9,10,13,14,15)$

$$\{(15),(15),(15),(15)\}$$

4. Sprawdź, czy wynikiem jest , gdzie jest liczbą elementów w rozwiązaniu, w przykładzie$2^m-1$$m$$m=4$

5. Zbierz brakujące liczby od do na liście sum pośrednich$1$$2^m-1$

$(6,7,11,12)$

6. Uzasadnij ich brak w następujący sposób: reprezentuj każdą liczbę w formie binarnej

$(6=0110_2)$ $(7=0111_2)$ $(11=1011_2)$ $(12=1010_2)$

$6$ oznacza sumę 3 + 5, ponieważ pokrywa drugi i trzeci element z . Suma tych elementów, 8, jest wymieniona na liście sum początkowych , więc wszystko jest w porządku.$0110_2$$(2=[1],3=[2],5=[4],5=[8])$$\{2,3,5,7,8,10,12,13,15\}$

$7$ oznacza sumę 2 + 3 + 5, ponieważ obejmuje pierwsze trzy elementy z . Suma tych elementów, 10, znajduje się na liście sum początkowych, więc wszystko jest w porządku.$0111_2$$(2=[1],3=[2],5=[4],5=[8])$

$11$ to 2 + 3 + 5, a 10 jest na liście. to 3 + 5, a 8 jest na liście.$12$

Jeśli jakaś reprezentacja binarna odpowiada sumie, której nie można znaleźć, zgłoś, że nie ma rozwiązania.

Wszystko jest w porządku, a jest rozwiązaniem. Jest to również minimalne rozwiązanie.$(2,3,5,5)$

Dyskusja

Konieczne było podanie algorytmu, który będzie sprawdzał, czy sumy pokrywają zakończenie zestawu mocy, co jest ukryte w binarnym rozszerzeniu. Na przykład, jeśli wykluczymy 8 i 7 z początkowego przykładu, pierwsza część nadal zapewni rozwiązanie, tylko druga część zgłosi brakujące kombinacje sum.

Pierwszą częścią odkrycia możliwego zestawu minimalnego jest który przychodzi do : rozglądamy się wokół elementów razy, mając jedno wyszukiwanie binarne .$mnlog(m)$$m\log^2(m)$$m$$n$$\log(m)$

Ostatnia część jest wykonywana w zwrocie rekurencyjnym i nie wymaga żadnego specjalnego wysiłku, szukamy mniej niż elementów, potrzebujemy postaci binarnej, którą jest i mamy jeden dodatek i szukamy, czy suma jest w listy, więc razem znów chodzi o .$m$$\log{m}$$m\log^2(m)$

Jeśli założymy, że liczba elementów w zestawie sumy mocy odpowiada liczbie partycji największego elementu w zestawie podstawowym, wówczas złożoność wynosi około . Każde z tych dwóch uzasadnia wstępne sortowanie w celu znalezienia największego elementu.$m\log^3(m)$

Części algorytmu zakładają, że możemy znaleźć parę sum w czasie liniowym, a to wymaga sortowania.

Niepoprawny początek

Pierwsza część algorytmu może się nie powieść, jeśli uruchomiliśmy go na niewłaściwej stopie. Na przykład ma podstawowe rozwiązanie które otrzymasz, jeśli uruchomisz algorytm od 6. Jednak my może uruchomić nasz algorytm od 7, ponieważ w kroku 4 nie ma nic, co powiedziałoby, że nie, i zablokować się, algorytm nie może zakończyć się poprawnie. Powodem jest to, że 7 to 7 = 4 + 3, a 4 i 3 są w roztworze. Tak zablokowany algorytm nie zawsze oznacza, że ​​nie ma rozwiązania, wystarczy spróbować ponownie z niższą wartością początkową. W takim przypadku niektóre pomysły dotyczące możliwych wartości są ukryte w pozostałych . Dlatego sugerowaliśmy zacząć od tego w razie awarii.$2,3,4,5,6,7,8,9,10,11,12,13,15$$2,3,4,6$$S_{ij}$

Kolejny przykład, jeśli i uruchomisz algorytm od 5, otrzymasz ale ten nie zawiera 2.$5,4,3,3$

Zauważ, że ten algorytm nie da pochodnych rozwiązań, takich jak , które otrzymaliśmy po prostu zamieniając 6 na 4 i 2 w rozwiązaniu . Istnieją specjalne zasady dotyczące tych wersji.$2,2,3,4,4$$2,3,4,6$

Celem tego algorytmu jest dostarczenie rozwiązania, gdy wszystko zaczniemy poprawnie.

Ulepszenia

Krok 4. to ten, który można zaktualizować w ten sposób: zamiast maksymalnego możemy wypróbować każdy element w malejącej kolejności, który spełnia podany warunek. Dla każdego tworzymy osobny oddział. Jeśli jakiś oddział nie daje rozwiązania, anuluj je.

Na przykład dla moglibyśmy spróbować w pierwszej rundzie osobno, ponieważ wszystkie z nich są zdanie pierwszego testu. (Nie ma powodu, aby używać 2 lub 3, ponieważ wiemy, że muszą one znajdować się w podstawowym zestawie.) I po prostu kontynuuj w ten sposób, aż zbierzemy wszystkie wersje, które mogą dotrzeć do końca. Stworzyłoby to pełne rozwiązanie, które odkryłoby więcej niż jeden podstawowy zestaw.7 , 6 , 5 , $2,3,4,5,6,7,8,9,10,11,12,13,15$$7,6,5,4$

Inna sprawa, ponieważ wiemy, że nie możemy mieć więcej niż jednego powtórzenia, jeśli przypadek jest minimalny, możemy to uwzględnić w naszym algorytmie.

Ogólnie rzecz biorąc, warunek w kroku 4., że liczba musi powtarzać się w każdej grupie lub mieć zdolność do tworzenia sumy, jest wystarczająco silny, aby wydostać nas z bezpośrednich wód wykładniczych, co byłoby algorytmem po prostu wypróbowania każdej kombinacji i stworzenia mocy ustawiać każdy z nich, aż znajdziemy dopasowanie.

UWAGA: Zasadniczo to nie działa, patrz kontrprzykład Uri poniżej.

$Y$$Y$

• $0\in Y$
• $y$$Y$$y$$X$$Y$
• $z_1<\dots<z_n$$Y$$Y'$$Y = Y' + \{0,y\}$$0$$Y'$$i=1,\dots,n$$z_i+y\in Y$$z_i$$Y'$$z_i-y\notin Y$$z_i+y\notin Y$$z_i+y\in Y$$z_i$$Y'$
• $Y'$$y,y',\dots$

$1$$y$$O(n)$$O(n^2)$

$Y=\{0,1,3,4,5,6,7\}$$\{0,1,3,4,6\}$$\{0,1,3,5,6\}$$y\in Y$$\{a+k\cdot y\}$$Y$$Y'$