Memoization in Java

[districon]

Hallo,
irgendwo muss hier ein Fehler in meinem Code sein. Ich suche schon lange und finde ihn einfach nicht.
Kann mir jmd helfen meinen Fehler zu finden? Danke



public class VeggieWahn {

public class VeggieWahn {

    private static long Wuerzmischungen(int v, int g, long[][] memo) {
       if (v == g) {
            return 1;
        } else if (v == 1){
            return memo[1][g];
        } else if(memo[v][g] != 0) {
            return memo[v][g];
        }
        if (memo[v][g] != 0){
            memo[v][g] = (Wuerzmischungen(v-1,g,memo))+(v*Wuerzmischungen(v,g-1,memo));
            return memo[v][g];
        }
    }
    public static long essen(int v, int g) {
        if (g <= 123 == false) {
            return 0;
        } if (v <= g == false) {
            return 0;
        } if (1 <= v == false) {
            return 0;
        }else {
            long [][] memo = new long [v+1][g+1];
        return 2 * (Wuerzmischungen(v,g,memo) + v);


    }

    }

 

[LimDul]

Viel Erfolg beim Suchen.

Der Code tut Dinge. Ob er die richtigen tut, kann man nicht beurteilen, weil man nicht weiß, was er tun soll.

 

[districon]

Das Küchenpersonal der Mensa hat ein Problem: In einer Umfrage haben sich die Studierenden über das angeblich fade Essen beschwert und zusätzlich gefordert, dass jedes Gericht auch vegan angeboten werden muss. Hier nun der Plan des Studentenwerks:

• Es werden mindestens so viele Gewürze g angeschafft, wie es vegane Grundgerichte v gibt, aus Kostengründen aber maximal 123 verschiedene Gewürze (1 ≤ v ≤ g ≤ 123).
  
  
• Jedes Gericht soll mit mindestens einem Gewürz abgeschmeckt werden.
  
  
• Jedes Gewürz soll für genau ein Gericht verwendet werden.
  
  
• Alle veganen Grundgerichte schmecken ungewürzt gleich und sehen auch identisch aus.
  
  
• Bei nicht-veganen Gerichten wird einfach zusätzlich etwas Hackfleisch reingekippt.
  
  Die Verteilung der g Gewürze auf die v veganen Grundgerichte soll möglichst abwechslungsreich gestaltet werden. Für die Erstellung des wöchentlichen Speiseplans muss das Studentenwerk be- stimmen, wie viele unterschiedliche Würzmischungen Wv,g auf diesem Wege überhaupt möglich sind und schließlich wie viele verschiedene Essen Ev,g im Speiseplan stehen werden:
  • Bei gleich vielen veganen Gerichten wie Gewürzen (v = g) gibt es eine Würzung Wv,g = 1: Jedes vegane Gericht bekommt genau eines der Gewürze.
    
    
  • Bei nur einem veganen Gericht (v = 1) gibt ebenfalls genau eine Würzmöglichkeit Wv,g = 1: Alle Gewürze werden in das eine Gericht zusammengekippt.
    
    
  • AndernfallsgibtesweitereKochtricks:MannehmedaserstbesteGewürzGzurHandund...
    • – entweder gibt es ein Gericht, das nur mit diesem einen Gewürz G abgeschmeckt wird, dann verteilen sich die restlichen g − 1 Gewürze auf die anderen v − 1 Gerichte;
      
      
    • – oder das Gewürz G kommt zusammen mit anderen Gewürzen in das gleiche Gericht, dann werden zuerst die anderen g − 1 Gewürze auf alle v Gerichte verteilt (ergibt Wv,g−1 Würzmischungen) und anschließend wird das aktuelle Gewürz G zu einem beliebigen der v Gerichte hinzugefügt (wofür es v Möglichkeiten gibt).

Das macht dann insgesamt Wv,g = Wv−1,g−1 + v · Wv,g−1 vegane Würzmischungen.
• Die v veganen Grundgerichte und die Wv,g Würzmischungen werden schließlich sowohl mit

als auch ohne Hackfleisch zu Ev,g = 2 · Wv,g unterschiedliche Essen zusammengerührt.

 

[districon]

Ich versuche die Anzahl E herauszufinden

 

[LimDul]

if (memo[v][g] != 0){
            memo[v][g] = (Wuerzmischungen(v-1,g,memo))+(v*Wuerzmischungen(v,g-1,memo));
            return memo[v][g];
        }

Der Teil wird nie durchlaufen - da vorher, wenn der Wert != 0 ist, bereits eine Rückgabe erfolgt.

} else if (v == 1){
            return memo[1][g];
}

Wie stellst du sicher das in dem Fall in dem Array der richtige Wert drin steht? Was soll den laut Aufgabe, zurückgegeben werden, wenn v=1 ist.

 

[districon]

} else if (v == 1){
            return 1;
}

Also ist es so? Wie ich das andere lösen soll weiß ich nicht genau

 

[LimDul]

Korrekt.

Nun wie funktioniert memoization - du speicherst Werte zwischen. Das heißt, wenn in memo[v][g] schon ein Wert drinsteht, (also != 0 ist), dann wird der zurückgegeben, anstelle berechnet.
Im anderen Fall (wenn kein Wert drinsteht), wird er berechnet und da gespeichert. Das heißt, du musst deine Bedingung nur auf == 0 ändern (bzw. die kann komplett raus, weil das ja die einzig mögliche Konstellation ist)

 

[districon]

if (v == g) {
            return 1;
        } else if (v == 1){
            return 1;
        } if (memo[v][g] != 0){
            memo[v][g] = (Wuerzmischungen(v-1,g,memo))+(v*Wuerzmischungen(v,g-1,memo));
            return memo[v][g];
        }
       return memo [v][g];

So vielleicht?

 

[districon]

if (v == g) {
            return 1;
        } else if (v == 1){
            return 1;
        } else if(memo[v][g] != 0) {
            return memo[v][g];
        }
        else {
            memo[v][g] = (Wuerzmischungen(v-1,g,memo))+(v*Wuerzmischungen(v,g-1,memo));
            return memo[v][g];
        }

Bzw. so hab ichs jetzt. Aber da kommen immer noch Fehler

 

[LimDul]

Definiere Fehler?

 

[districon]

1. Meine Laufzeit ist noch zu lang.
2. Und wenn ich jetzt v=3 und g=4 überprüfe kommt was anderes raus. Da kommt bei mir 26 raus, aber eig sollte es 18 sein

 

[LimDul]

            memo[v][g] = (Wuerzmischungen(v-1,g,memo))+(v*Wuerzmischungen(v,g-1,memo));

Vergleich mal den linken Aufruf mit der Aufgabenstellung, da muss v-1, g-1 sehen nicht v-1,g

 

[districon]

Jetzt passt alles. Und ich hab schon die ganze Zeit im Code rumgesucht

 

[mrBrown]

Zwar nicht die Frage, aber ich würde unter Memoization beI der Aufgabe was anderes verstehen.
Schwierig, das hier abzugrenzen, aber diese würde ich eher als dynamische Programmierung sehen, anstatt als Memoisation.