Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
public class VeggieFad {
public static long meals (int s, int v) {
table = new long[s + 1][];
for (int i = 0; i < table.length; i++) {
table[i] = new long[i + 1];
}
return 2 * ((mealsMem(s,v,table)) + v);
}
Diese Methode scheitert an folgendem Test, der 1000 Millisekunden Laufzeit hat:
Code:
public void(){
for (int i = 0; i <= 1000; i++) {
test_n_and_special(4);
}
}
Es wird gesagt, dass das Array global initialisiert werden soll, um die Laufzeit zu verkürzen. Ich weiß aber nicht wie man in Java Arrays global initialisiert.
Kann mir jemand dabei helfen, die Methode weniger als 1 Sekunde laufen zu lassen?
Wie sollen wir Dir helfen, wenn wir kaum etwas von dem Code kennen? In dem Test wird test_n_and_special aufgerufen, die wir nicht kennen.
Die meals Methode sehen wir, aber keine Ahnung, was die macht, denn mealsMem kennen wir auch nicht.
Und ohne Details können wir nicht wissen, was da optimierbar ist. Wenn da 1000 mal immer die gleiche Tabelle tabelle aufgebaut wird und die da keine weitere Initialisierung sein muss, dann könnte man das einmalig machen. Aber ohne die Details zu kennen, ist es unsinnig.
Das wäre dann wie: Ich gebe Dir immer wieder das gleiche Auto. Also Du kommst jeden Tag morgens zu mir und willst ein Auto. Das kann ich dann immer groß vorbereiten: Das kostet aber Zeit. Die Zeit kann ich einsparen, in dem ich Dir immer das gleiche Auto gebe (das ist einmalig vorbereite).
Wenn Du das Auto aber veränderst (drickig machst, Tank leer, irgend welche Schäden), dann ist das nicht neu aufbereiten kritisch und das Ergebnis ist dann natürlich verändert (Ich bezweifle, dass Du mit einem Auto, das nach einem Crash Totalschaden hat, von München nach Hamburg fahren kannst).
Wie sollen wir Dir helfen, wenn wir kaum etwas von dem Code kennen? In dem Test wird test_n_and_special aufgerufen, die wir nicht kennen.
Die meals Methode sehen wir, aber keine Ahnung, was die macht, denn mealsMem kennen wir auch nicht.
Und ohne Details können wir nicht wissen, was da optimierbar ist. Wenn da 1000 mal immer die gleiche Tabelle tabelle aufgebaut wird und die da keine weitere Initialisierung sein muss, dann könnte man das einmalig machen. Aber ohne die Details zu kennen, ist es unsinnig.
Das wäre dann wie: Ich gebe Dir immer wieder das gleiche Auto. Also Du kommst jeden Tag morgens zu mir und willst ein Auto. Das kann ich dann immer groß vorbereiten: Das kostet aber Zeit. Die Zeit kann ich einsparen, in dem ich Dir immer das gleiche Auto gebe (das ist einmalig vorbereite).
Wenn Du das Auto aber veränderst (drickig machst, Tank leer, irgend welche Schäden), dann ist das nicht neu aufbereiten kritisch und das Ergebnis ist dann natürlich verändert (Ich bezweifle, dass Du mit einem Auto, das nach einem Crash Totalschaden hat, von München nach Hamburg fahren kannst).
public class VeggieFad {
static long [][] table;
public static long meals (int s, int v) {
table = new long[s + 1][]; // table for memoization
for (int i = 0; i < table.length; i++) {
table[i] = new long[i + 1]; //
}
return 2 * ((mealsMem(s,v,table)) + v);
}
private static long mealsMem(int s, int v, long [][] table){
if(table[s][v] != 0){ // Lookup
return table[s][v];
}
long result = 0;
if ( s == v || v == 1 ) {
result = 1;
} else {
result += mealsMem (s -1 , v -1 , table ) + v * ( mealsMem (s -1 , v , table ));
}
table[s][v] = result; // memoization
return result;
}
}
public class VeggieFad {
static long [][] table;
public static long meals (int s, int v) {
table = new long[s + 1][]; // table for memoization
for (int i = 0; i < table.length; i++) {
table[i] = new long[i + 1]; //
}
return 2 * ((mealsMem(s,v,table)) + v);
}
private static long mealsMem(int s, int v, long [][] table){ // Helper_Methode
if(table[s][v] != 0){ // Lookup
return table[s][v];
}
long result = 0;
if ( s == v || v == 1 ) {
result = 1;
} else {
result += mealsMem (s -1 , v -1 , table ) + v * ( mealsMem (s -1 , v , table ));
}
table[s][v] = result; // memoization
return result;
}
}
Es werden mindestens so viele Gewürze s angeschafft, wie es vegane Grundgerichte v gibt, aus Kostengründen aber maximal 256 verschiedene Gewürze (1 ≤ v ≤ s ≤ 256).
• 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 Methode soll bestimmen wie viele unterschiedliche Gewürzmischungen B_s,v auf diesem Wege überhaupt möglich sind und schließlich wie viele verschiedene Essen M_s,v im Speiseplan stehen werden:
• Bei gleich vielen veganen Gerichten wie Gewürzen (s = v) gibt es eine Würzung B_s,s = 1: Jedes vegane Gericht bekommt genau eines der Gewürze.
• Bei nur einem veganen Gericht (v = 1) gibt es auch genau eine Würzmöglichkeit B_s,1 = 1: Alle Gewürze werden in das eine Gericht zusammengekippt.
• Andernfalls gibt es weitere Kochtricks: Man nehme das erstbeste Gewürz S zur Hand und . . .
– entweder gibt es ein Gericht, das nur mit diesem einen Gewürz S abgeschmeckt wird, dann verteilen sich die restlichen s − 1 Gewürze auf die anderen v − 1 Gerichte; – oder das Gewürz S kommt zusammen mit anderen Gewürzen in das gleiche Gericht, dann werden zuerst die anderen s − 1 Gewürze auf alle v Gerichte verteilt (ergibt Bs−1,v Würzmischungen) und anschließend wird das aktuelle Gewürz S zu einem beliebigen der v Gerichte hinzugefügt (wofür es v Möglichkeiten gibt). ; Das macht dann insgesamt Bs,v = Bs−1,v−1 + v · Bs−1,v vegane Würzmischungen.
• Die v veganen Grundgerichte und die Bs,v Würzmischungen werden schließlich sowohl mit als auch ohne Hackfleisch zu Ms,v = 2 ·(Bs,v +v) unterschiedliche Essen zusammengerührt.
Generell ist das aber eine rekursive Berechnung mit zwei Parametern, wobei die Tabelle genutzt wird, um sich einzelne Ergebnisse zu merken.
Jetzt solltest Du Dir überlegen: Wie unterscheiden sich die Tabellen in Abhängigkeit von s und v?
s ist offensichtlich: Die Tabelle sieht anders aus, wenn s unterschiedlich ist. Alleine schon von der Größe her.
Aber wie sieht es mit v aus? Ändern sich Werte in der Tabelle, wenn s gleich bleibt und sich v verändert? Die Frage musst Du Dir Überlegen.
Die Initialisierung von tabelle
Java:
table = new long[s + 1][];
for (int i = 0; i < table.length; i++) {
table[i] = new long[i + 1];
}
machst Du nur dann, wenn es notwendig ist. Notwendig ist es:
wenn es noch nie initialisiert wurde. (Woran kannst Du das erkennen? Schau Dir einmal die Variable table an.)
Wenn die Tabelle bereits Werte einer vorherigen Berechnung enthält, die aber für unsere Berechnung ungültig wären. (Das musst Du Dir noch überlegen, wann dies der Fall wäre!)
Generell ist das aber eine rekursive Berechnung mit zwei Parametern, wobei die Tabelle genutzt wird, um sich einzelne Ergebnisse zu merken.
Jetzt solltest Du Dir überlegen: Wie unterscheiden sich die Tabellen in Abhängigkeit von s und v?
s ist offensichtlich: Die Tabelle sieht anders aus, wenn s unterschiedlich ist. Alleine schon von der Größe her.
Aber wie sieht es mit v aus? Ändern sich Werte in der Tabelle, wenn s gleich bleibt und sich v verändert? Die Frage musst Du Dir Überlegen.
Die Initialisierung von tabelle
Java:
table = new long[s + 1][];
for (int i = 0; i < table.length; i++) {
table[i] = new long[i + 1];
}
machst Du nur dann, wenn es notwendig ist. Notwendig ist es:
wenn es noch nie initialisiert wurde. (Woran kannst Du das erkennen? Schau Dir einmal die Variable table an.)
Wenn die Tabelle bereits Werte einer vorherigen Berechnung enthält, die aber für unsere Berechnung ungültig wären. (Das musst Du Dir noch überlegen, wann dies der Fall wäre!)
