Mayor suma divisible por n

16

Hice esta pregunta en StackOverflow , pero creo que este es un lugar más apropiado.

Este es un problema del curso de Introducción al algoritmo :

Tiene una matriz con enteros positivos (la matriz no necesita ser ordenada o los elementos únicos). Sugiera un algoritmo para encontrar la mayor suma de elementos que sea divisible por .n O ( n ) nanO(n)n

Ejemplo: . La respuesta es (con los elementos 6, 13, 4, 8, 25 )56 6 , 13 , 4 , 8 , 25a=[6,1,13,4,9,8,25],n=7566,13,4,8,25

Es relativamente fácil encontrarlo en O(n2) usando programación dinámica y almacenando la suma más grande con el resto 0,1,2,...,n1 .

Además, si restringimos la atención a una secuencia contigua de elementos, es fácil encontrar la secuencia óptima en el tiempo O(n) , almacenando sumas parciales módulo n : sea S[i]=a[0]+a[1]++a[i] , para cada resto r recuerde el índice más grande j tal que S[j]r(modn) , y luego para cada i considere S[j]S[i] donde j es el índice correspondiente a r=S[i]modn .

Pero, ¿hay una solución de tiempo O(n) para el caso general? ¡Cualquier sugerencia será apreciada! Considero que esto tiene algo que ver con el álgebra lineal, pero no estoy seguro de qué es exactamente.

Alternativamente, ¿se puede hacer esto en tiempo O(nlogn) ?

delta-terminador
fuente
2
1. Has publicado exactamente la misma pregunta en Stack Overflow. Por favor, no publicar la misma pregunta en varios sitios . No queremos múltiples copias flotando en múltiples sitios SE. Si no obtuvo una respuesta aceptable, está bien marcar su pregunta para la migración a otro sitio, pero no vuelva a publicar lo mismo en otro lugar. 2. ¿Puedes dar una referencia / cita / enlace al libro de texto o curso donde apareció? ¿Qué tan seguro está de que existe una solución de tiempo ? O(n)
DW
55
¿El desafío en tu universidad aún está abierto? Sería realmente útil ver el enlace al curso, la pregunta exacta y si realmente es y las personas que lo prepararon explicarán / publicarán su respuesta, sería increíble. O(n)
Evil
Es relativamente fácil encontrarlo en O (n2) O (n2) usando programación dinámica y almacenando la suma más grande con el resto 0,1,2, ..., n − 10,1,2, ..., n − 1. ¿Podría por favor elaborar esto un poco? Puedo entender cómo esto sería n cuadrado si solo consideramos elementos contiguos, pero también con elementos no contiguos, ¿no sería exponencial en orden?
Nithish Inpursuit Ofhappiness

Respuestas:

4

Aquí hay algunas ideas al azar:

  • El algoritmo de programación dinámica se puede voltear para buscar una suma más pequeña en lugar de una suma más grande. Simplemente termina buscando una suma congruente con el resto de la suma de toda la matriz, en lugar de una congruente con cero. Si procesamos los elementos en orden creciente, esto a veces permite que el algoritmo dinámico termine antes de procesar toda la matriz.

    El costo sería si procesáramos elementos. Hay no un límite inferior de en este algoritmo, ya que no tenemos que ordenar todos los elementos. Solo toma tiempo obtener los elementos más pequeños.O(nk)kΩ(nlogn)O(nlogk)k

  • Si nos preocupamos por el conjunto con el tamaño más grande, en lugar del conjunto con la suma más grande, podríamos ser capaces de utilizar la multiplicación polinómica basada en la transformación de Fourier rápida para resolver el problema en tiempo. Similar a lo que se hace en 3SUM cuando el rango de dominio es limitado. (Nota: use el cuadrado repetido para hacer una búsqueda binaria, de lo contrario obtendrá donde es el número de elementos omitidos).O(n(logn)2(loglogn))O(nk(logn)(loglogn))k

  • Cuando es compuesto, y casi todos los restos son múltiplos de uno de los factores de , se puede ahorrar un tiempo significativo al centrarse en los restos que no son múltiplos de ese factor.nn

  • Cuando un resto res muy común, o solo hay unos pocos restos presentes, realizar un seguimiento de la 'próxima ranura abierta si comienza desde aquí y sigue avanzando por r' la información puede ahorrar una gran cantidad de escaneos en busca de saltos en espacios abiertos hora.

  • Puede reducir un factor de registro solo rastreando el alcance y utilizando máscaras de bits (en el algoritmo dinámico invertido), luego retroceda una vez que alcance el resto del objetivo.

  • El algoritmo de programación dinámica es muy susceptible de ejecutarse en paralelo. Con un procesador para cada ranura de búfer, puede bajar a . Alternativamente, al usar la amplitud y dividir y conquistar la agregación en lugar de la agregación iterativa, el costo de profundidad del circuito puede llegar hasta .O(n)O(n2)O(log2n)

  • (Meta) Sospecho firmemente que el problema que le dieron es sobre sumas contiguas . Si se vinculó con el problema real, sería fácil verificarlo. De lo contrario, estoy muy sorprendido por lo difícil que es este problema, dado que fue asignado en un curso llamado "Introducción a los algoritmos". Pero tal vez cubriste un truco en clase que lo hace trivial.

