Subset sum problem mit Backtracking

  • Themenstarter Gelöschtes Mitglied 59006
  • Beginndatum
G

Gelöschtes Mitglied 59006

Gast
Hallo :) ich brauche Hilfe bei einer Aufgabe, ich bin noch Programmieranfänger
ich muss ein Subset als int[] von einen Array finden, die zu einer gegebene Zahl summiert.
also ein typisches Teilmengensummen Problem.
Nur ich darf das originale Array nicht sortieren und ich darf keine rekursion benutzen. Außerdem darf ich keine Java bibliotheken benutzen.
ich habe eine Lösung geschrieben aber mein Array ist entweder immer 0 oder sie enthält manche werte mehrere mals.
könnt ihr mir dabei helfen? hier meine Lösung, wenn ich das ergebnis im loop printe gibt sie richtige ergebnis, aber am ende enthält mein array viele Zahlen

Java:
public int[] DP() {
          long counter = 0;
            boolean sum = true;
            boolean print = false;
            int mySum = 0;
            int listi = 0;
            int[]last=new int[menge.length];
            while (counter < (1 << menge.length)) {
                if (sum) {
                    if (listi == menge.length) {
                        sum = false;
                        listi = 0;
                        print = mySum == summe;
                        if (!print) {
                            counter++;
                            mySum = 0;
                            sum = true;
                        }
                        continue;
                    }
                    if (((1L << listi) & counter) != 0) {
                        mySum += menge[listi];
                    }
                    listi += 1;
                    continue;
                } else if (print) {
                    if (listi == menge.length) {
                        System.out.println();
                        listi = 0;
                        counter++;
                        mySum = 0;
                        sum = true;
                        continue;
                    }
                    if (((1L << listi) & counter) != 0) {
                        last[listi]=menge[listi];
                        System.out.print(last[listi]);
                        System.out.print(" ");
                    }
                   
                    listi += 1;
                   continue;
                } else {
                   // throw new RuntimeException("Invalid state!");
                }
                break;
            }
            System.out.println();
            for(int i=0;i<last.length;i++) {
                System.out.print(last[i]+",");
            }
            return last;
}
 
Zuletzt bearbeitet von einem Moderator:

Vega1

Mitglied
Es ist leider völlig unklar, was du möchtest. Ein Subset, dessen Summe einer gegebenen Zahl entspricht? Code bitte immer in Java Code Tags.
 

MoxxiManagarm

Top Contributor
Er hat es etwas verwirrt erklärt, aber ich denke er will ein Array von möglichen Summen, die mit Elementen eines Input Arrays gebildet werden können.
 

MoxxiManagarm

Top Contributor
Ich habe dir ein Beispiel zusammengebaut.

Java:
int[] elements = {1, 2, 5, 7, 8};
int[] sums = new int[31];

int k = 0;
for (int i = 0; i < elements.length; i++) {
    for (int j = 0; j < k; j++) {
        sums[k + j] = sums[j] + elements[i];
    }
    k *= 2;

    sums[k++] = elements[i];
}

System.out.println(Arrays.toString(sums));

Ausgabe:
Code:
[1, 3, 2, 6, 8, 7, 5, 8, 10, 9, 13, 15, 14, 12, 7, 9, 11, 10, 14, 16, 15, 13, 16, 18, 17, 21, 23, 22, 20, 15, 8]

Folgende Problemstellungen sind hier noch offen:
1. Die Ausgabe ist nicht Unique, aber ich habe verstanden es soll unique sein
2. Ich habe die 31 im Beispiel fest reingeschrieben. Ich kenne zwar die rekursive Formel um den Wert zu berechnen, aber nicht die absolute. f(n) = f(n-1)*2+1 Ich bin kein Mathegenie, man kommt bestimmt aus der rekursiven Formel irgendwie auf die absolute, das überlasse ich dir.
 

JCODA

