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

20

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?

ipsec
źródło

Odpowiedzi:

11

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={x1,,xn}KSK

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 } .xi>0S={x1,x2,,xn,K}

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

Problem występuje, gdy możemy mieć dla niektórych z i .xi0i

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

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

Teraz skonstruuj nowy zestaw taki, żeS={y1,y2,yn}

gdzie M = P + | N | + K .yi=xi+MM=P+|N|+K

Każdy .yi>0

Teraz uruchom na zestawach algorytm sumy zerowej

S{(K+M)}

S{(K+2M)}

S{(K+3M)}

S{(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.SK

Pozostawiam dowód innego kierunku.

Aryabhata
źródło
Dziękuję Ci bardzo. Zastanawiam się, czy istnieje redukcja, która przekształca wystąpienie sumy zerowej w jedną (zamiast ) wystąpienie sumy częściowej K? n
ipsec
@ipsec: Masz na myśli przekształcenie wystąpienia sumy K-podzbioru na sumę 0-podzbioru? Być może przyjęcie unii zestawów powyżej zadziała. n
Aryabhata,
Cóż, właściwie dwa razy zastanawiałem się, czy mam teraz kierunek w prawo. Kiedy chcę pokazać, że suma K podzbioru jest NP-trudna dla każdego K, biorąc pod uwagę fakt, że suma 0-podzbioru jest NP-trudna, mogę zastosować redukcję z sumy 0-podzbioru do sumy K-podzbioru , dla którego potrzebowałbym transformacji wieloczasowej z dowolnej instancji 0 na instancję K. Ale nie jestem teraz pewien, czy tak właśnie zadałem w swoim pytaniu.
ipsec
s=0KKKKkk
Nieważne. Zastanawiałem się pierwotnie nad tym, skoro wiemy, że suma zerowa jest NP-trudna, czy możemy wywnioskować, że np. Również suma częściowa? Wikipedia tak mówi, ale szukałem odpowiedniej redukcji. Widzę jednak teraz, że moje sformułowania zostały całkowicie pomieszane i faktycznie pytałem o coś przeciwnego. W każdym razie dałeś mi wystarczająco dużo danych wejściowych, aby zredukować instancję z dowolnej sumy K do instancji sumy L dla dowolnej liczby całkowitej K i L, więc mój problem jest nadal rozwiązany.
ipsec
0

ccKc=2(n+1)

(S={x1,,xn},K)K

  • Y={y1,,yn}yi=2(n+1)xi+1
  • z=2K(n+1)n
  • n1

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

{xj1,,xjm}mKy{yj1,,yjm}2K(n+1)+m2K(n+1)nmn1mn[n+1,0]

2(n+1)

{yj1,,yjm}mY[1,n1]zz=2K(n+1)nnn1

zY2(n+1)nYn1Yn+n1=2n12(n+1)z2(n+1)Y2(n+1)2(n+1)z=2K(n+1)n

z

(2K(n+1)n)+i=1m(2(n+1)xji+1)+pull-ups=0

i możemy zmienić warunki:

2K(n+1)+i=1m(2(n+1)xji)(n+i=1m1+pull-ups)=0

2K(n+1)+i=1m(2(n+1)xji)(n+m+pull-ups)=0

2(n+1)(K+i=1mxji)(n+m+pull-ups)=0

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

(n+m+pull-ups)=0

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

2(n+1)(K+i=1mxji)=0

2(n+1)

K+i=1mxji=0

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

j_random_hacker
źródło