Subset sum problem mit Backtracking

[Gelöschtes Mitglied 59006]

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

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;
}

 

[Vega1]

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]

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]

Ich habe dir ein Beispiel zusammengebaut.

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:

[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]

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.

 

[Gelöschtes Mitglied 59006]

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

 

[Gelöschtes Mitglied 59006]

Ich habe dir ein Beispiel zusammengebaut.

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:

[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

 

[Gelöschtes Mitglied 59006]

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

 

[Flown]

Außerdem darf ich keine Java bibliotheken

Was ist damit gemeint? Darfst du keine zusätzlichen libraries verwenden oder die JDK libraries?

 

[Gelöschtes Mitglied 59006]

Was ist damit gemeint? Darfst du keine zusätzlichen libraries verwenden oder die JDK libraries?

ich darf nur Java.util.Arrays importieren
ansonsten keine zusätzlichen libraries
das heißt ich kann kein ArrayLists oder hashsets benutzen

 

[fhoffmann]

Hallo,

mich lässt diese Frage nicht los.
Es ist relativ einfach, das Problem mit einer rekursiven Methode zu lösen, beispielsweise folgendermaßen:

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

 

[MoxxiManagarm]

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:

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:

Required length: 63
[1, 5]
[6]

 

[MoxxiManagarm]

Ha! Ich habe die explizite Formel gefunden 😀 (das hat mich nicht losgelassen)
f(n) = n^2 - n + 1

 

[fhoffmann]

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:

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]

Und wie JCODA ebenfalls geschrieben hat, ist es das Ziel der Aufgabe, nicht all diese (exponentiel vielen) Möglichkeiten auszuprobieren.

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

Hatte ich geschrieben, ist ja auch kein großen Ding einfach an gegebener Stelle das Programm zu beenden.

 

[MoxxiManagarm]

Hier mal die abgewandelte Form

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");
    }
}

 

[Gelöschtes Mitglied 59006]

danke ihr alle für die Antwort
ich habe eine dp Lösung gefunden

 

[fhoffmann]

ich habe eine dp Lösung gefunden

Kannst du uns die Lösung bitte noch zeigen.
Und was bedeutet "dp"?

 

[mihe7]

Und was bedeutet "dp"?

Evtl. dynamische Programmierung.