Top Contributor
f(n) = f(n-1)*2+1 Ich bin kein Mathegenie, man kommt bestimmt aus der rekursiven Formel irgendwie auf die absolute
Das sieht für mich aus wie die Kardinalität der Potenzmenge (Menge aller Teilmengen) und die ist 2^n (Jedes Element kann drin sein oder nicht.) 2^5 wäre 32. Die eins, die du abgezogen hast, scheint wohl die leere Menge zu sein, welche hier natürlich keine Rolle spielt.

Edit: hat natürlich wenig Relevanz für die obige Aufgabe, denn ich denke es geht darum ein wenig effizienter durch Backtracking zu sein. Dein Ansatz ist eher Bruteforce alle 2^n Möglichkeiten ausprobieren. Außerdem scheint noch relevant zu sein, durch welche Summanden die Summe zustande kam.
 
G

Gelöschtes Mitglied 59006

Gast
Es ist leider völlig unklar, was du möchtest. Ein Subset, dessen Summe einer gegebenen Zahl entspricht? Code bitte immer in Java Code Tags.
also ja ich brauchte ein subset dessen Summe ein gegenebe Zahl entspricht
ich möchte die Aufgabe mittels backtracking lösen
 
G

Gelöschtes Mitglied 59006

Gast
Ich habe dir ein Beispiel zusammengebaut.

Java:
int[] elements = {1, 2, 5, 7, 8};
int[] sums = new int[31];

int k = 0;
for (int i = 0; i < elements.length; i++) {
    for (int j = 0; j < k; j++) {
        sums[k + j] = sums[j] + elements[i];
    }
    k *= 2;

    sums[k++] = elements[i];
}

System.out.println(Arrays.toString(sums));

Ausgabe:
Code:
[1, 3, 2, 6, 8, 7, 5, 8, 10, 9, 13, 15, 14, 12, 7, 9, 11, 10, 14, 16, 15, 13, 16, 18, 17, 21, 23, 22, 20, 15, 8]

Folgende Problemstellungen sind hier noch offen:
1. Die Ausgabe ist nicht Unique, aber ich habe verstanden es soll unique sein
2. Ich habe die 31 im Beispiel fest reingeschrieben. Ich kenne zwar die rekursive Formel um den Wert zu berechnen, aber nicht die absolute. f(n) = f(n-1)*2+1 Ich bin kein Mathegenie, man kommt bestimmt aus der rekursiven Formel irgendwie auf die absolute, das überlasse ich dir.



Hallo, die summe ist fest gegeben , also in Ihre Besispiel, sei die summe 6, sollte meine Lösung {1,5} zurückgeben
also ich muss ein Subset finden deren Summe ein gegebene Zahl entspricht
 
G

Gelöschtes Mitglied 59006

Gast
Das sieht für mich aus wie die Kardinalität der Potenzmenge (Menge aller Teilmengen) und die ist 2^n (Jedes Element kann drin sein oder nicht.) 2^5 wäre 32. Die eins, die du abgezogen hast, scheint wohl die leere Menge zu sein, welche hier natürlich keine Rolle spielt.

Edit: hat natürlich wenig Relevanz für die obige Aufgabe, denn ich denke es geht darum ein wenig effizienter durch Backtracking zu sein. Dein Ansatz ist eher Bruteforce alle 2^n Möglichkeiten ausprobieren. Außerdem scheint noch relevant zu sein, durch welche Summanden die Summe zustande kam.
genau ich versuche eine Lösung mittels Backtracking zu finden, die Lösung (welche summanden die gegebene summe erreichen) als integer array zurückgeben
 

fhoffmann

Top Contributor
Hallo,

mich lässt diese Frage nicht los.
Es ist relativ einfach, das Problem mit einer rekursiven Methode zu lösen, beispielsweise folgendermaßen:
Java:
public class SubsetSum {
    public static void main(String[] args) {
        SubsetSum subsetSum = new SubsetSum();
        int[] elements = {1, 2, 5, 7, 8};
        int expectedSum = 6;
        int[] result = subsetSum.rekSubsetSum(elements, expectedSum);
        System.out.println(java.util.Arrays.toString(result));
    }

