Hallo zusammen,
Ich muss die folgende Aufgabe lösen, und zwar mit einer dynamischen Programmierung, wie es in der Aufgabe steht. Nur habe ich leider noch keinerlei Ansatzpunkte.
"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:
• 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.
ergänzen Sie die Methode essen so, dass sie die oben beschriebene Anzahl Ev,g ermittelt. Verwenden Sie zur Implementierung unbedingt dynamische Programmierung mittels Memoization. Sie dürfen davon ausgehen, dass das Ergebnis Ihrer Rechnung in einen long passt. "
Ich muss die folgende Aufgabe lösen, und zwar mit einer dynamischen Programmierung, wie es in der Aufgabe steht. Nur habe ich leider noch keinerlei Ansatzpunkte.
"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).
- – 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;
- 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.
• 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.
ergänzen Sie die Methode essen so, dass sie die oben beschriebene Anzahl Ev,g ermittelt. Verwenden Sie zur Implementierung unbedingt dynamische Programmierung mittels Memoization. Sie dürfen davon ausgehen, dass das Ergebnis Ihrer Rechnung in einen long passt. "
Code:
public class VeggieWahn {
public static long essen(int v, int g) {
return -1;
}
}
