Teilmenge Summe: Spezialfall auf allgemeinen Fall reduzieren

Wikipedia gibt das Teilmengen-Summenproblem an, indem es eine Teilmenge einer gegebenen Mehrfachmenge von ganzen Zahlen findet, deren Summe Null ist. Ferner heißt es, dass es äquivalent ist, eine Teilmenge mit der Summe für jedes gegebene .$s$$s$

Ich glaube also, da sie gleichwertig sind, muss es auf beiden Seiten eine Reduzierung geben. Die Eins von bis Null ist durch Setzen von trivial . Aber ich hatte kein Glück, eine Reduktion von Null auf , dh wenn man eine Menge von ganzen Zahlen , konstruiere man eine Menge von ganzen Zahlen die eine Teilmenge mit der Summe (für jedes ) enthält, genau dann, wenn es eine Teilmenge von mit gibt Summe Null.$s$$s = 0$$s$$A$$B$$s$$s$$A$

Kannst du mir ein paar Hinweise geben?

Sie haben tatsächlich bereits eine Ermäßigung von Spezial auf Allgemein. Wenn Sie , verwenden Sie grundsätzlich den allgemeinen Algorithmus, um das spezielle Problem zu lösen.$s=0$

Umgekehrt (dh Reduzierung vom Allgemeinen zum Besonderen):

Angenommen, Sie erhalten eine Menge und eine Zahl und müssen feststellen, ob es eine Teilmenge von die zu summiert .K S $S = \{x_1, \dots, x_n\}$$K$$S$$K$

Nun möchten Sie dieses Problem lösen, indem Sie einen Algorithmus für den Fall angeben, in dem Sie bestimmen können, ob eine Teilmenge ergibt .$0$

Wenn nun , haben wir eine einfache Reduktion: .S ' = { x 1 , x 2 , … , x n , - K $x_i \gt 0$$S' = \{x_1, x_2, \dots, x_n, -K\}$

0 S $S'$ hat eine Teilmenge von Summe wenn eine Teilmenge von Summe .$0$$S$$K$

Das Problem tritt auf, wenn wir für einige der haben können .$x_i \le 0$$i$

Wir können annehmen, dass (warum?).$K \gt 0$

Angenommen , die Summe der positiven ist und die negative ist . P x i$x_i$$P$$x_i$$N$

Konstruiere nun eine neue Menge so dass$S' = \{y_1, y_2 \dots, y_n\}$

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

Jedes .$y_i \gt 0$

Führen Sie nun den Null-Teilmengen-Summen-Algorithmus für die Mengen aus

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

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

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

$\dots$

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

Es ist leicht zu zeigen, dass, wenn eine Teilmenge der Summe , mindestens eine der obigen Mengen eine Teilmenge der Summe Null hat.$S$$K$

Ich überlasse Ihnen den Beweis der anderen Richtung.

Aryabhatas Antwort kann korrigiert werden, indem wir die Tatsache ausnutzen, dass wir alle Zahlen mit einem großen multiplizieren und dann jedem eine kleine Zahl hinzufügen, um sich wie ein "Anwesenheitsetikett" zu verhalten, und dann einige zusätzliche Zahlen angeben, die dies ermöglichen uns auf Null zu bringen, wenn wir ohne sie zu könnten. Insbesondere werden wir und 1 als Präsenz-Tag verwenden.$c$c K c = 2 ( n + 1 )$cK$$c=2(n+1)$

Bei einer Instanz des allgemeinen Problems mit dem Zielwert erstellen wir eine Instanz des spezifischen Problems (mit dem Zielwert 0), die Folgendes enthält:$(S = \{x_1, \dots, x_n\}, K)$$K$

• $Y = \{y_1, \dots, y_n\}$ , wobei .$y_i = 2(n+1)x_i + 1$
• Die Zahl .$z = -2K(n+1)-n$
• $n-1$ Kopien der Nummer 1, die als "Pull-up" -Nummern bezeichnet werden.

Ich gehe davon aus, dass positiv ist , wenn Aryabhatta es tut . (Da es 6 Jahre her ist, beantworte ich seine Aufgabe für den Leser: Der Grund, warum wir dies tun können, ist, dass wir, wenn wir die Vorzeichen aller Zahlen in einem Fall des allgemeinen Problems, einschließlich , tauschen , mit einem enden neue, äquivalente Probleminstanz: Das bedeutet, dass ein Algorithmus zum Lösen positiver Instanzen ausreicht, um jedes Problem zu lösen. Um eine Instanz mit negativem zu lösen , können wir diesen Vorzeichentausch durchführen, diesen Algorithmus ausführen und seine Antwort weiterleiten als die Antwort auf die ursprüngliche Frage. Und natürlich müssen wir, wenn ist, den allgemeinen Fall überhaupt nicht in den speziellen Fall umwandeln!)$K$K K K K = 0$K$$K$$K$$K=0$

