Stabzerlegungsproblem / Optimierung

B

baker333

Bekanntes Mitglied
Servus,

da mir hier besser geholfen wird als in jedem VL Skript kommt hier wieder eines meiner Verständnisprobleme. Zum Glück ist es das letzte Kapitel bis zur Klausur. Es geht um Optimierungsprobleme:

Es geht um einen Stab, der geteilt werden kann und man nun herausfinden möchte, ob es sich lohnt den Stab als Ganzes zu verkaufen oder ihn zu teilen.
Eigentlich ist das Ganze jetzt recht trivial aber ich verstehe den Code nicht so ganz:

Java: 
public static int eisenSchneidenRek(int n, int [] p) {
        //Basisfall
        if (n==0) {
            return 0;
            
        }
        
        int optimum = p[n-1];
        for (int i =1; i<n; i++) {
            int aktuellerErloes = eisenSchneidenRek(i, p)+
                    eisenSchneidenRek(n-i,p);
            if(aktuellerErloes > optimum) {
                optimum = aktuellerErloes;
            }
            
            
        }
        
        return optimum;
    }

Es ist klar, dass wenn mein Stab die Länge 0 hat, dass der Preis auch 0 ist. Was aber genau übergebe ich oben für eine Preisliste? Im Skript steht "In unserem Fallbeispiel der Zerteilung einer Eisenstange ergibt sich bspw., wenn wir die Preisliste über ein Feld p von Ganzzahlen repräsentieren, bei der der Index i den Preis für eine Eisenstange der Länge i +1 angibt". Verstehe ich das richtig, dass im Prinzip einfach nur die Preisliste durchsucht wird, um den optimalen Erlös zu finden?
 
LimDul

LimDul

Top Contributor
Quasi. Durch die Rekursion wird jede mögliche Zerlegung geprüft und dafür der Preis ermittelt.

Stab der Länge 0: Preis von 0
Stab der Länge 1: Preis von p[0]
Stab der Länge 2: Preis von p[1] oder Preis zweier Stäbe der Länge 1
Stab der Länge 3: Preis von p[2] oder Preis zweier Stäbe der Länge 1 und 2 oder Preis zweier Stäbe der Länge 2 und 1
usw.
 
B

baker333

Bekanntes Mitglied
Ja, aber wie genau erfolgt jetzt der Zugriff auf die Preisliste?

Sprich wie genau greift eisenSchenidenRek auf das Array p an der Stelle n zu?
 
B

baker333

Bekanntes Mitglied
lennero hat gesagt.:
Die Methode bekommt die Preisliste doch als Parameter übergeben oder übersehe ich da etwas??

Edit: genaugenommen eine Referenz auf das Array Preisliste.
Zum Vergrößern anklicken....

Dann scheine ich ein grundsätzliches Verständnisproblem zu haben:

Ich übergebe der Methode eine Stablänge n und ein Array (Preisliste). Wieso ist jetzt der Aufruf von "eisenSchneidenRek(i, p) ein Zugriff auf den Wert am Index i des Arrays p?
 
B

baker333

Bekanntes Mitglied
Stimmt, ich habe mich falsch ausgedrückt. In der Preisliste sind ja die Preise für eine Eisenstange der Länge i +1 gespeichert. Aber wie werden diese Preise nun aufgerufen?
 
M

Meniskusschaden

Top Contributor
baker333 hat gesagt.:
Mir geht es um die FOR Schleife!
Zum Vergrößern anklicken....
Beispielsweise in der zweiten Schleifeniteration ist i=2. Dann werden durch rekursive Aufrufe der Methode die optimalen Preise für eine (evtl. weiter gestückelte) Stange der Länge 2 und eine (evtl. weiter gestückelte) Stange der Länge n-2 ermittelt und zusammengerechnet. Wenn das besser als das bisherige Optimum ist, ist es das neue Optimum.
 
mihe7

mihe7

