Teilsummenproblem

Blubby0

Neues Mitglied
Aufgabe: Java Programm erstellen welches folgendes tut:
1. Eine Zahlenmenge einlesen ( Benutzer Fragen wie viele Zahlen er einlesen möchte und dann jede Zahl einzel in einem double Array abspeichern)
2. Alle Teilsummen berechnen und das Ergebnis welches am nächsten an Pi ist herausgeben.

Ich komme bei der Aufgabe nicht wirklich weiter. Der erste Teil ist mir klar mit dem zweiten habe ich meine Schwierigkeiten. Als Hilfestellung habe ich folgenden Pseudocode für Menge M der Länge n:

für alle ganzen Zahlen x von 0 bis 2^n
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 dem Ergebnis hinzu






So weit ich das verstehe ist 2^n die Anzahl an Teilsummen von M und die soll der Algorithmus berechnen und dann vergleichen welche Teilsumme am nächsten an Pi ist. Wenn ich also eine Menge mit drei Elementen (1,2) nehme dann sind dass 4 verschiedene Teilsummen nämlich:
0*1+0*2 ; 0*1+1*2; 1*1+0*2 ; 1*1+1*2
So verstehe ich jetzt die dritte Zeile des Pseudocodes. Ist das so richtig?
Ich verstehe das Prinzip des Pseudocodes nicht wirklich wenn mir das mal jemand erklären könnte wäre das super.
 

mihe7

Top Contributor
Du verstehst das schon richtig (im Code fehlen Indizes. Um das zu umgehen und auch der Lesbarkeit wegen solltest Du den Code so posten: [code]Dein Code[/code]).

Du hast eine Menge mit n Elementen. Wenn Du eine Teilsumme bildest, musst Du aussuchen, welche Elemente Du in die Teilsumme aufnimmst. D. h. für jedes der n Elemente kannst Du angeben, ob es in der Teilsumme enthalten sein soll (1) oder nicht (0). Formal dargestellt
Code:
        / 1 falls M[i] in Teilsumme enthalten
a[i] = {
        \ 0 sonst

Für jede Teilsumme kann also ein binäres Wort der Länge n angegeben werden:
a[n-1]a[n-2]...a[i]...a[2]a[1]a[0]

Es gibt 2^n mögliche Belegungen. Diesen lassen sich die Zahlen von 0 bis einschließlich 2^(n-1) eineindeutig zuordnen. Der Code zählt jetzt x einfach von 0 bis einschließlich 2^(n-1) durch, d. h. x entspricht genau einer von 2^n möglichen Belegungen. Mit i werden einfach die a[i] (s. oben) durchgezählt.[/i][/i]
 

Curtis_MC

Mitglied
Hallo,

ich habe ein ähnliches Problem und scheitere gerade an der Bildung von allen möglichen Teilsummen eines Arrays. Deinen Pseudocode habe ich mal probiert umzustellen:
Java:
for(int x=0; x<2^n;x++) {
      for(int i=0; i<n; i++) {
             if(x[i]==1) {
                sum+=M[i];
             }
      }
}

Das Grundprinzip mit der Umstellung in Binärdarstellung und Überprüfung, ob die Stelle eine 1 oder eine 0 ist, habe ich soweit verstanden, nur weiß ich nicht wie man das implementieren kann.Die Umwandlung in Binärdarstellung habe ich folgendermaßen gemacht:
Java:
 Integer.toBinaryString(zahl));

PS: Das ist mein erster Beitrag, entschuldigt also bitte Darstellungsfehler :)
 

mihe7

Top Contributor
Hallo, die Darstellung ist top!

In Java ist 2^n aber nicht die n-te Potenz von 2 sondern 2 XOR n. Die n-te Potenz von 2 findest Du mit Math.pow(2, n) oder auch (1 << n). Warum Du eine Summe bildest, weiß ich nicht aber vielleicht hat das irgendeinen tieferen Sinn in Deiner Aufgabe.

Die Umwandlung in Binärdarstellung habe ich folgendermaßen gemacht:
Das würde funktionieren, ist aber sehr teuer, so dass man das normalerweise anders macht. Aber erstmal zu Deiner Variante. In der ersten for-Schleife würdest Du das x in eine Binärzahl umwandeln
Java:
String binary = Integer.toBinaryString(x);
int len = binary.length() - 1; // brauchen wir gleich noch
In der zweiten for-Schleife würdest Du anhand des Strings prüfen, ob das i-te Bit gesetzt ist. Nun zählt man Bits aber von rechts, d. h. Du müsstest vom Ende des Strings ausgehen (daher die Variablen len):
Java:
if (i <= len && binary.charAt(len-i) == '1') { ... }

Mit wesentlich weniger Aufwand kommt man an das i-te Bit mit Hilfe binärer Operatoren, da das x intern bereits in binärer Form vorliegt.

Dazu braucht man lediglich in der zweiten for-Schleife zu prüfen:
Java:
if ((x & (1 << i)) != 0) { ... }
 