    int[] rekSubsetSum(int[] elements, int expectedSum) {
        int[] result = new int[elements.length];
        rekSubsetSum(elements, expectedSum, 0, result);
        return result;
    }

    boolean rekSubsetSum(int[] elements, int expectedSum, int pos, int[] result) {
        // System.out.println(pos + " " + expectedSum);
        if(elements[pos] == expectedSum) {
            result[pos] = elements[pos];
            return true;
        } else if (pos < elements.length - 1) {
            if (elements[pos] < expectedSum && rekSubsetSum(elements, expectedSum - elements[pos], pos + 1, result)) {
                result[pos] = elements[pos];;
                return true;
            } else {
                return rekSubsetSum(elements, expectedSum, pos + 1, result);
            }
        } else {
            return false;
        }
    }
}

// Ausgabe ist [1, 0, 5, 0, 0]
// diese Ausgabe entspricht nicht genau der Anforderung, lässt sich aber leicht korrigieren
Hat jemand eine Idee, wie man es ohne Rekursion (und ohne alle 2^n Möglichkeiten auszuprobieren) lösen kann?
(Im schlechtesten Fall muss man (vermutlich) dennoch 2^n Möglichkeiten durchtesten, da das Problen NP-vollständig ist.)
 
Zuletzt bearbeitet:

MoxxiManagarm

Top Contributor
Hat jemand eine Idee, wie man es ohne Rekursion (und ohne alle 2^n Möglichkeiten auszuprobieren) lösen kann?
Mein Ansatz von oben lässt sich relativ einfach umwandeln. Das Ergebnis sieht dann etwa so aus:
Java:
public class SubsetSum {
    public static int[] concat(int[] array, int element) {
        int[] biggerArray = new int[array.length + 1];

        for(int i = 0; i < array.length; i++) {
            biggerArray[i] = array[i];
        }
        biggerArray[array.length] = element;

        return biggerArray;
    }

    public static int sum(int[] array) {
        int sum = 0;

        for (int element : array) {
            sum += element;
        }

        return sum;
    }

    // Ich kenne 2 Berechnungsvarianten: Iterative Summe wie hier
    // oder rekursiv f(n) = 2*f(n-1) + 1
    // es gibt bestimmt auch eine explizite Formel, aber k.a. :D
    public static int requiredLength(int n) {
        int sum = 0;

        for (int i = 0; i < n; i++) {
            sum += Math.pow(2, i);
        }

        System.out.println("Required length: " + sum);
        return sum;
    }

    public static void main(String[] args) {
        int[] elements = {1, 2, 5, 7, 8, 6};
        int[][] combinations = new int[requiredLength(elements.length)][];
        int goalSum = 6;

        int k = 0;
        for (int i = 0; i < elements.length; i++) {
            for (int j = 0; j < k; j++) {
                combinations[k + j] = concat(combinations[j], elements[i]);
            }
            k *= 2;

            combinations[k++] = new int[] { elements[i] };
        }

        for (int[] combination : combinations) {
            if (sum(combination) == goalSum) {
                System.out.println(Arrays.toString(combination));
            }
        }
    }
}

Der Code sucht alle Möglichkeiten. Man könnte die Summe natürlich schon vorher testen und abbrechen, sobald ein Ergebnis gefunden wurde.

Ausgabe:
Code:
Required length: 63
[1, 5]
[6]
 
Zuletzt bearbeitet:

fhoffmann

Top Contributor
Hallo MoxxiManagram,

wie JCODA in #5 schon geschrieben hat, ist die Formel f(n) = 2^n - 1.

