Teilsummenproblem in Java

tm.grp

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

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

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
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 0
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
M SQL-Developer Installation: Unable to launch the Java Virtual Machine Located at path msvcr100.dll Allgemeine Java-Themen 1
L Java frage Allgemeine Java-Themen 3
D Verkauf von einem Programm welches ich in Java geschrieben habe Allgemeine Java-Themen 4
M this application requires a java runtime environment 1.8.0 Allgemeine Java-Themen 2
W Haben Konstruktoren in Java eigentlich immer mindestens einen Parameter? Allgemeine Java-Themen 4
N Kurs Java Oraclce Certified Allgemeine Java-Themen 0
C Java und die IDE´s und die Zukunft Allgemeine Java-Themen 11
M Java – Warum kann ich plötzlich bei Android Studio Grafische Benutzeroberflächen mit der Maus gestalten? Allgemeine Java-Themen 5
M JAVA API in Eclipse auf deutsch Allgemeine Java-Themen 18
hello_autumn Java_Home geändert auf Java 13, trotzdem wird Java Version 8 angezeigt. Allgemeine Java-Themen 2
S Java.exe exestiert, aber irgendwie auch nicht Allgemeine Java-Themen 11
J CMD Befehl in Java Consolenprogramm ausführen Allgemeine Java-Themen 6
Bluedaishi Java versteckte Partition Allgemeine Java-Themen 9
O Java-Applikation tut in Netbeans, als JAR nicht, wegen Pfadangaben einer benötigten Datei Allgemeine Java-Themen 8
M Hilfe bei einer Java Programmieraufgabe! Ab morgen Montag um 08:00 Uhr Allgemeine Java-Themen 5
W Java Telegram Bot - Eingabe durch User Allgemeine Java-Themen 2
A Java-Webanwendung Allgemeine Java-Themen 7
Tashtego Externe Java Klasen zur Laufzeit einbinden Allgemeine Java-Themen 10
K Binärbäume in Java Allgemeine Java-Themen 2
P Swing Exception in thread "AWT-EventQueue-0" java.lang.IndexOutOfBoundsException: npoints > xpoints.length || npoints > ypoints.length Allgemeine Java-Themen 5
M Java 8 nach Java 6 konvertieren Allgemeine Java-Themen 7
S Java verknüpft mit Aseba Allgemeine Java-Themen 0
Tashtego Java 8 Security Update Allgemeine Java-Themen 3
U Klassen Komplexe Datenstruktur in Java Allgemeine Java-Themen 4
B Java Mail: Prüfung auf neue Emails Allgemeine Java-Themen 1
B Java Mail: Emails sortieren? Allgemeine Java-Themen 5
B Java Mail: Prüfen, ob Email hat ein Anhang oder nicht Allgemeine Java-Themen 2
T Java-Quiz Code Fehler Allgemeine Java-Themen 10
X Collections Gibt es eine Klasse welche die Vorteile von List und HashMap vereint, aber konstante Laufzeit (O(1)) hat in Java? Allgemeine Java-Themen 4
L Python in Java ausführen Allgemeine Java-Themen 4
L Nach dem Login // Java Desktop Software Allgemeine Java-Themen 7
V Maus mitthilfe Bewegungssensor steuern (Java) Allgemeine Java-Themen 12
L Eclipse Java Code ausführen Allgemeine Java-Themen 18
S Java SAT (Haltbarkeitsproblem) mit Regex Allgemeine Java-Themen 6
D Was sind Bibliotheken in Java/Pyhton? Allgemeine Java-Themen 1
L Echtzeitdaten aus einer Webseite ziehen mit Java Allgemeine Java-Themen 19
F Java Code ausführen direkt nach Anmelden in Windows Allgemeine Java-Themen 2
F Java Web App - welche Technologien? Allgemeine Java-Themen 11
B Java Mail: Unterscheidung bei Attachments und eingefügte Bilder in Email Allgemeine Java-Themen 18

Ähnliche Java Themen

Anzeige

Neue Themen


Oben