Craig Gidney
fuente
Para el punto uno. No está escrito en las especificaciones del problema, por lo que no puede suponer eso. Además, el problema no es decir que no puede modificar la matriz o crear otras nuevas, de hecho sí puede. Lo único que debe hacer es encontrar los números que sumados juntos le dan la suma más grande que es divisible por en O ( n ) complejidad de tiempo (generalmente se supone solo la complejidad de tiempo). nO(n)
nbro
2
@EvilJS El subconjunto con la suma más grande con el resto 0 es igual al conjunto completo después de eliminar el subconjunto con la suma más pequeña con el resto congruente con la suma del conjunto completo. Buscar una suma congruente más pequeña a es más conveniente que buscar una suma más grande congruente a r 2 porque le permite terminar tan pronto como encuentre una solución (al procesar elementos en orden creciente) en lugar de tener que continuar. r1r2
Craig Gidney
-1

Mi algoritmo propuesto es el siguiente:

Una suma es divisible por n si solo agrega sumandos que son múltiplos de n.

Antes de comenzar, cree un hashmap con un int como clave y una lista de índices como valor. También crea una lista de resultados que contiene índices.

Luego, recorre la matriz y agrega cada índice cuyo mod n es cero a su lista de resultados. Para cualquier otro índice, haga lo siguiente:

Resta el valor mod n de este índice de n. Este resultado es la clave para su hashmap que almacena índices para elementos con el valor requerido. Ahora, agrega este índice a la lista en el hashmap y continúa.

Después de que termine de recorrer la matriz, calcula la salida. Para ello, ordena cada lista en el mapa hash de acuerdo con el valor al que apunta el índice. Ahora considera que cada par en el hashmap suma n. Entonces, si n = 7, busca en el hashmap 3 y 4. Si obtiene una entrada en ambos, toma los dos valores más grandes, los elimina de sus listas y los agrega a su lista de resultados.

Última recomendación: todavía no probé el algoritmo, escribí un caso de prueba contra él usando un algoritmo de fuerza bruta.

Tobias Würfl
fuente
2
Codicioso, lineal, no funciona. Considera solo elementos que son divisibles por n y pares divisibles por n, ¿qué pasa con triples y más? No garantiza la suma máxima del subconjunto en caso trivial. [2, 1, 8] -> la suma máxima es 9, pero su algoritmo devuelve 3.
Mal
n2
Gracias por señalarme este error. Mi idea sobre la mejora sería hacer un hashmap de pilas de listas que se ordena aumentando el valor y comenzar a acumular solo después de completar un pase a través de la matriz.
Tobias Würfl
¿Te refieres a una matriz de matrices, que se ordenarán, y "hashmap" es% n? Todavía necesita ordenarlos, y si los tiene ordenados, tomar el valor mínimo / máximo está bien, pero aún así es inevitable parte de la elección real del subconjunto, que en el peor de los casos no se beneficia. De todos modos, si tienes algunas mejoras, ¿podrías editar la publicación?
Evil
Sí, fue una idea bastante rápida con las pilas. De hecho, solo necesita listas en el hashmap que ordena. No estaba seguro de si es cortés editar mi primera respuesta. Después de todo, cometí un error en mi primer intento.
Tobias Würfl
-2

use este método DP de ( /programming/4487438/maximum-sum-of-non-conse cu- ratement-elements?rq =1 ):

Dada una matriz A [0..n], deje que M (i) sea la solución óptima utilizando los elementos con índices 0..i. Entonces M (-1) = 0 (usado en la recurrencia), M (0) = A [0] y M (i) = max (M (i - 1), M (i - 2) + A [i ]) para i = 1, ..., n. M (n) es la solución que queremos. Esto es O (n) . Puede usar otra matriz para almacenar qué opción se hace para cada subproblema, y ​​así recuperar los elementos reales elegidos.

Cambie la recursión a M (i) = max (M (i - 1), M (i - 2) + A [i]) de modo que se almacene solo si es divisible por N

Cabeza de alfiler
fuente
2
Esto no funciona. Te dejaré descubrir por qué. (Sugerencia: intente ejecutarlo en la matriz constante 1). Además, en este problema permitimos elementos consecutivos.
Yuval Filmus
1
Esta es una muy buena solución, solo para un problema totalmente diferente (y mucho más fácil).
Evil