Hallo Leute, ich brauche eure Hilfe bei folgender Aufgabe. Die Aufgabe bestand darin, zu beweisen:
Angenommen, man nimmt an einem Tanzwettbewerb teil, bei dem man zu jedem Song \( k \) Punkte \( P[k] \) erhält, aber zwischen den Songs braucht man eine Pause von \( W[k] \) Songs. Man muss entscheiden, zu welchen Songs man tanzen sollte, um die Gesamtpunktzahl zu maximieren, dabei die Wartezeiten berücksichtigend.
Dazu habe ich einen Algorithmus geschrieben, der das Problem lösen soll:
`python
1. C[n+1] = 0; // Basisfall: Es gibt nach dem letzten Song keine weiteren Punkte
2. for (j = n; j >= 1; j--) do // Gehe rückwärts durch die Songs
3. if (j + W[j] + 1 > n) then
4. C[j] = max{C[j+1], P[j]} // Wenn keine weiteren Songs nach j folgen, dann tanze zu Song j oder überspringe ihn
5. else
6. C[j] = max{C[j+1], P[j] + C[j + W[j] + 1]} // Wenn es weitere Songs nach j gibt, dann tanze zu j oder überspringe ihn
7. return C[1]; // Gib die optimale Punktzahl zurück, beginnend ab Song 1
`
Ich muss jetzt die Korrektheit des Algorithmus beweisen. Dazu verwende ich folgenden Invariante: Nach jeder Iteration enthält \( C[j] \) die optimale Punktzahl, die ab Song \( j \) erzielt werden kann, wenn die restlichen Songs optimal ausgewählt werden.
Induktionsanfang:
Im Basisfall setzen wir \( i = n + 1 \). Zu diesem Zeitpunkt gibt es keine weiteren Songs, daher ist \( C[n+1] = 0 \), was korrekt ist, da ab Song \( n+1 \) keine Punktzahl mehr erreichbar ist. Die Invariante gilt hier, da es keine weiteren Songs gibt und somit auch keine Punktzahl zu erzielen ist.
Induktionsannahme:
Angenommen, die Invariante gilt für ein beliebiges \( j \), das heißt, \( C[j] \) enthält die optimale Punktzahl, die ab Song \( j \) erzielt werden kann, wenn die restlichen Songs optimal ausgewählt werden.
Induktionsschritt:
Ich tue mir leider hier schwer, ein geeignetes \( j \) zu finden. Ich bin mir nicht sicher, ob ich \( n \to n-1 \) machen soll oder doch \( n+1 \to n \). Ich weiß leider nicht genau, welchen geeigneten Wert für \( n \) ich nehmen soll, um das zu zeigen.
