Ich bin auf diese Frage gestoßen. Bei einem Array, das nur positive Werte enthält, möchten Sie die Summe der ausgewählten Elemente unter der Einschränkung maximieren, dass keine Gruppe von mehr als k ausgewählten Elementen benachbart ist. Zum Beispiel, wenn der Eingang 1 2 3 1 7 9 ist (n = 6 und k = 2). Die Ausgabe wird 21 sein, das kommt von der Auswahl der Elemente _ 2 3 _ 7 9. Meine einfache DP-Lösung ist das
%Vor%Aber ich bin mir nicht sicher, ob dies die effiziente Lösung ist. Kann die Komplexität weiter reduziert werden? Danke für deine Hilfe
Ihr Code ist richtig (zumindest der Gedanke ist richtig), auch Bisher habe ich keine falschen Testdaten gefunden. Folge deinem Gedanken, wir können die DP-Gleichung auflisten
P(v)=max{sum(C[v]~C[v+i-1])+P(v+i+1),0<=i<=k}
In dieser Gleichung bedeutet P (v) das Maximum in {C [v] ~ C [n]} (wir lassen {C [1] ~ C [n]} die ganze Liste sein), also brauchen wir nur um P (1) zu bestimmen.
Ich habe bis jetzt keine bessere Lösung gefunden, aber Ihr Code kann optimiert werden, nachdem Sie P (v) festgelegt haben, können Sie die Daten i speichern. Wenn Sie P (v-1) finden, können Sie einfach vergleiche die Summe (C [v-1] + C [v] ~ C [v + i-1]) + P [v + i + 1] mit P [v + 1] + C [v], wenn i! = k , die schlimmste Komplexität ist die gleiche, aber die beste Komplexität ist linear.
Tags und Links algorithm c dynamic-programming