Optimierung der Gesamtsumme der gewichteten Intervalle

Question

Ich habe M Intervalle auf der realen Linie, jeweils mit einem positiven Gewicht. Ich muss N unter ihnen so auswählen, dass sie sich nicht überschneiden und die maximale Summe geben. Wie kann ich das effizient machen?

Wenn es keine Teilmenge von N nicht überlappenden Intervallen gibt, gibt es keine Lösung.

Ohne die Non-Overlap-Einschränkung ist die Frage trivial: Wählen Sie die N größten Gewichte. Aufgrund der Einschränkung funktioniert dies nicht mehr. In meinem Fall sind N und M klein (< 20), aber ich hoffe, dass es eine effizientere Lösung gibt, als alle Teilmengen erschöpfend auszuprobieren.

Answer 1

Sie können es mit dynamischer Programmierung lösen. Sei C(k, i) die maximale Summe von (bis zu) k gewichteten Intervallen, von denen keines ihr linkes Ende weniger als i hat.

Sie können i beschränken 0-N in dem Satz von (real) Startpunkte für alle Intervalle und k Bereiche liegen.

• Starten von C(k, max(start for start, end in interval))-0 und alle anderen Einträge zu -unendlich initialisiert.
• Sortieren Sie die Intervalle nach Startpunkten und durchlaufen Sie sie rückwärts.

• Für jedes Intervall (start, end) mit Gewicht w und für jeden k:

  C(start, k) = max(C(start, k), C(next(start), k), w + C(next'(end), k-1))

Hier next(x) gibt den kleinsten Startpunkt größer ist als x, und next'(x) gibt den kleinsten Start Punkt größer oder gleich x. Beide können durch binäre Suche implementiert werden (oder linearer Scan, wenn M klein ist).

Insgesamt wird dies O (M * N * logM) Zeit und O (M * N) Platz benötigen.

(Dies setzt voraus, dass die Intervalle nicht an beiden Enden geschlossen sind, also (0, 100) und (100, 200) nicht überlappen - eine kleine Anpassung muss vorgenommen werden, wenn diese als überlappend betrachtet werden) .

Answer 2

In Bearbeitung:

Inspiriert von @ PaulHankin-Lösung, hier ist eine Neuformulierung.

Alle Intervalle sortieren, indem die rechte Abszisse erhöht wird, und iterativ die größtmögliche Summe bis zur K-ten rechten Schranke finden. Angenommen, Sie haben alle Optimierungsprobleme für die ersten K-Intervalle und für alle relevanten N (von 0 bis K) gelöst.

Wenn Sie das nächste Intervall berücksichtigen, berechnen Sie neue Kandidatenlösungen wie folgt: für jedes N (bis zum aktuellen nomber der Intervalle), verlängern Sie alle bisherigen Lösungen (einschließlich der leeren) ohne Überlappung zu verursachen und halten Sie die verlängerten Lösungen, die besser sind.

Beispiel:

Die optimalen Summen bis zum K-ten Recht gebunden ist, durch N zu erhöhen sind

1: 2 
2: 2 or 8 => 8 | - 
3: 8 or 3 => 8 | 2 + 3     | - 
4: 8 or 2 => 8 | 2 + 3 or 8 + 2 => 8 + 2 | 2 + 3 + 2 | - 
5: 8 or 9 => 9 | 8 + 2 or 2 + 9 => 2 + 9 | 2 + 3 + 2 | - | -