¿Qué algoritmo calcularía las elecciones máximas de dos conjuntos?

11

Dados dos vectores de enteros de longitudes posiblemente desiguales, ¿cómo puedo determinar el resultado máximo posible al acumular la elección del máximo entre los pares de números correspondientes entre los dos vectores con ceros adicionales insertados en el vector más corto para compensar la diferencia de tamaño?

Por ejemplo, considere los siguientes dos vectores como entradas:

[8 1 4 5]
[7 3 6]

Las opciones para insertar el cero y la suma resultante son:

[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

Por lo tanto, en este caso, el algoritmo debería devolver 25.

Podría hacerlo mediante la fuerza bruta calculando todas las permutaciones de colocar ceros en el vector más pequeño (como se acaba de hacer anteriormente), pero esto sería computacionalmente costoso, y lo peor en el caso cuando un vector es exactamente la mitad del tamaño del otro.

¿Hay alguna manera de calcular la respuesta en tiempo lineal proporcional a la longitud del vector más largo, incluso cuando los vectores difieren en longitud? Si no, ¿podemos hacerlo mejor que el número de permutaciones factoriales que se eligen?

WilliamKF
fuente
3
Buen problema, ¿cómo se te ocurrió? ¿Tiene algún escenario realista donde agregar s en posiciones arbitrarias está bien, pero reordenar el segundo vector no lo está? 0
frafl
2
Estoy usando esto para calcular el resultado máximo de otro algoritmo de búsqueda relacionado con la clasificación de cuán similares son dos oraciones entre sí. Correcto, el reordenamiento no es aceptable.
WilliamKF
¿Se nos promete algo sobre la diferencia entre las longitudes de los vectores? En su ejemplo, solo falta un cero. Si sabe que el número de ceros faltantes es pequeño, existen algoritmos más eficientes (por ejemplo, el algoritmo de programación dinámica puede ejecutarse en tiempo lineal, si el número de ceros faltantes es una constante).
DW

Respuestas:

6

Sugerencia: use programación dinámica. Para cada , calcule la forma óptima de insertar ceros al prefijo de longitud de la matriz más pequeña.z,lzl

Yuval Filmus
fuente
1
Este algoritmo se ejecuta en tiempo cuadrático, puede haber mejores.
Yuval Filmus