Lassen Sie uns zunächst zeigen, dass eine JA-Antwort auf die gegebene Instanz des allgemeinen Problems eine JA-Antwort auf die konstruierte Instanz des speziellen Problems impliziert. Hier können wir davon ausgehen , dass einige Lösung auf das allgemeine Problem besteht: Das heißt, diese nicht leer Sammlung von Zahlen Summen . Wenn wir also die entsprechenden Werte in unsere Lösung für die konstruierte Instanz aufnehmen, summieren sie sich zu . Wir können dann wählen, in die Lösung aufzunehmen, wobei wir eine Summe von . Da , liegt dieses im Bereich$\{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]$ , das wir erfolgreich auf 0 hochziehen können, indem wir eine Teilmenge der Pull-up-Nummern einschließen.

Lassen Sie uns nun zeigen, dass eine JA-Antwort auf die erstellte Instanz eine JA-Antwort auf die ursprünglich angegebene Instanz impliziert. An dieser Stelle wird die Multiplikation mit wichtig - so können wir sicher sein, dass die zusätzlichen Zahlen, die wir einbeziehen, nicht "zu viel bewirken" können.$2(n+1)$

Hier können wir annehmen, dass eine Lösung für die konstruierte Instanz existiert: Das heißt, diese nicht leere Sammlung von m' Zahlen summiert sich zu 0 Aufgrund der Problemanforderungen enthält diese Lösung mindestens ein Element. Weiterhin muss es mindestens ein Element aus , da es ohne dieses nicht möglich ist, eine Gesamtzahl von 0 zu erreichen: Liegen nur Pull-Up-Zahlen vor, so liegt die Summe zwangsläufig im Bereich ( Beachten Sie, dass in diesem Fall mindestens eine Pull-up-Nummer vorhanden sein muss und alle von ihnen streng positiv sind, sodass die Summe nicht 0 sein kann. während wenn die Lösung nur aus und einigen Pull-Up-Zahlen besteht, dann ist die Summe notwendigerweise negativ, weil$\{y_{j'_1}, \dots, y_{j'_{m'}}\}$$m'$$Y$$[1, n-1]$$z$$z = -2K(n+1)-n \le -n$ und das , um das die Pull-up-Zahlen die Summe erhöhen können, ist .$n-1$

Nehmen wir nun zum Widerspruch an, dass die Lösung . Jedes Element in besteht aus zwei Begriffen: Einem Vielfachen von und einem +1 "Anwesenheits-Tag". Beachten Sie, dass der Term +1 für jedes der Elemente von die Summe um 1 erhöht, wenn dieses Element ausgewählt wird, ebenso wie jede der bis zu Pull-up-Zahlen, also die Summe, die diese 2 beigetragen haben Quellen für jede Lösung ist mindestens 1 (weil wir im vorherigen Absatz festgelegt haben, dass mindestens ein Element von muss) und höchstens . Insbesondere impliziert dies, dass die Summe dieser beiden Mengen von Begriffen, wenn sie modulo genommen wird$z$$Y$$2(n+1)$$n$$Y$$n-1$$Y$$n + n-1 = 2n-1$$2(n+1)$ ist ungleich Null. Unter der Annahme, dass die Lösung kein enthält , sind die einzigen anderen Komponenten in dieser Summe die Vielfachen von die von den ausgewählten Mitgliedern von beigesteuert werden und die den Wert der Summe bei Modulo nicht beeinflussen . Somit ist die Summe aller Terme in der Lösung, wenn Modulo , ungleich Null, was bedeutet, dass sie nicht gleich der Zielsumme von 0 sein kann, was bedeutet, dass sie überhaupt keine gültige Lösung sein kann: Wir haben einen Widerspruch gefunden Das heißt, es muss sein, dass in jeder Lösung doch vorhanden ist.$z$$2(n+1)$$Y$$2(n+1)$$2(n+1)$$z = -2K(n+1)-n$

So enthält jede Lösung . Wir wissen das$z$

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

und wir können die Begriffe neu ordnen:

$-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$ .

Da die Summe 0 ist, muss sie bei Modulo 0 bleiben , was bedeutet, dass wir alle Terme verwerfen können, die ein Vielfaches von , um die neue Gleichung zu erhalten$2(n+1)$$2(n+1)$

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

Dies kann direkt wieder in die vorherige Gleichung eingesetzt werden, um zu erhalten

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

Zum Schluss werden beide Seiten durch Blätter geteilt$2(n+1)$

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

Dies ergibt eine Lösung für die ursprüngliche allgemeine Probleminstanz.