Teilsummenproblem in Java

[tm.grp]

Hi,
ich habe die Aufgabe das Teilsummenproblem für eine Annäherung an Pi mit der Menge von maximal 20 Zahlen, die über die Konsole eingelesen werden , via Java zu lösen. Wie man die letztendlichen Teilmengen darauf vergleicht welche am nähesten an Pi liegen, ist mir klar. Jedoch soll ich für die Bestimmung aller Teilmengen der Menge folgenden Pseudocode in Java umsetzen, aber mir fehlt es einfach vollkommen am Zugang zum Sinn bzw. zur Funktionsweise dieses Algorithmus, insbesondere der Schleifeninhalt: "wenn die Binärdarstellung von x an der Stelle i eine 1 stehen hat", was soweit ich es verstanden habe über: " (x >> i) & 1" implementiert werden soll, erscheint mir äußerst rätselhaft. (Details weiter unten im Aufgabentext). Ich habe für besseres Verständnis mal die Tipps mit rein kopiert. Falls mir irgendjemand die Funktionsweise, zumindest grob, erläutern könnte, wäre ich sehr dankbar.

LG, Tim

Unser Algorithmus soll alle Teilmengen durchprobieren und diejenige finden, deren Elemente aufsummiert am nächsten an Pi liegen. Im Grunde benötigen wir also zwei Algorithmen. Einen, der alle Teilmengen generiert und einen Weiteren, der die Beste unter ihnen findet. Letzterer ist ein einfacher Suchalgorithmus, der jedes Element des Suchraums nacheinander betrachtet und sich das aktuell Beste merkt. Hat der Algorithmus alle Elemente betrachtet, kann er sich sicher sein das beste Element gefunden zu haben.
Etwas schwieriger ist es, alle Teilmengen einer Menge zu generieren. Betrachten Sie folgenen Pseudocode für eine Menge M mit n Elementen:

für alle ganzen Zahlen x von 0 bis 2n
für alle ganzen Zahlen i von 0 bis n
wenn die Binärdarstellung von x an der Stelle i eine 1 stehen hat
dann
füge M[ i ] dem Ergebnis hinzu

Dieser Algorithmus findet alle möglichen Teilmengen der Menge M in exponentieller Zeit. Das ist wie einleitend geschrieben sehr ineffizient. Umso wichtiger ist eine effiziente Implementierung der Teilschritte. Einige Tipps zur Umsetzung finden Sie am Ende der Aufgabenstellung.

Tipps:

• Die Klasse Math enthält eine Konstante PI mit sehr vielen Nachkommastellen, die man alle nicht selbst eintippen muss, wenn man die Konstante nimmt.
• Im Algorithmus werden sehr große Ganzzahlen erzeugt (2n). Hier kann der Datentyp long erforderlich werden.
• Die i-te Binärstelle einer positiven Zahl x erhält man sehr effizient durch: (x >> i) & 1, nur falls Sie sich gefragt haben, wozu Java diese ganzen komischen Operatoren hat.
• 2n kann man auch mit Bitshift-Operatoren ausrechnen.
• Die Anzahl Einsen in der Binärdarstellung einer Zahl x erhält man komfortabel und effizient durch die Methode Long.bitCount(long x).
• Das erstellen neuer Arrays ist vergleichsweise zeitaufwändig. Sie können ausnutzen, dass Sie zum Berechnen der Summe aller Elemente einer Teilmenge die Teilmenge selbst nicht speichern müssen. Sie erzeugen sie ja sowieso "on the fly". Erst für die Ausgabe der besten Teilmenge ganz am Ende, ist es sinnvoll, die Elemente der Teilmenge zwischenzuspeichern.
• Die Methode Arrays.toString(double[] arr) gibt double-Arrays in einem Format aus, das dem Geforderten verdächtig ähnlich ist.
• Auch die leere Menge ist eine Teilmenge und damit eine potentielle Lösung

 

[fhoffmann]

Die Idee ist folgende:

Ich suche alle Telmengen der Menge {A,B,C} (eine Menge mit drei Elementen).
Dann gehe ich alle Zahlen von 0 bis 2^3-1=7 (in Binärdarstellung) durch und bestimme dazu die entsprechenden Mengen:

0=000 {}
1=001 {C}
2=010 {B}
3=011 {B,C}
4=100 {A}
5=101 {A,C}
6=110 {A,B}
7=111 {A,B,C}

Ich wähle ein Element aus der Menge also genau dann aus, wenn in der Binärdarstellung der Zahl an der passenden Stelle eine 1 steht.

 

[FelixN]

vielleicht hilft der Denkanstoß: die äußere x-Schleife läuft ja 2^n mal durch. Grund dafür ist, dass eine Menge aus n Elementen immer aus 2^n verschiedenen Teilmengen besteht! also bei z.B. 3 Elementen gibt es 2^n (=8) mögliche Teilmengen .

für jedes x wird dann in der inneren Schleife geprüft, ob in der Binärdarstellung an der Stelle i eine 1 steht.
hier hilft der Tipp " (x >> i) & 1".
Im Prinzip erhältst du also nach jedem inneren Durchlauf eine Teilmenge. An der Stelle es gilt es diese Teilmenge bzw. die Summe dazu zwischenzuspeichern und zu prüfen, ob diese Teilmenge bzw. Summe besser geeignet ist als die davor.