Teilsummenproblem in Java

tm.grp

Neues Mitglied
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
 
Zuletzt bearbeitet:

fhoffmann

Top Contributor
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:

Code:
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

Mitglied
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.
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
Master3000 JAVA Filereader Allgemeine Java-Themen 13
N A java Exception has occured Allgemeine Java-Themen 7
F Java Script für das Vorhaben das richtige? Allgemeine Java-Themen 9
M wiviel Java muss ich für die Berufswelt können ? Allgemeine Java-Themen 5
R Datumsformat für GB ab Java 16 Allgemeine Java-Themen 1
1Raini Java Warteschlange Allgemeine Java-Themen 21
Tobero .jar Dateine aus einem Ordner laden (Java 16) Allgemeine Java-Themen 5
Z WebApp mit Java verbinden. Allgemeine Java-Themen 8
Mart Vergleich C# und Java Allgemeine Java-Themen 24
S Bildrechte Java, HTML5 und PDF Symbole Allgemeine Java-Themen 5
P Bat Datei in Java ausführen Allgemeine Java-Themen 2
S Java öffnet immer im editor Allgemeine Java-Themen 1
Z macOS java konnte nicht entfernt werden xpc verbindungsfehler Allgemeine Java-Themen 4
F Java JDK ohne Oracle Konto Allgemeine Java-Themen 5
B Mit Java Click bei (x,y) machen? Allgemeine Java-Themen 6
S Java-Clicker Allgemeine Java-Themen 6
yakazuqi Fehler beim Laden. JDA (Java Discord API) Allgemeine Java-Themen 1
J Gmail Postfach und Java Allgemeine Java-Themen 6
E Java Website Login Allgemeine Java-Themen 2
D SHA-3 für Java-version 1.8 Allgemeine Java-Themen 1
N Regulären Ausdruck in normalen Java-Code umwandeln Allgemeine Java-Themen 12
X Java gewerblich nutzen mit externe Bibliothek. Was zu beachten? Allgemeine Java-Themen 18
B In Java Methode mit generic input und output basteln? Allgemeine Java-Themen 4
A Java ListNode Element einfügen ohne Bibliothek Allgemeine Java-Themen 6
S Flächenermittlung von 3D-Modellen per Java? Allgemeine Java-Themen 8
sascha-sphw Erste Schritte Unit und Integration-Tests im Java Modul System Allgemeine Java-Themen 10
Q Java-Programmieren Allgemeine Java-Themen 1
mrBrown Java 16 ist seit heute verfügbar Allgemeine Java-Themen 12
1Raini Java if-Abfrage funktioniert nicht! Allgemeine Java-Themen 3
B BOT mit Java [Eclipse] programmieren Allgemeine Java-Themen 7
NicoDeluxe Java Email Templates Allgemeine Java-Themen 2
V4ll3.Wff Array in Java Allgemeine Java-Themen 4
G Übermittlung zusätzlicher ASCII-Zeichen bei Übertragung von Dateiinhalt mit Xmodem - JAVA Allgemeine Java-Themen 9
D Java als anfänger Allgemeine Java-Themen 6
H was ist den dieses zur Kompilierzeit und zur Laufzeit in Java? Allgemeine Java-Themen 3
rtm007 Per Java Im Terminal Befehle eingeben. Allgemeine Java-Themen 4
J4n5chmiddi Methoden Website-URL im Browser öffnen nach erfolgreicher Basisauthentifizierung in Java Allgemeine Java-Themen 12
R Java Stream: Ist es möglich, einen stream zusammenzufassen Allgemeine Java-Themen 6
T Best Practice Java und unmodifiable Allgemeine Java-Themen 10
KeTho1712 Java Swing: JTable standardmäßig füllen, sodass bei Start bereits Datensätze gespeichert sind Allgemeine Java-Themen 1
Vanessa001 Hausaufgabe in Java Allgemeine Java-Themen 7
kanywayne Java programmieren: Polynom Klasse Allgemeine Java-Themen 4
T C++ Methode Übersetzung in Java Allgemeine Java-Themen 3
s_1895 Hilfe bei Java Tic Tac Toe Allgemeine Java-Themen 8
xGh0st2014 Problem mit Java Array Allgemeine Java-Themen 1
AGW in Java-Code plötzlich ein paar Wörter in Rot Allgemeine Java-Themen 2
F Java Console Allgemeine Java-Themen 2
Gaudimagspam Skip Liste erstellen in Java Allgemeine Java-Themen 3
AGW Java zu Kotlin Allgemeine Java-Themen 5
bax7891 Java Damals - Java Heute Allgemeine Java-Themen 6
N Value Wert aus HTML-Button mittels thymeleaf spring an java übergeben Allgemeine Java-Themen 2
N Lottowebsite programmieren mittels Java, HTML,.... Allgemeine Java-Themen 7
O Input/Output java.io.File beenden Allgemeine Java-Themen 5
S Java class direved from inner class Allgemeine Java-Themen 6
O Leerzeichen und Umlaute im Pfad einer Java Applikation machen Probleme Allgemeine Java-Themen 13
Gaudimagspam CSV-Datei auslesen in Java Allgemeine Java-Themen 7
T Meine Frage lautet wie ich 2 CSV Dateien miteinander in Java verbinde und Spalten die zueinander gehören durch den gleichen Key zusammen ausgebe? Allgemeine Java-Themen 5
H Java SDK unter 32 Bit Allgemeine Java-Themen 5
P Unterschied Java SE und Java EE Allgemeine Java-Themen 2
B Methoden Java Getter und Setter Methoden Allgemeine Java-Themen 9
M Registry Autostart Eintrag mit Java erstellen (über Windows cmd) Allgemeine Java-Themen 7
M Registry Autostart Eintrag ertstellen mit Java (Runtime.getRuntime().exec()) Allgemeine Java-Themen 0
S Java-Task-Management-Tool für Windows und Mac selber programmieren Allgemeine Java-Themen 4
M java.util.prefs.Preferences "not visible" Allgemeine Java-Themen 7
M Website Quelltext mit Java einlesen Allgemeine Java-Themen 10
J Java Filechooser Speichern Allgemeine Java-Themen 8
Dann07 Java-Programm findet DLLs nicht! Allgemeine Java-Themen 20
F Fehlermeldung: java.lang.NoClassDefFoundError: org/apache/commons/net/ntp/NTPUDPClient Allgemeine Java-Themen 6
T Java-Anfänger möchte professionell coden lernen Allgemeine Java-Themen 23
M Java 2D Array für ein Grid erstellen ? Allgemeine Java-Themen 2
H Java Dom Childelemente von de Childelemente von den Childelement bekommen Allgemeine Java-Themen 1
P USER Management in SQL übergreifend auf JAVA Programm Allgemeine Java-Themen 41
platofan23 Wie .txtDatei im Java Eclipse-Projekt bzw. in der Jar speichern? Allgemeine Java-Themen 7
Z Welches GUI Framework für Java ist aktuell? Allgemeine Java-Themen 16
I Java und XML Allgemeine Java-Themen 10
K Java Programmfluss Allgemeine Java-Themen 13
R Delete files before creating new from temp using Java file method Allgemeine Java-Themen 1
N Byte Array in Java "dekomprimieren" Allgemeine Java-Themen 3
N Convert.FromBase64 von C# für Java Allgemeine Java-Themen 11
C Java RMI Client - Server Allgemeine Java-Themen 0
Ullenboom Ein neues Java-Buch entsteht, willst du helfen? Allgemeine Java-Themen 7
N fixed-keyword von C# für Java Allgemeine Java-Themen 6
G Java Reflections Allgemeine Java-Themen 6
bueseb84 Java : Cannot find Symbol Allgemeine Java-Themen 7
N E-Mail per Java verschicken Allgemeine Java-Themen 2
Y Java Bruttoberechnen + runden Methode Allgemeine Java-Themen 1
Y Java Methoden unterschiedliche Zahlenreihen Allgemeine Java-Themen 2
M java.io.EOFException bei einem DataoutputStream ?! Allgemeine Java-Themen 2
D Java Kuriositäten / Rätsel Allgemeine Java-Themen 9
S File lesen und schreiben Java 6 Allgemeine Java-Themen 2
1 Java Scanner Allgemeine Java-Themen 2
J Key Keystore Certificate Java Android Development Allgemeine Java-Themen 1
J Java KeyStore Schlüssel Allgemeine Java-Themen 10
F Sich automatisch aufrufende Java-Methoden Allgemeine Java-Themen 2
M Java model class ? Allgemeine Java-Themen 9
C Java Script Pause berechnen Allgemeine Java-Themen 5
P Input/Output entfernte Datei mit Java öffnen ohne Download Allgemeine Java-Themen 5
M Java komplexe Map mit 2 values ? Allgemeine Java-Themen 8
bueseb84 Java Deploy to JFrog Repository Allgemeine Java-Themen 3
R Java mit Selenium "Geister"Loop Allgemeine Java-Themen 1

Ähnliche Java Themen


Oben