Top Contributor
Code: 
e(5, p): es ist n=5 und zunächst optimum=p[n-1], also p[4]
  Schleife:
  e(1, p) + e(4, p)
  e(2, p) + e(3, p)
  e(3, p) + e(2, p)
  e(4, p) + e(1, p)

e(1,p): es ist n=1 und zunächst optimum=p[n-1], also p[0]
  Schleife: keine Iteration

e(4,p): es ist n=4 und zunächst optimum=p[n-1], also p[3]
  Schleife:
  e(1, p) + e(3, p)
  e(2, p) + e(2, p)
  e(3, p) + e(1, p)

e(3,p): es ist n=3 und zunächst optimum=p[n-1], also p[2]
  Schleife:
  e(1, p) + e(2, p)
  e(2, p) + e(1, p)

e(2,p): es ist n=2 und zunächst optimum=p[n-1], also p[1]
  Schleife:
  e(1, p) + e(1, p)

Das wäre der rekursive Abstieg für e(1, p) + e(4, p); da sich in den Schleifen keine anderen Berechnungen ergeben, sind alle Fälle aufgeführt.
 
B

baker333

Bekanntes Mitglied
Ich muss das ganze nochmal hervorbringen, weil ich gerade bei der Memoisation gelandet bin.
Ich persönlich sehe in dem u.g. Code jetzt nicht wirklich den Vorteil (im Gegensatz zu den Fibonacci Zahlen, wo man wirklich viele Zwischenergebnisse nicht doppelt berechnen musste).

Der Code speichert doch lediglich "nur" das optimum in einem Array. Eine wirkliche doppelte Berechnung umgeht man nicht wirklich, oder übersehe ich etwas?

Java: 
    //Memoisation = Speicherung von Zwischenergebnissen
    public int eisenSchneidenMemoised(int n, int [] p) {
        int[] r = new int[n];
        return eisenSchneidenMemoisedRek(n,p,r);
    }
   
    private int eisenSchneidenMemoisedRek(int n, int[] p, int[]r) {
        //Wenn der Wert bereits berechnet wurde, dann wird er ausgegeben.
        if (r[n-1] > 0) {
            return r[n-1];
        }
       
        if(n==0) {
            return 0;
        }
        int optimum = p[n-1];
        //mittels For-Schleife werden alle Stabzerlegungen durchgegangen
        for(int i = 1; i < n; ++i) {
            int aktuellerErloes = eisenSchneidenMemoisedRek(i,p,r)+ eisenSchneidenMemoisedRek(n-i,p,r);
            if(aktuellerErloes > optimum) {
                optimum = aktuellerErloes;
               
            }
        }
            r[n-1]=optimum;
            return optimum;
       
    }
 
M

Meniskusschaden