Curtis_MC

Mitglied
Hallo, vielen Dank für deine schnelle Antwort.
Danke für den Hinweis zur Potenz. Ich bin noch Anfänger in Java und kann jeden Tipp gut gebrauchen ;).

Ich habe einiges ausprobiert und folgenden Code erstellt:
Java:
int n = menge.length;  //menge ist mein Array, welches ich in der Main-Methode definiere ( Bsp.: menge[] = {1, 2};  )

for (int x = 0; x < (1 << n); x++) {
    System.out.print("{ ");

    for (int i = 0; i < n; i++) {

        if ((x & (1 << i)) != 0) {
            System.out.print(menge[i] + " ");
        }
    }
    System.out.println("}");
}
Damit werden mir alle Kombinationen in Form von {} {1} {2} {1 2} ausgegeben. Wie kann ich jetzt jede einzelne Möglichkeit addieren um mögliche Teilmengen zu erhalten? Zur Addition der Werte eines Arrays habe ich folgenden Code verwendet:
Java:
int summe = 0;
for (int m = 0; m < n; m++) {
     summe += menge[m];
}
Leider werden nur die Werte der letzten Möglichkeit {1, 2} addiert, sodass 3 dabei rauskommt. Die Additions-Funktion stimmt also, nur die Implementierung ist noch fehlerhaft. Das Ergebnis, sprich de Summe einer Möglichkeit, müsste ich noch irgendwie speichern, damit ich diese in weiteren Verlauf des Programms mit einem anderen Wert vergleichen kann.
Hast du da auch einen Tipp? Danke schonmal[/I]
 

mihe7

Top Contributor
Wenn ich Dich richtig verstanden habe: Du hast 2^n Kombinationen (von x = 0 bis x = 2^n-1) und für jede Kombination willst Du die Summe bilden. Also kannst Du ein Array der Größe 2^n anlegen und in diesem die Summen speichern.
 

Curtis_MC

Mitglied
Danke, ich habe es hinbekommen die Summe in einem Array zu speichern. Hatte einen kleinen, schusseligen Denkfehler :D
Leider steh ich jetzt vor einem viel größeren Problem und ich bin mir nicht sicher, ob mein Algorithmus das abbilden kann. Nachdem die Beste Teilsumme errechnet und ausgegeben wird, muss ich noch ausgeben, mit welcher Kombination diese beste Teilsumme berechnet wurde. Da in meiner findClosest-Methode das array bestehend aus allen möglichen Teilsummen übergeben wird und daraus das beste Element ausgegeben wird, habe ich keine Verknüpfung zwischen möglicher Kombination und dazugehöriger Teilsumme. Ich müsste also eine Verbindung herstellen. Das Problem ist glaube ich, dass ich die möglichen Kombinationen nicht in einem array speichere.
Hier mal mein Code:
Java:
static void subsets(double menge[]) {
    int n = menge.length;
    double summe = 0;
    int potenz = (1 << n);
    double array[] = new double[potenz]; // Array mit allen möglichen Teilsummen aus menge[]
    for (int x = 0; x < (1 << n); x++) {
        summe = 0;
        for (int i = 0; i < n; i++) {
            if ((x & (1 << i)) != 0) {
                summe += menge[i];
            }
        }
        array[x] = summe;
    }
    double pi = Math.PI;
    System.out.println("Best subset sum: ");
    System.out.println(findClosest(array, pi));
}

public static double findClosest(double array[], double pi) {
    int n = array.length;
    if (pi <= array[0]){
        return array[0];
}
    if (pi >= array[n - 1]){
        return array[n - 1];
}

    int i = 0, j = n, mid = 0;
    while (i < j) {
        mid = (i + j) / 2;

        if (array[mid] == pi){
            return array[mid];
}
        if (pi < array[mid]) {
            if (mid > 0 && pi > array[mid - 1])
                return getClosest(array[mid - 1], array[mid], pi);
            j = mid;
        }
        else {
            if (mid < n - 1 && pi < array[mid + 1])
                return getClosest(array[mid], array[mid + 1], pi);
            i = mid + 1;
        }
    }
    return array[mid];

}

public static double getClosest(double val1, double val2, double pi) {
    if (pi - val1 >= val2 - pi) {
        return val2;
    } else if (val1 == pi || val2 == pi) {
        return pi;
    } else {

        return val1;
    }
[/java]
Kann mir da jemand weiterhelfen? Besten Dank
 

Thorsten100

Neues Mitglied
Hey, habe das Problem auch, hat einer von euch denn jetzt eine vollständige Lösung zu dem Problem bzw. zu der ursprünglichen Aufgabe? Wäre sehr hilfreich, da ich ein kompletter Neuling im Programmieren bin und auch mit Dingen wie Arrays noch Probleme habe. Wäre wirklich top wenn jemand hierzu eine Lösung teilen könnte :)
 

Neue Themen


Oben