Ansatz dynamische Programmierung

Erste Frage Aufrufe: 1241     Aktiv: 25.05.2020 um 08:11

0

Hi, ich habe folgende Aufgabe:

enter image description here enter image description here

Wie kann ich einen ersten rekursiven Ansatz für dieses Problem finden und wie kann ich dies am Ende in Pseudocode umsetzen?

Diese Frage melden
gefragt

Punkte: 10

 
Kommentar schreiben
1 Antwort
0

Hi missiondepay,

der Ansatz sähe wohl folgendermaßen aus:

An Tag i: Manni kann nicht arbeiten, wenn er eine Pause braucht bzw. er kann arbeiten, wenn er noch keine braucht. Wenn er arbeiten kann, muss geprüft werden, ob es rentabler wäre zu arbeiten oder eine Pause zu machen (um dann an anderen Tagen arbeiten zu können)

Der Pseudocode:

solve(A, i, streak) {
  if (i >= A.length) return 0;
  // Pause an Tag i
  res1 = solve(A, i++, 0);
  if (streak >= 2) return res1;
  else {
    ai = A[i];
    // Zusätzliche Autos ai an Tag i verkauft
    res2 = ai + solve(A, i++, streak++); 
    return max(res1, res2);
  }
}

Hier müsstest du dann gegebenenfalls noch dynamische Programmierung einbauen.

Diese Antwort melden
geantwortet

Student, Punkte: 10

 

Kommentar schreiben