Welcher Algorithmus würde die maximale Auswahl aus zwei Sätzen berechnen?

11

Wie kann ich bei zwei Vektoren von ganzen Zahlen mit möglicherweise ungleichen Längen das maximal mögliche Ergebnis aus der Akkumulation bestimmen, indem ich das Maximum zwischen entsprechenden Zahlenpaaren zwischen den beiden Vektoren mit zusätzlichen Nullen auswähle, die in den kürzeren Vektor eingefügt werden, um den Größenunterschied auszugleichen?

Betrachten Sie beispielsweise die folgenden zwei Vektoren als Eingaben:

[8 1 4 5]
[7 3 6]

Die Auswahlmöglichkeiten zum Einfügen der Null und der resultierenden Summe sind:

[0 7 3 6]  => Maximums: [8 7 4 6]  =>  Sum is: 25
[7 0 3 6]  => Maximums: [8 1 4 6]  =>  Sum is: 19
[7 3 0 6]  => Maximums: [8 3 4 6]  =>  Sum is: 21
[7 3 6 0]  => Maximums: [8 3 6 5]  =>  Sum is: 22

Daher sollte der Algorithmus in diesem Fall 25 zurückgeben.

Ich könnte dies durch rohe Gewalt tun, indem ich für alle Permutationen der Platzierung von Nullen in den kleineren Vektor berechne (wie oben ausgeführt), aber dies wäre rechenintensiv und am schlimmsten, wenn ein Vektor genau halb so groß wie der andere ist.

Gibt es eine Möglichkeit, die Antwort in linearer Zeit proportional zur Länge des längeren Vektors zu berechnen, selbst wenn sich die Vektoren in der Länge unterscheiden? Wenn nicht, können wir es besser machen als die Anzahl der gewählten faktoriellen Permutationen?

WilliamKF
quelle
3
0
2
Ich verwende dies, um das maximale Ergebnis eines anderen Suchalgorithmus zu berechnen, der sich auf die Rangfolge bezieht, wie ähnlich zwei Sätze zueinander sind. Richtig, eine Nachbestellung ist nicht akzeptabel.
WilliamKF
Wird uns etwas über den Unterschied zwischen den Längen der Vektoren versprochen? In Ihrem Beispiel fehlt nur eine Null. Wenn Sie wissen, dass die Anzahl der fehlenden Nullen gering ist, gibt es effizientere Algorithmen (z. B. kann der dynamische Programmieralgorithmus in linearer Zeit ausgeführt werden, wenn die Anzahl der fehlenden Nullen eine Konstante ist).
DW

Antworten:

6

z,lzl

Yuval Filmus
quelle
1
Dieser Algorithmus läuft in quadratischer Zeit, es könnte bessere geben.
Yuval Filmus