Subset sum problem mit Backtracking

L

Lama-rajjo

Mitglied
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:
V

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

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

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

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.
 
L

Lama-rajjo

Mitglied
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
 
L

Lama-rajjo

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

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

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

MoxxiManagarm

Top Contributor
Ha! Ich habe die explizite Formel gefunden :D (das hat mich nicht losgelassen)
f(n) = n^2 - n + 1
 
F

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

MoxxiManagarm

Top Contributor
MoxxiManagarm

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
J Allgemeines Problem mit Klassen Java Basics - Anfänger-Themen 2
U Problem mit dem initialisieren meines Strings in einer Schleife Java Basics - Anfänger-Themen 4
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
S 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
T Bruchrechner Problem Java Basics - Anfänger-Themen 16
M Problem mit meinem Programm Java Basics - Anfänger-Themen 6
pkm Problem mit der JSP-Syntax Java Basics - Anfänger-Themen 2
J Rückgabe-Problem Java Basics - Anfänger-Themen 10
D Problem mit der Serialisierung Java Basics - Anfänger-Themen 31
W Problem mit dem Wert von boolean-Variable Java Basics - Anfänger-Themen 3
W Problem mit Konsolenausgabe bei StringTokenizer Java Basics - Anfänger-Themen 2
O Verständniss Problem bei abstract class Java Basics - Anfänger-Themen 7
K Java Problem mit Übergabe von argumenten Java Basics - Anfänger-Themen 3
J "travelling salesman problem" mit Java Editor Java Basics - Anfänger-Themen 17
M Problem mit ArrayList Java Basics - Anfänger-Themen 32
B Array Problem Java Basics - Anfänger-Themen 3
O Problem mit SOAP / javax.xml importieren Java Basics - Anfänger-Themen 7
V Variablen Problem mit Matheaufgabe / int first = mScanner.nextInt(); Java Basics - Anfänger-Themen 5
X Problem mit Arraylist in Arraylist Java Basics - Anfänger-Themen 2
cpt.Tomato Scanner problem mit Passwort Login Java Basics - Anfänger-Themen 3
F Switch Case Problem mit Regex lösen? Java Basics - Anfänger-Themen 6
CT9288 Mini Anfänger-Problem mit loops, statements und ; Java Basics - Anfänger-Themen 4
C Two-Center Problem in Java Java Basics - Anfänger-Themen 0
H regex-Problem Java Basics - Anfänger-Themen 2
J Problem bei seriellem Start von Threads Java Basics - Anfänger-Themen 11
E Weg-Suche-Problem rekursiv Java Basics - Anfänger-Themen 12
C Problem: PC ohne Internet und keine Möglichkeit Programme zu laden Java Basics - Anfänger-Themen 5
E Problem mit static Methode Java Basics - Anfänger-Themen 4
J Problem bei Aufgabe "Geldstückelung" Java Basics - Anfänger-Themen 5
P Problem bei Java-Aufgabe Java Basics - Anfänger-Themen 12
T Rückgabewert Problem Java Basics - Anfänger-Themen 2
O Problem gleiche Zahlen Java Basics - Anfänger-Themen 2
C Methoden Problem beim Speichern von Variablen Java Basics - Anfänger-Themen 1
W Problem bei JUnit Test Aufgabe Java Basics - Anfänger-Themen 15
D Break Sprungmarken Problem einer While True in While True Java Basics - Anfänger-Themen 6
J "Tetris" - Problem bei der Grafik Java Basics - Anfänger-Themen 5
L Klassen NFC Reader und JavaFx Problem -> threads? Java Basics - Anfänger-Themen 2
C Hamster Simulator Problem Java Basics - Anfänger-Themen 2
S CSV auslesen UTF-8 Problem Java Basics - Anfänger-Themen 7
F Problem beim entfernen von mehreren Listenelementen auf einmal (Programmierung des Spiels Arschloch) Java Basics - Anfänger-Themen 1
felix92 eclipse Problem Java Basics - Anfänger-Themen 12
J unzip Problem Java Basics - Anfänger-Themen 5
J Pizza und Pasta Problem.. Java Basics - Anfänger-Themen 19
F Problem mit der Aufgabe(Array) Java Basics - Anfänger-Themen 21
X Erste Schritte Problem mit scanner Java Basics - Anfänger-Themen 2
J GUI-Problem Java Basics - Anfänger-Themen 4
C Problem mit der Aufgabe Java Basics - Anfänger-Themen 3
L Problem mit Android ListView Java Basics - Anfänger-Themen 2
J String Problem kann das einer erklären Java Basics - Anfänger-Themen 13
R Schaltjahr problem Java Basics - Anfänger-Themen 10
S Doppel For Schleife mit Arrays - Problem bei der Ausgabe Java Basics - Anfänger-Themen 4
R Problem mit Code Java Basics - Anfänger-Themen 3
scitex Problem mit JFormattedTextField Java Basics - Anfänger-Themen 2
D Problem mit Installation von JRE Java Basics - Anfänger-Themen 2
_0815_ Problem mit dem Automatischen eintragen in Textdateien Java Basics - Anfänger-Themen 1
L PROBLEM! "Bug" bei Konto-Projekt! Java Basics - Anfänger-Themen 7
H boolean Array Problem Java Basics - Anfänger-Themen 7
javajoshi Problem mit zwei Threads und Arrays (Runnable) Java Basics - Anfänger-Themen 12
M Textfield Problem Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Anzeige

Neue Themen


Oben