Und wie JCODA ebenfalls geschrieben hat, ist es das Ziel der Aufgabe, nicht all diese (exponentiel vielen) Möglichkeiten auszuprobieren.
Es soll davon ausgegangen werden dass alle Zahlen echt positiv sind. Wenn ich also folgende Zahlen habe:
Java:
int[] elements = {1, 2, 5, 7, 8, 6};
int goalSum = 6;
und bereits festgestellt habe, dass 1 + 2 + 5 = 8 > 6, brauche ich alle weiteren Kombinationen mit 1, 2, 5 gar nicht mehr auszuprobieren (also beispielsweise 1 + 2 + 5 + 7), da diese erst Recht größer als 6 sind.
 

MoxxiManagarm

Top Contributor

MoxxiManagarm

Top Contributor
Hier mal die abgewandelte Form

Java:
public class SubsetSum {
    public static int[] concat(int[] array, int element) {
        int[] biggerArray = new int[array.length + 1];

        for(int i = 0; i < array.length; i++) {
            biggerArray[i] = array[i];
        }
        biggerArray[array.length] = element;

        return biggerArray;
    }

    public static int sum(int[] array) {
        int sum = 0;

        for (int element : array) {
            sum += element;
        }

        return sum;
    }

    public static void main(String[] args) {
        int[] elements = {1, 2, 5, 7, 8};
        int n = elements.length;
        int maxCombinations = n * n - n + 1; // maximale Kombinationen die gehalten werden können
        int[][] combinations = new int[maxCombinations][];
        int goalSum = 6;

        int k = 0;
        for (int i = 0; i < elements.length; i++) {
            for (int j = 0; j < k; j++) {
                int[] combination = concat(combinations[j], elements[i]);
                int sum = sum(combination);

                if (sum < goalSum) {
                    combinations[k++] = combination;
                } else if(sum == goalSum) {
                    System.out.println("Found combination: " + Arrays.toString(combination));
                    return;
                }
            }

            if (elements[i] < goalSum) {
                combinations[k++] = new int[] { elements[i] };
            } else if(elements[i] == goalSum) {
                System.out.println("Found single element: " + elements[i]);
                return;
            }
        }

        System.out.println("No combination found");
    }
}
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
K Verständnis Problem bei Server/Client Java Basics - Anfänger-Themen 2
I WildFily - unterschiedliche Libs im Projekt verursachen Problem Java Basics - Anfänger-Themen 11
imocode Vererbung Problem mit Vererbung Java Basics - Anfänger-Themen 2
L Taschenrechner Problem Java Basics - Anfänger-Themen 4
I Applikationsserver (WildFly) - Zugriff auf Ressourcen.. Problem mit Pfade Java Basics - Anfänger-Themen 10
A ScheduledExecutorService problem Java Basics - Anfänger-Themen 7
marcelnedza Problem mit Weltzuweisung, JavaKarol Java Basics - Anfänger-Themen 13
XWing Methoden rückgabe Problem? Java Basics - Anfänger-Themen 6
M Erste Schritte Collatz Problem max int Java Basics - Anfänger-Themen 3
M Problem bei verschachtelter for-Schleife bei zweidimensionalen Arrays Java Basics - Anfänger-Themen 3
C GLOOP Problem beim Erstellen der Kamera Java Basics - Anfänger-Themen 9
nelsonmandela Problem bei Ausgabe einer Switch - Case Funktion Java Basics - Anfänger-Themen 5
frager2345 Problem mit Methode Java Basics - Anfänger-Themen 4
L Problem bei Rechnung mit Math.pow Java Basics - Anfänger-Themen 13
A Thread-Schreibe-Lese-Problem Java Basics - Anfänger-Themen 4
SUPERTJB return Problem Java Basics - Anfänger-Themen 3
sserio BigInteger Problem Java Basics - Anfänger-Themen 4
JordenJost Taschenrechner problem Java Basics - Anfänger-Themen 5
K Problem mit "Random" Java Basics - Anfänger-Themen 5
S Datei anlegen Problem! Groß- und Kleinschreibung wird nicht unterschieden Java Basics - Anfänger-Themen 4
sserio Problem beim Anzeigen Java Basics - Anfänger-Themen 5
xanxk Problem For-Schleife mit Charakter Java Basics - Anfänger-Themen 2
L Unbekanntes Problem mit 2d Array Java Basics - Anfänger-Themen 6
sserio Liste erstellt und ein Problem mit dem Index Java Basics - Anfänger-Themen 8
sserio Schwimmen als Spiel. Problem mit to String/ generate a card Java Basics - Anfänger-Themen 4
J Schleife Problem Java Basics - Anfänger-Themen 2
D Problem mit der Erkennung von \n Java Basics - Anfänger-Themen 2
milan123 das ist meine aufgabe ich hab das problem das bei mir Wenn ich die Richtung der Linien verändern will und drei davon sind richtig, verändere ich die 4 Java Basics - Anfänger-Themen 3
M Verständins Problem bei Aufgabe Java Basics - Anfänger-Themen 4
HeiTim Problem mit der Kommasetzung an der richtigen stelle Java Basics - Anfänger-Themen 59
Temsky34 Problem mit dem Code Java Basics - Anfänger-Themen 17
P Problem mit Calendar.getDisplayName() Java Basics - Anfänger-Themen 8
C Problem mit mehreren Methoden + Scanner Java Basics - Anfänger-Themen 5
P Datei einlesen, nach Begriff filtern und in Datei ausgeben. Problem Standardausgabe über Konsole Java Basics - Anfänger-Themen 19
M Problem mit Klassenverständnis und Button Java Basics - Anfänger-Themen 8
EchtKeineAhnungManchmal hallo habe ein Problem mit einer Datei -> (Zugriff verweigert) Java Basics - Anfänger-Themen 4
H Problem mit Verzweigungen Java Basics - Anfänger-Themen 6
H Problem mit Rückgabewert Java Basics - Anfänger-Themen 7
josfe1234 JAVA FX problem Java Basics - Anfänger-Themen 3
A Code Problem Java Basics - Anfänger-Themen 6
Henri Problem von Typen Java Basics - Anfänger-Themen 7
J Problem mit "ArrayIndexOutOfBoundsException" Java Basics - Anfänger-Themen 11
K jackson Mapping - Problem mit Zeitzonen Java Basics - Anfänger-Themen 10
B Threads Problem mit mehreren Threads Java Basics - Anfänger-Themen 38
I Output BigDecimal anstatt double / Problem beim Rechnen Java Basics - Anfänger-Themen 16
D Schleifen Problem Java Basics - Anfänger-Themen 2
H So viele Fehlermeldungen, dass ich nicht weiß wo das Problem ist. Java Basics - Anfänger-Themen 6
J JAVA-Problem blockiert MEDIATHEKVIEW Java Basics - Anfänger-Themen 13
T Problem mit Lehrzeichen und String bei einfacher Chiffre Java Basics - Anfänger-Themen 8
J extends Problem Java Basics - Anfänger-Themen 2
C Polymorphie-Problem Java Basics - Anfänger-Themen 3
Kalibru Problem bei Ausgabe von Objekt Java Basics - Anfänger-Themen 1
I Format Problem mit Wert - bekomme 0,10 anstatt 10,00 Java Basics - Anfänger-Themen 6
J Problem mit einer Methode die gewissen Inhalt einer Array löschen soll Java Basics - Anfänger-Themen 9
J Problem mit einer Methode, die beliebig viele Objekte in Array speichern soll Java Basics - Anfänger-Themen 6
J Allgemeines Problem mit Klassen Java Basics - Anfänger-Themen 5
U Problem mit dem initialisieren meines Strings in einer Schleife Java Basics - Anfänger-Themen 5
amgadalghabra algorithmisches Problem Java Basics - Anfänger-Themen 19
J Traveling Salesman Problem [Arrays] Java Basics - Anfänger-Themen 9
R ArrayList Problem Java Basics - Anfänger-Themen 6
InfinityDE Problem mit Datenübergabe an Konstruktor Java Basics - Anfänger-Themen 7
C RegEx Problem Java Basics - Anfänger-Themen 4
J Anfänger TicTacToe, Problem bei Gewinnoption, sowohl Unentschieden Java Basics - Anfänger-Themen 8
E Taschenrechner GUI Problem mit Fehlerhandling Java Basics - Anfänger-Themen 6
M Input/Output Fallunterscheidung Problem Java Basics - Anfänger-Themen 17
P Problem beim Überschreiben einer vererbten Methode Java Basics - Anfänger-Themen 4
M Problem bei Ausgabe Java Basics - Anfänger-Themen 7
Splayfer Java Array Problem... Java Basics - Anfänger-Themen 2
G Problem bei der Ausgabe einer Main Claase Java Basics - Anfänger-Themen 7
F Problem mit KeyListener in kombination mit dem ActionListener Java Basics - Anfänger-Themen 4
N Problem mit Scanner Java Basics - Anfänger-Themen 2
J Klassen Problem Java Basics - Anfänger-Themen 8
A Out.format problem. Java Basics - Anfänger-Themen 3
J Problem bei der Programmierung eines Tannenbaums Java Basics - Anfänger-Themen 9
A Array problem Java Basics - Anfänger-Themen 16
2 Taschenrechner mit GUI Problem bei der Berechnung Java Basics - Anfänger-Themen 8
W Remote Method Invocation RMI - Problem Java Basics - Anfänger-Themen 0
I Ich habe ein Problem Java Basics - Anfänger-Themen 3
A Problem bei returnen eines Wertes Java Basics - Anfänger-Themen 6
M Regex Erstellung Problem Java Basics - Anfänger-Themen 2
D Input/Output Problem bei der Benutzereingabe eines Befehls Java Basics - Anfänger-Themen 14
M (Sehr großes Problem) Listen als static in anderen Klassen verwendet Java Basics - Anfänger-Themen 12
F Habe ein problem mit dem ActionListener Java Basics - Anfänger-Themen 3
C Regex-Problem Java Basics - Anfänger-Themen 4
J Problem beim vergleich von zwei Integer Java Basics - Anfänger-Themen 3
M Problem in der Modellierung Java Basics - Anfänger-Themen 20
W Wo ist das URL-Problem ? Java Basics - Anfänger-Themen 1
S Generics-Problem: Class, Class<?>, Class<Object> Java Basics - Anfänger-Themen 4
D FileWriter / FileReader Problem Java Basics - Anfänger-Themen 10
G Problem beim Speichern von Objekten in einer Datei Java Basics - Anfänger-Themen 7
S Compiler-Fehler Exception in thread "main" java.lang.Error: Unresolved compilation problem: Java Basics - Anfänger-Themen 6
J Problem mit Array: 2 Klassen Java Basics - Anfänger-Themen 2
S Collections funktionale Listen (ListNode<E>) review und problem beim clone Java Basics - Anfänger-Themen 0
W OOP Vererbung und Problem bei Zählschleife in einer Methode Java Basics - Anfänger-Themen 10
C Problem mit If Else If und Überprüfung eines Counters Java Basics - Anfänger-Themen 3
F Problem mit Listen Java Basics - Anfänger-Themen 5
I wieder mit einer Umwandelung habe ich Problem (diesmal von char Array zu char) Java Basics - Anfänger-Themen 1
J Problem bei Umrechnung von Hex in Bin Java Basics - Anfänger-Themen 4
W Problem bei Programmierung von Monte-Carlo-Integration Java Basics - Anfänger-Themen 12
C Java Methoden "Parameter" Problem Java Basics - Anfänger-Themen 16

Ähnliche Java Themen

Neue Themen


Oben