Podzbiór Suma: zredukuj przypadek specjalny do ogólnego

Wikipedia stwierdza problem sumy podzbiorów jako znalezienie podzbioru danego zbioru wielu liczb całkowitych, którego suma wynosi zero. Dalej stwierdza, że ​​jest to równoważne ze znalezieniem podzbioru z sumą $s$ dla dowolnego danego $s$ .

Sądzę więc, że ponieważ są one równoważne, musi nastąpić zmniejszenie po obu stronach. Jeden od $s$ do zera jest trywialny, ustawiając $s = 0$ . Ale nie miałem szczęścia znaleźć redukcji od zera do $s$ , tj. Biorąc pod uwagę zestaw liczb całkowitych $A$ , skonstruuj zestaw liczb całkowitych $B$ zawierający podzbiór z sumą $s$ (dla dowolnych $s$ ), tylko wtedy, gdy istnieje taki podzbiór $A$ z suma zero.

Czy możesz podać mi wskazówki?

W rzeczywistości masz już redukcję ze specjalnej na ogólną. Ustawiając , zasadniczo używasz ogólnego algorytmu do rozwiązania specjalnego problemu.$s=0$

W drugą stronę (tj. Redukcję z ogólnej do specjalnej):

Załóżmy, że przy danym zestawie a liczba K i trzeba sprawdzić, czy nie jest pewnego podzbioru S które sumuje się do K .$S = \{x_1, \dots, x_n\}$$K$$S$$K$

Teraz chcesz rozwiązać ten problem, biorąc pod uwagę algorytm dla przypadku, w którym możesz określić, czy niektóre podzbiory sumują się do .$0$

Teraz jeśli , mamy łatwą redukcję: S ′ = { x 1 , x 2 , … , x n , - K } .$x_i \gt 0$$S' = \{x_1, x_2, \dots, x_n, -K\}$

jest podzbiór sumy 0 IFF S ma podzbiór sumie K .$S'$$0$$S$$K$

Problem występuje, gdy możemy mieć dla niektórych z i .$x_i \le 0$$i$

Możemy założyć, że (dlaczego?).$K \gt 0$

Załóżmy, że suma pozytywnych jest P i ujemny x i to dotyczy .$x_i$$P$$x_i$$N$

Teraz skonstruuj nowy zestaw taki, że$S' = \{y_1, y_2 \dots, y_n\}$

gdzie M = P + | N | + K .$y_i = x_i + M$$M = P + |N| + K$

Każdy .$y_i \gt 0$

Teraz uruchom na zestawach algorytm sumy zerowej

$S' \cup \{-(K+M)\}$

$S' \cup \{-(K+2M)\}$

$S' \cup \{-(K+3M)\}$

$\dots$

$S' \cup \{-(K+nM)\}$

Łatwo jest wykazać, że jeśli ma podzbiór sumy K , to co najmniej jeden z powyższych zestawów ma podzbiór sumy zero.$S$$K$

Pozostawiam dowód innego kierunku.

$c$$cK$$c=2(n+1)$

$(S = \{x_1, \dots, x_n\}, K)$$K$

• $Y = \{y_1, \dots, y_n\}$$y_i = 2(n+1)x_i + 1$
• $z = -2K(n+1)-n$
• $n-1$

$K$$K$$K$$K$$K=0$ wtedy nie musimy w ogóle przekształcać przypadku ogólnego w przypadek specjalny!)

$\{x_{j_1}, \dots, x_{j_m}\}$$m$$K$$y$$\{y_{j_1}, \dots, y_{j_m}\}$$2K(n+1)+m$$-2K(n+1)-n$$m-n$$1 \le m \le n$$[-n+1, 0]$

$2(n+1)$

$\{y_{j'_1}, \dots, y_{j'_{m'}}\}$$m'$$Y$$[1, n-1]$$z$$z = -2K(n+1)-n \le -n$$n-1$

$z$$Y$$2(n+1)$$n$$Y$$n-1$$Y$$n + n-1 = 2n-1$$2(n+1)$$z$$2(n+1)$$Y$$2(n+1)$$2(n+1)$$z = -2K(n+1)-n$

$z$

$(-2K(n+1) - n) + \sum_{i'=1}^{m'} (2(n+1) x_{j'_{i'}} + 1) + \sum {\text{pull-ups}} = 0$

i możemy zmienić warunki:

$-2K(n+1) + \sum_{i'=1}^{m'} (2(n+1) x_{j'_{i'}}) - (n + \sum_{i'=1}^{m'} 1 + \sum {\text{pull-ups}}) = 0$

$-2K(n+1) + \sum_{i'=1}^{m'} (2(n+1) x_{j'_{i'}}) - (n + m' + \sum {\text{pull-ups}}) = 0$

$2(n+1)(-K + \sum_{i'=1}^{m'} x_{j'_{i'}}) - (n + m' + \sum {\text{pull-ups}}) = 0$

$2(n+1)$$2(n+1)$

$-(n + m' + \sum {\text{pull-ups}}) = 0$

Można to bezpośrednio zastąpić poprzednim równaniem

$2(n+1)(-K + \sum_{i'=1}^{m'} x_{j'_{i'}}) = 0$

$2(n+1)$

$-K + \sum_{i'=1}^{m'} x_{j'_{i'}} = 0$

co daje rozwiązanie pierwotnej instancji problemu ogólnego.