Top Contributor
baker333 hat gesagt.:
Der Code speichert doch lediglich "nur" das optimum in einem Array. Eine wirkliche doppelte Berechnung umgeht man nicht wirklich, oder übersehe ich etwas?
Zum Vergrößern anklicken....
Ich habe mal in beide Varianten ein paar Ausgabeanweisungen reingemurkst, um die jeweilige Aufrufhierarchie für ein Beispiel darzustellen (siehe Spoiler).
Code: 
┌eisenSchneidenRek(5, [3, 5, 7, 11, 13])
│ Startoptimum 13
│ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ Startoptimum 3
│ └return 3
│ ┌eisenSchneidenRek(4, [3, 5, 7, 11, 13])
│ │ Startoptimum 11
│ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 3
│ │ └return 3
│ │ ┌eisenSchneidenRek(3, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 7
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 5
│ │ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ │ Startoptimum 3
│ │ │ │ └return 3
│ │ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ │ Startoptimum 3
│ │ │ │ └return 3
│ │ │ │ aktuellerErloes 6
│ │ │ └return 6
│ │ │ aktuellerErloes 9
│ │ │ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 5
│ │ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ │ Startoptimum 3
│ │ │ │ └return 3
│ │ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ │ Startoptimum 3
│ │ │ │ └return 3
│ │ │ │ aktuellerErloes 6
│ │ │ └return 6
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ aktuellerErloes 9
│ │ └return 9
│ │ aktuellerErloes 12
│ │ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 5
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ aktuellerErloes 6
│ │ └return 6
│ │ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 5
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ aktuellerErloes 6
│ │ └return 6
│ │ aktuellerErloes 12
│ │ ┌eisenSchneidenRek(3, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 7
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 5
│ │ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ │ Startoptimum 3
│ │ │ │ └return 3
│ │ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ │ Startoptimum 3
│ │ │ │ └return 3
│ │ │ │ aktuellerErloes 6
│ │ │ └return 6
│ │ │ aktuellerErloes 9
│ │ │ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 5
│ │ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ │ Startoptimum 3
│ │ │ │ └return 3
│ │ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ │ Startoptimum 3
│ │ │ │ └return 3
│ │ │ │ aktuellerErloes 6
│ │ │ └return 6
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ aktuellerErloes 9
│ │ └return 9
│ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 3
│ │ └return 3
│ │ aktuellerErloes 12
│ └return 12
│ aktuellerErloes 15
│ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ Startoptimum 5
│ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 3
│ │ └return 3
│ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 3
│ │ └return 3
│ │ aktuellerErloes 6
│ └return 6
│ ┌eisenSchneidenRek(3, [3, 5, 7, 11, 13])
│ │ Startoptimum 7
│ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 3
│ │ └return 3
│ │ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 5
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ aktuellerErloes 6
│ │ └return 6
│ │ aktuellerErloes 9
│ │ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 5
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ aktuellerErloes 6
│ │ └return 6
│ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 3
│ │ └return 3
│ │ aktuellerErloes 9
│ └return 9
│ aktuellerErloes 15
│ ┌eisenSchneidenRek(3, [3, 5, 7, 11, 13])
│ │ Startoptimum 7
│ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 3
│ │ └return 3
│ │ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 5
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ aktuellerErloes 6
│ │ └return 6
│ │ aktuellerErloes 9
│ │ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 5
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ aktuellerErloes 6
│ │ └return 6
│ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 3
│ │ └return 3
│ │ aktuellerErloes 9
│ └return 9
│ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ Startoptimum 5
│ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 3
│ │ └return 3
│ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 3
│ │ └return 3
│ │ aktuellerErloes 6
│ └return 6
│ aktuellerErloes 15
│ ┌eisenSchneidenRek(4, [3, 5, 7, 11, 13])
│ │ Startoptimum 11
│ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 3
│ │ └return 3
│ │ ┌eisenSchneidenRek(3, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 7
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 5
│ │ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ │ Startoptimum 3
│ │ │ │ └return 3
│ │ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ │ Startoptimum 3
│ │ │ │ └return 3
│ │ │ │ aktuellerErloes 6
│ │ │ └return 6
│ │ │ aktuellerErloes 9
│ │ │ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 5
│ │ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ │ Startoptimum 3
│ │ │ │ └return 3
│ │ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ │ Startoptimum 3
│ │ │ │ └return 3
│ │ │ │ aktuellerErloes 6
│ │ │ └return 6
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ aktuellerErloes 9
│ │ └return 9
│ │ aktuellerErloes 12
│ │ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 5
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ aktuellerErloes 6
│ │ └return 6
│ │ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 5
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ aktuellerErloes 6
│ │ └return 6
│ │ aktuellerErloes 12
│ │ ┌eisenSchneidenRek(3, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 7
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 5
│ │ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ │ Startoptimum 3
│ │ │ │ └return 3
│ │ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ │ Startoptimum 3
│ │ │ │ └return 3
│ │ │ │ aktuellerErloes 6
│ │ │ └return 6
│ │ │ aktuellerErloes 9
│ │ │ ┌eisenSchneidenRek(2, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 5
│ │ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ │ Startoptimum 3
│ │ │ │ └return 3
│ │ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ │ Startoptimum 3
│ │ │ │ └return 3
│ │ │ │ aktuellerErloes 6
│ │ │ └return 6
│ │ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ │ Startoptimum 3
│ │ │ └return 3
│ │ │ aktuellerErloes 9
│ │ └return 9
│ │ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ │ Startoptimum 3
│ │ └return 3
│ │ aktuellerErloes 12
│ └return 12
│ ┌eisenSchneidenRek(1, [3, 5, 7, 11, 13])
│ │ Startoptimum 3
│ └return 3
│ aktuellerErloes 15
└return 15
┌eisenSchneidenMemoisedRek(5, [3, 5, 7, 11, 13], [0, 0, 0, 0, 0])
│ Startoptimum 13
│ ┌eisenSchneidenMemoisedRek(1, [3, 5, 7, 11, 13], [0, 0, 0, 0, 0])
│ │ Startoptimum 3
│ └return 3
│ ┌eisenSchneidenMemoisedRek(4, [3, 5, 7, 11, 13], [3, 0, 0, 0, 0])
│ │ Startoptimum 11
│ │ ┌eisenSchneidenMemoisedRek(1, [3, 5, 7, 11, 13], [3, 0, 0, 0, 0])
│ │ └return 3
│ │ ┌eisenSchneidenMemoisedRek(3, [3, 5, 7, 11, 13], [3, 0, 0, 0, 0])
│ │ │ Startoptimum 7
│ │ │ ┌eisenSchneidenMemoisedRek(1, [3, 5, 7, 11, 13], [3, 0, 0, 0, 0])
│ │ │ └return 3
│ │ │ ┌eisenSchneidenMemoisedRek(2, [3, 5, 7, 11, 13], [3, 0, 0, 0, 0])
│ │ │ │ Startoptimum 5
│ │ │ │ ┌eisenSchneidenMemoisedRek(1, [3, 5, 7, 11, 13], [3, 0, 0, 0, 0])
│ │ │ │ └return 3
│ │ │ │ ┌eisenSchneidenMemoisedRek(1, [3, 5, 7, 11, 13], [3, 0, 0, 0, 0])
│ │ │ │ └return 3
│ │ │ │ aktuellerErloes 6
│ │ │ └return 6
│ │ │ aktuellerErloes 9
│ │ │ ┌eisenSchneidenMemoisedRek(2, [3, 5, 7, 11, 13], [3, 6, 0, 0, 0])
│ │ │ └return 6
│ │ │ ┌eisenSchneidenMemoisedRek(1, [3, 5, 7, 11, 13], [3, 6, 0, 0, 0])
│ │ │ └return 3
│ │ │ aktuellerErloes 9
│ │ └return 9
│ │ aktuellerErloes 12
│ │ ┌eisenSchneidenMemoisedRek(2, [3, 5, 7, 11, 13], [3, 6, 9, 0, 0])
│ │ └return 6
│ │ ┌eisenSchneidenMemoisedRek(2, [3, 5, 7, 11, 13], [3, 6, 9, 0, 0])
│ │ └return 6
│ │ aktuellerErloes 12
│ │ ┌eisenSchneidenMemoisedRek(3, [3, 5, 7, 11, 13], [3, 6, 9, 0, 0])
│ │ └return 9
│ │ ┌eisenSchneidenMemoisedRek(1, [3, 5, 7, 11, 13], [3, 6, 9, 0, 0])
│ │ └return 3
│ │ aktuellerErloes 12
│ └return 12
│ aktuellerErloes 15
│ ┌eisenSchneidenMemoisedRek(2, [3, 5, 7, 11, 13], [3, 6, 9, 12, 0])
│ └return 6
│ ┌eisenSchneidenMemoisedRek(3, [3, 5, 7, 11, 13], [3, 6, 9, 12, 0])
│ └return 9
│ aktuellerErloes 15
│ ┌eisenSchneidenMemoisedRek(3, [3, 5, 7, 11, 13], [3, 6, 9, 12, 0])
│ └return 9
│ ┌eisenSchneidenMemoisedRek(2, [3, 5, 7, 11, 13], [3, 6, 9, 12, 0])
│ └return 6
│ aktuellerErloes 15
│ ┌eisenSchneidenMemoisedRek(4, [3, 5, 7, 11, 13], [3, 6, 9, 12, 0])
│ └return 12
│ ┌eisenSchneidenMemoisedRek(1, [3, 5, 7, 11, 13], [3, 6, 9, 12, 0])
│ └return 3
│ aktuellerErloes 15
└return 15
 
M

Meniskusschaden

Top Contributor
Habe vergessen, den angepassten Quellcode zu posten. Hier für die Variante mit Memoisation:
Java: 
import java.util.Arrays;

public class EisenSchneider2 {
    private static final char HORIZONTALEDGE = '\u2500';
    private static final char VERTICALEDGE = '\u2502';
    private static final char TOPLEFTCORNER = '\u250c';
    private static final char BOTTOMLEFTCORNER = '\u2514';

    public static void main(String[] args) {
        System.out.println(eisenSchneidenMemoised(5, new int[] { 3, 5, 7, 11, 13 }));
    }

    public static int eisenSchneidenMemoised(int n, int[] p) {
        int[] r = new int[n];
        return eisenSchneidenMemoisedRek(0, n, p, r);
    }

    private static int eisenSchneidenMemoisedRek(int level, int n, int[] p, int[] r) {
        print("eisenSchneidenMemoisedRek(" + n + ", " + Arrays.toString(p) + ", " + Arrays.toString(r) + ")", level, TOPLEFTCORNER);

        // Wenn der Wert bereits berechnet wurde, dann wird er ausgegeben.
        if (r[n - 1] > 0) {
            print("return " + r[n-1], level, BOTTOMLEFTCORNER);
            return r[n - 1];
        }

        if (n == 0) {
            return 0;
        }
        int optimum = p[n - 1];
        print(" Startoptimum " + optimum, level, VERTICALEDGE);
        
        // mittels For-Schleife werden alle Stabzerlegungen durchgegangen
        for (int i = 1; i < n; ++i) {
            int aktuellerErloes = eisenSchneidenMemoisedRek(level+1, i, p, r) + eisenSchneidenMemoisedRek(level+1, n - i, p, r);
            print(" aktuellerErloes " + aktuellerErloes, level, VERTICALEDGE);
            if (aktuellerErloes > optimum) {
                optimum = aktuellerErloes;

            }
        }
        r[n - 1] = optimum;
        print("return " + optimum, level, BOTTOMLEFTCORNER);
        return optimum;
    }

    private static void print(String text, int level, char prefix) {
        for (int i = 0; i < level; i++) {
            System.out.print(VERTICALEDGE + " ");
        }
        System.out.println("" + prefix + text);
    }

}
 
B

baker333

Bekanntes Mitglied
Aber wieso wird das Array r mit mehreren Werten gefüttert? es gibt doch lediglich die Anweisung r[n-1] = optimum undn steht doch immer fest. Vielen Dank für Deine detaillierte Ausführung.

Edit: Ich rede Unfug, die Methode wird ja rekursiv mit unterschiedlichen "n" aufgerufen.
 
B

baker333

Bekanntes Mitglied
Das nächste woran ich noch hänge ist diese Bottom up Lösung. Ich verstehe, dass ich ein Array erstelle und es mit Werten füttere. Ich stehe beim Aufruf völlig auf dem Schlauch.
Java: 
public static int eisenSchneidenIt(int n, int[] p) {
        int[] r = new int[n];
        for (int j = 1; j <= n; ++j) {
            //Optimum ist zunächst der Preis an Indexstelle 0 des Arrays p, Array p wird dann durchlaufen.
            int optimum = p[j-1];
                for (int i = 1; i<j; ++i) {
                    int aktuellerErloes = r[i-1] + r[j-i-1];
                    if (aktuellerErloes > optimum) {
                        optimum = aktuellerErloes;
                    }   
        //Optimum im Array r gespeichert
        r[j-1]= optimum;
        }
    }
    
    return r[n-1];
    
    }
 
B

baker333

Bekanntes Mitglied
okay, ich glaube ich habs, ich muss sagen, dass das ganze im Prinzip nicht so schwer ist. Das, was mich verwirrt, sind die unzähligen Methodenaufrufe, vor allem, weil in der rekursiven Methode durch die for-Schleife ja die Methode unzählige Male aufgerufen wird. Da stockt mein Gehirn noch etwas. Da muss ich mich immer durch wurschteln :D
 
B

baker333

Bekanntes Mitglied
also ich stehe doch noch etwas auf dem Schlauch, mir wird folgendes ausgegeben mit p = {3, 5, 7, 11, 13}:


0 //da r leer ist, muss ja der aktuelleErloes zunächst 0 sein
5 // warum 5? optimum ist doch p[j-1] --> p[0] und das ist 3

5
7

5
7

7
11

10
11

7
11

11
13

12
13

12
13

11
13




Java: 
public static int eisenSchneidenIt(int n, int[] p) {
        int[] r = new int[n];
        for (int j = 1; j <= n; ++j) {
            //Optimum ist zunächst der Preis an Indexstelle 0 des Arrays p, Array p wird dann durchlaufen.
            int optimum = p[j-1];
            //System.out.println(optimum);
                for (int i = 1; i<j; ++i) {
                    int aktuellerErloes = r[i-1] + r[j-i-1];
                    if (aktuellerErloes > optimum) {
                        optimum = aktuellerErloes;           
                    }   
        //Optimum im Array r gespeichert
        
        System.out.println(aktuellerErloes);
        System.out.println(optimum);
        System.out.println();
        
        r[j-1]= optimum;
        }
    }

    return r[n-1];
 
B

baker333

Bekanntes Mitglied
Ich stehe echt auf dem Schlauch: wenn ich mir r anzeigen lasse erhlate ich folgende Ausgabe:

[0, 5, 7, 11, 13]

Auch hier: warum ist der erste Wert des Arrays 0, wenn vorher optimum = p[j-1] //das ist ja 3 gilt.
 
B

baker333

Bekanntes Mitglied
Nun ja, die innere for-Schleife wird sofort abgebrochen, da i=j, deswegen wird j auf 2 erhöht und
Java: 
r[1-1] = optimum
nicht ausgeführt, korrekt?
 
B

baker333

Bekanntes Mitglied
Okay. Auf den Code für diese Bottom - up Lösung wäre ich in der Klausur nie gekommen. Dass das eine iterative Lösung ist, ist mir klar. Warum heißt sowas denn bottom up Lösung und ich vermute, dass der Lösungsansatz für solche "Probleme" bzw. Aufgaben immer ähnlich ist?
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
A Optimierung eines Programms: Mergen der Dateien Java Basics - Anfänger-Themen 23
CptK Optimierung von Flächen Java Basics - Anfänger-Themen 9
Y "Optimierung" des Codes Java Basics - Anfänger-Themen 14
T Auslesen der Zwischenablage - Optimierung Geschwindigkeit Java Basics - Anfänger-Themen 6
M Code Optimierung - Verbesserungen Java Basics - Anfänger-Themen 10
S Optimierung bzw. verschönerung des Quellcodes Java Basics - Anfänger-Themen 9
F code Optimierung (Bin-Hex-Bytes) Java Basics - Anfänger-Themen 9
A Frage zur Laufzeit / Optimierung Java Basics - Anfänger-Themen 2
P JUnit - Optimierung der Testklassen Java Basics - Anfänger-Themen 13
-horn- "Berechnung vorwärts, Optimierung rückwärts?" - Wie würdet ihr das machen? Java Basics - Anfänger-Themen 8
T synchronisations-optimierung Java Basics - Anfänger-Themen 2

Ähnliche Java Themen

Aktuelle Jobs

Neue Themen


Oben