algorithm - sustraccion - Obtener la suma más baja posible de la diferencia de números

sustraccion de numeros naturales y sus propiedades (10)

Tengo que encontrar la suma más baja posible de la diferencia de los números.

Digamos que tengo 4 números. 1515, 1520, 1500 y 1535. La suma de diferencia más baja es 30, porque 1535 - 1520 = 15 && 1515 - 1500 = 15 y 15 + 15 = 30. Si hiciera esto: 1520 - 1515 = 5 && 1535 - 1500 = 35 sería 40 en suma.

Espero que lo tengas, si no, pregúntame.

¿Alguna idea de cómo programar esto? Acabo de encontrar esto en línea, intenté traducir de mi idioma al inglés. Suena interesante. No puedo hacer fuerza bruta, porque llevaría mucho tiempo compilar. No necesito código, solo ideas de cómo programar o poco fragmento de código.

Gracias.

Edición: No publiqué todo ... Una edición más:

Tengo digamos 8 números posibles. Pero tengo que tomar solo 6 de ellos para hacer la suma más pequeña. Por ejemplo, los números 1731, 1572, 2041, 1561, 1682, 1572, 1609, 1731 , la suma más pequeña será 48, pero aquí tengo que tomar solo 6 números de 8.

Algo como

Lista Ordenada
Encontrar duplicados
Haz los duplicados un par
eliminar duplicados de la lista
romper el resto de la lista en parejas
calcular las diferencias de cada par
tomar las cantidades más bajas

En tu ejemplo tienes 8 números y necesitas los 3 mejores pares. Primero ordena la lista que te da

1561, 1572, 1572, 1609, 1682, 1731, 1731, 2041

Si tiene duplicados, forme un par y elimínelos de la lista para que tenga

[1572, 1572] = 0 [1731, 1731] = 0 L = { 1561, 1609, 1682, 2041 }

Divide la lista restante en pares, dándote los 4 pares siguientes

[1572, 1572] = 0 [1731, 1731] = 0 [1561, 1609] = 48 [1682, 2041] = 359

Luego suelta la cantidad de números que necesitas.

Esto te da los siguientes 3 pares con los pares más bajos

[1572, 1572] = 0 [1731, 1731] = 0 [1561, 1609] = 48

Asi que

0 + 0 + 48 = 48

Creo que el enfoque de @marcog puede simplificarse aún más.

Adopte el enfoque básico que demostró @ jonas-kolker para encontrar las diferencias más pequeñas. Toma la lista resultante y ordénala. Tome las R entradas más pequeñas de esta lista y úselas como sus diferencias. Probar que esta es la suma más pequeña es trivial.

El enfoque de @ marcog es efectivamente O (N ^ 2) porque R == N es una opción legítima. Este enfoque debe ser (2 * (N log N)) + N aka O (N log N).

Esto requiere una pequeña estructura de datos para mantener una diferencia y los valores de los que se derivó. Pero, eso es constante por entrada. Por lo tanto, el espacio es O (N).

He tomado un enfoque que utiliza un algoritmo recursivo, pero toma algo de lo que otras personas han contribuido.

En primer lugar ordenamos los números:

[1561,1572,1572,1609,1682,1731,1731,2041]

Luego, calculamos las diferencias y hacemos un seguimiento de los índices de los números que contribuyeron a cada diferencia:

[(11,(0,1)),(0,(1,2)),(37,(2,3)),(73,(3,4)),(49,(4,5)),(0,(5,6)),(310,(6,7))]

Entonces obtuvimos 11 al obtener la diferencia entre el número en el índice 0 y el número en el índice 1, 37 de los números en los índices 2 y 3.

Luego ordené esta lista, así que me dice qué pares me dan la menor diferencia:

[(0,(1,2)),(0,(5,6)),(11,(0,1)),(37,(2,3)),(49,(4,5)),(73,(3,4)),(310,(6,7))]

Lo que podemos ver aquí es que, dado que queremos seleccionar n números, una solución ingenua podría ser seleccionar los primeros n / 2 elementos de esta lista. El problema es que, en esta lista, el tercer elemento comparte un índice con el primero, por lo que solo obtendríamos 5 números, no 6. En este caso, también debe seleccionar el cuarto par para obtener un conjunto de 6 números.

A partir de aquí, se me ocurrió este algoritmo. A lo largo, hay un conjunto de índices aceptados que comienzan vacíos, y hay una cantidad de números que quedan para seleccionar n :

Si n es 0, hemos terminado.
si n es 1, y el primer elemento proporcionará solo 1 índice que no está en nuestro conjunto, tomamos el primer elemento y hemos terminado.
si n es 2 o más, y el primer elemento proporcionará 2 índices que no están en nuestro conjunto, tomamos el primer elemento y respondemos (por ejemplo, goto 1). Esta vez, busque n - 2 números que hagan la menor diferencia en el resto de la lista.

Esta es la rutina básica, pero la vida no es tan simple. Hay casos que aún no hemos cubierto, pero asegúrese de tener la idea antes de continuar.

En realidad, el paso 3 es incorrecto (se encontró que justo antes de publicar esto: - /), ya que puede ser innecesario incluir una diferencia temprana para cubrir los índices que se tratan más adelante, diferencias esenciales. El primer ejemplo ([1515, 1520, 1500, 1535]) falla en esto. Debido a esto, lo deseché en la sección a continuación y expandí el paso 4 para resolverlo.

Entonces, ahora podemos ver los casos especiales:

** como anteriormente **
** como anteriormente **
Si n es 1, pero el primer elemento proporcionará dos índices, no podemos seleccionarlo. Tenemos que tirar ese artículo y repetirlo. Esta vez todavía estamos buscando n índices, y no se han realizado cambios en nuestro conjunto aceptado.
Si n es 2 o más, tenemos una opción. O bien, podemos a) elegir este elemento y repetir la búsqueda en busca de n - (1 o 2) índices, o b) omitir este elemento, y solicitar asistencia en busca de n índices.

4 es donde se vuelve complicado, y donde esta rutina se convierte en una búsqueda en lugar de solo un ejercicio de clasificación. ¿Cómo podemos decidir qué rama (aob) tomar? Bueno, somos recursivos, así que llamemos a ambos y veamos cuál es mejor. ¿Cómo los juzgaremos?

Queremos tomar cualquier rama que produzca la suma más baja.
... pero solo si usará el número correcto de índices.

Así que el paso 4 se convierte en algo así (pseudocódigo):

x = numberOfIndicesProvidedBy(currentDifference) branchA = findSmallestDifference (n-x, remainingDifferences) // recurse looking for **n-(1 or 2)** branchB = findSmallestDifference (n , remainingDifferences) // recurse looking for **n** sumA = currentDifference + sumOf(branchA) sumB = sumOf(branchB) validA = indicesAddedBy(branchA) == n validB = indicesAddedBy(branchB) == n if not validA && not validB then return an empty branch if validA && not validB then return branchA if validB && not validA then return branchB // Here, both must be valid. if sumA <= sumB then return branchA else return branchB

Codifiqué esto en Haskell (porque estoy tratando de ser bueno en eso). No estoy seguro de publicar todo esto, porque podría ser más confuso que útil, pero aquí está la parte principal:

findSmallestDifference = findSmallestDifference'' Set.empty findSmallestDifference'' _ _ [] = [] findSmallestDifference'' taken n (d:ds) | n == 0 = [] -- Case 1 | n == 1 && provides1 d = [d] -- Case 2 | n == 1 && provides2 d = findSmallestDifference'' taken n ds -- Case 3 | provides0 d = findSmallestDifference'' taken n ds -- Case 3a (See Edit) | validA && not validB = branchA -- Case 4 | validB && not validA = branchB -- Case 4 | validA && validB && sumA <= sumB = branchA -- Case 4 | validA && validB && sumB <= sumA = branchB -- Case 4 | otherwise = [] -- Case 4 where branchA = d : findSmallestDifference'' (newTaken d) (n - (provides taken d)) ds branchB = findSmallestDifference'' taken n ds sumA = sumDifferences branchA sumB = sumDifferences branchB validA = n == (indicesTaken branchA) validB = n == (indicesTaken branchA) newTaken x = insertIndices x taken

Esperemos que puedas ver todos los casos allí. Ese código (-ish), más algún envoltorio produce esto:

*Main> findLeastDiff 6 [1731, 1572, 2041, 1561, 1682, 1572, 1609, 1731] Smallest Difference found is 48 1572 - 1572 = 0 1731 - 1731 = 0 1572 - 1561 = 11 1609 - 1572 = 37 *Main> findLeastDiff 4 [1515, 1520, 1500,1535] Smallest Difference found is 30 1515 - 1500 = 15 1535 - 1520 = 15

Esto se ha vuelto largo, pero he tratado de ser explícito. Esperemos que haya merecido la pena.

Edición : hay un caso 3a que se puede agregar para evitar un trabajo innecesario. Si la diferencia actual no proporciona índices adicionales, se puede omitir. Esto se ha resuelto en el paso 4 anterior, pero no tiene sentido evaluar ambas mitades del árbol sin ganancia. He añadido esto al Haskell.

La solución de marcog es una solución correcta, no recursiva, de tiempo polinomial al problema, es un problema de DP bastante estándar, pero, para completar, aquí hay una prueba de que funciona, y un código real para el problema. [@marcog: siéntase libre de copiar cualquier parte de esta respuesta en su cuenta si lo desea; Entonces eliminaré esto.]

Prueba

Deje que la lista sea x ₁ , ..., x _N. Supongamos wlog que la lista está ordenada. Estamos tratando de encontrar K (disjuntos) pares de elementos de la lista, de modo que la suma de sus diferencias se minimice.

Reclamo : Una solución óptima siempre consiste en las diferencias de elementos consecutivos.
Prueba : suponga que arregla el subconjunto de elementos cuyas diferencias se toman. Luego, según la prueba proporcionada por Jonas Kölker , la solución óptima solo para este subconjunto consiste en diferencias de elementos consecutivos de la lista. Ahora suponga que hay una solución correspondiente a un subconjunto que no comprende pares de elementos consecutivos, es decir, la solución implica una diferencia x _j -x _i donde j> i + 1. Entonces, podemos reemplazar x _j con x _{i + 1} para obtener una diferencia menor, ya que
x _i ≤ x _{i + 1} ≤ x _j ⇒ x _{i + 1} -x _i ≤ x _j -x _i .
(No hace falta decir que si x _{i + 1} = x _j , entonces tomar x _{i + 1} es indistinguible de tomar x _j .) Esto prueba la afirmación.

El resto es solo una rutina de programación dinámica: la solución óptima que usa k pares de los primeros n elementos tampoco usa el elemento nth (en este caso es la solución óptima que usa k pares desde el primer n-1), o usa el elemento nth, en cuyo caso es la diferencia x _n -x _n-1 más la solución óptima utilizando pares k-1 desde el primer n-2.

Todo el programa se ejecuta en el tiempo O (N log N + NK), como dice marcog. (Clasificación + DP.)

Código

Aquí hay un programa completo. Yo era perezoso con la inicialización de matrices y escribí el código de Python usando dictados; este es un pequeño factor de registro (N) sobre el uso de matrices reales.

'''''' The minimum possible sum|x_i - x_j| using K pairs (2K numbers) from N numbers '''''' import sys def ints(): return [int(s) for s in sys.stdin.readline().split()] N, K = ints() num = sorted(ints()) best = {} #best[(k,n)] = minimum sum using k pairs out of 0 to n def b(k,n): if best.has_key((k,n)): return best[(k,n)] if k==0: return 0 return float(''inf'') for n in range(1,N): for k in range(1,K+1): best[(k,n)] = min([b(k,n-1), #Not using num[n] b(k-1,n-2) + num[n]-num[n-1]]) #Using num[n] print best[(K,N-1)]

Pruébalo:

Input 4 2 1515 1520 1500 1535 Output 30 Input 8 3 1731 1572 2041 1561 1682 1572 1609 1731 Output 48

Me gustaría ir con la respuesta de marcog, puede ordenar utilizando cualquiera de los algoritmos de clasificación. Pero hay poco que analizar ahora.

Si tiene que elegir números R, N números de modo que la suma de sus diferencias sea mínima, entonces los números se elegirán en una secuencia sin perder ningún número entre ellos.

Por lo tanto, después de ordenar la matriz, debe ejecutar un bucle externo de 0 a NR y un bucle interno de 0 a R-1 veces para calcular la suma de las diferencias.

Si es necesario, intente con algunos ejemplos.

Ordene la lista, luego haga el cálculo de la diferencia.

EDITAR: hola @hey

Puedes resolver el problema utilizando la programación dinámica.

Digamos que tienes una lista L de N enteros, debes formar k pares (con 2*k <= N )

Cree una función que encuentre la menor diferencia dentro de una lista (si la lista está ordenada, será más rápida;) llámela la más smallest(list l)

Construya otro que encuentre el mismo para dos pares (puede ser complicado, pero factible) y llámelo más smallest2(list l)

Definamos best(int i, list l) la función que le da el mejor resultado para i pares dentro de la lista l

El algoritmo es el siguiente:

mejor (1, L) = más pequeño (L)
best (2, L) = smallest2 (L)
para i de 1 a k:

lazo

compute min ( stored_best(i-2) - smallest2( stored_remainder(i-2) ), stored_best(i-1) - smallest( stored_remainder(i-1) ) and store as best(i) store the remainder as well for the chosen solution

Ahora, el problema es que una vez que haya elegido un par, los dos ints que forman los límites están reservados y no se pueden utilizar para formar una mejor solución. Pero al mirar dos niveles atrás, puede garantizar que ha permitido el cambio de candidatos.

(El trabajo de conmutación es realizado por el smallest2 )

Sé que usted dijo que no necesitaba código, pero es la mejor manera de describir una solución basada en conjuntos. La solución se ejecuta bajo SQL Server 2008. En el código se incluyen los datos de los dos ejemplos que proporciona. La solución de SQL se podría hacer con una sola tabla de autounidad, pero me resulta más fácil de explicar cuando hay varias tablas.

--table 1 holds the values declare @Table1 table (T1_Val int) Insert @Table1 --this data is test 1 --Select (1515) Union ALL --Select (1520) Union ALL --Select (1500) Union ALL --Select (1535) --this data is test 2 Select (1731) Union ALL Select (1572) Union ALL Select (2041) Union ALL Select (1561) Union ALL Select (1682) Union ALL Select (1572) Union ALL Select (1609) Union ALL Select (1731) --Select * from @Table1 --table 2 holds the sorted numbered list Declare @Table2 table (T2_id int identity(1,1), T1_Val int) Insert @Table2 Select T1_Val from @Table1 order by T1_Val --table 3 will hold the sorted pairs Declare @Table3 table (T3_id int identity(1,1), T21_id int, T21_Val int, T22_id int, T22_val int) Insert @Table3 Select T2_1.T2_id, T2_1.T1_Val,T2_2.T2_id, T2_2.T1_Val from @Table2 AS T2_1 LEFT Outer join @Table2 AS T2_2 on T2_1.T2_id = T2_2.T2_id +1 --select * from @Table3 --remove odd numbered rows delete from @Table3 where T3_id % 2 > 0 --select * from @Table3 --show the diff values --select *, ABS(T21_Val - T22_val) from @Table3 --show the diff values in order --select *, ABS(T21_Val - T22_val) from @Table3 order by ABS(T21_Val - T22_val) --display the two lowest select TOP 2 CAST(T22_val as varchar(24)) + '' and '' + CAST(T21_val as varchar(24)) as ''The minimum difference pairs are'' , ABS(T21_Val - T22_val) as ''Difference'' from @Table3 ORDER by ABS(T21_Val - T22_val)

Supongo que el problema general es el siguiente: dada una lista de 2n enteros, genere una lista de n pares, de manera que la suma de | x - y | sobre todos los pares (x, y) es lo más pequeño posible.

En ese caso, la idea sería:

ordena los números
emitir (numbers[2k], numbers[2k+1]) para k = 0, ..., n - 1 .

Esto funciona. Prueba:

Supongamos que tiene x_1 < x_2 < x_3 < x_4 (posiblemente con otros valores entre ellos) y salida (x_1, x_3) y (x_2, x_4) . Entonces

|x_4 - x_2| + |x_3 - x_1| = |x_4 - x_3| + |x_3 - x_2| + |x_3 - x_2| + |x_2 - x_1| >= |x_4 - x_3| + |x_2 - x_1| .

En otras palabras, siempre es mejor emitir (x_1, x_2) y (x_3, x_4) porque no cubre el espacio entre x_2 y x_3 dos veces de manera x_3 . Por inducción, el número más pequeño de la 2n debe emparejarse con el segundo número más pequeño; por inducción en el resto de la lista, el emparejamiento de los vecinos más pequeños siempre es óptimo, por lo que el boceto del algoritmo que propuse es correcto.

Teniendo en cuenta la edición:

Comience por ordenar la lista. Luego use una solución de programación dinámica, donde el estado i , n representa la suma mínima de n diferencias al considerar solo los primeros números i en la secuencia. Estados iniciales: dp [*] [0] = 0, todo lo demás = infinito. Use dos bucles: el bucle externo que pasa por i desde 1 a N , el bucle interno que pasa por n desde 0 hasta R (3 en su caso de ejemplo en su edición: esto usa 3 pares de números, lo que significa 6 números individuales). Su relación de recurrencia es dp [i] [n] = min (dp [i-1] [n], dp [i-2] [n-1] + seq [i] - seq [i-1]).

Debe tener en cuenta el manejo de casos de límites que he ignorado, pero la idea general debería funcionar y se ejecutará en O ( N log N + NR ) y usará el espacio O ( NR ).

Paso 1: Calcular las diferencias de pares

Creo que es bastante obvio que el enfoque correcto es ordenar los números y luego tomar las diferencias entre cada par de números adyacentes. Estas diferencias son las diferencias "candidatas" que contribuyen a la suma de la diferencia mínima. Usar los números de tu ejemplo llevaría a:

Number Diff ====== ==== 1561 11 1572 0 1572 37 1609 73 1682 49 1731 0 1731 310 2041

Guarde las diferencias en una matriz o tabla o alguna otra estructura de datos donde pueda mantener las diferencias y los dos números que contribuyeron a cada diferencia. Llama a esto el DiffTable . Debería verse algo como:

Index Diff Number1 Number2 ===== ==== ======= ======= 1 11 1561 1572 2 0 1572 1572 3 37 1572 1609 4 73 1609 1682 5 49 1682 1731 6 0 1731 1731 7 310 1731 2041

Paso 2: Elige las diferencias mínimas

Si todos los números tuvieran que ser elegidos, podríamos habernos detenido en el paso 1 al elegir el par de números para los índices de números impares: 1, 3, 5, 7. Esta es la respuesta correcta. Sin embargo, el problema indica que se elige un subconjunto de pares y esto complica bastante el problema. En su ejemplo, 3 diferencias (6 números = 3 pares = 3 diferencias) deben elegirse de modo que:

La suma de las diferencias es mínima.
Los números que participan en cualquier diferencia elegida se eliminan de la lista.

El segundo punto significa que si elegimos Diff 11 (Índice = 1 arriba), los números 1561 y 1572 se eliminan de la lista, y en consecuencia, el siguiente Diff de 0 en el índice 2 no se puede usar porque solo queda 1 instancia de 1572 . Cada vez que se elige un Diff , se eliminan los valores Diff adyacentes. Es por esto que solo hay una forma de elegir 4 pares de números de una lista que contiene ocho números.

Acerca del único método que se me ocurre para minimizar la suma de la Diff anterior es generar y probar.

El siguiente pseudo código describe un proceso para generar todos los conjuntos de valores de índice ''legales'' para una DiffTable de tamaño arbitrario donde se elige un número arbitrario de pares de números. Uno (o más) de los conjuntos de índices generados contendrán los índices en la DiffTable arroja una suma mínima de DiffTable .

/* Global Variables */ M = 7 /* Number of candidate pair differences in DiffTable */ N = 3 /* Number of indices in each candidate pair set (3 pairs of numbers) */ AllSets = [] /* Set of candidate index sets (set of sets) */ call GenIdxSet(1, []) /* Call generator with seed values */ /* AllSets now contains candidate index sets to perform min sum tests on */ end procedure: GenIdxSet(i, IdxSet) /* Generate all the valid index values for current level */ /* and subsequent levels until a complete index set is generated */ do while i <= M if CountMembers(IdxSet) = N - 1 then /* Set is complete */ AllSets = AppendToSet(AllSets, AppendToSet(IdxSet, i)) else /* Add another index */ call GenIdxSet(i + 2, AppendToSet(IdxSet, i)) i = i + 1 end return

La función CountMembers devuelve el número de miembros en el conjunto dado, la función AppendToSet devuelve un nuevo conjunto donde los argumentos se agregan a un único conjunto ordenado. Por ejemplo, AppendToSet([a, b, c], d) devuelve el conjunto: [a, b, c, d] .

Para los parámetros dados, M = 7 y N = 3, AllSets se convierte en:

[[1 3 5] [1 3 6] <= Diffs = (11 + 37 + 0) = 48 [1 3 7] [1 4 6] [1 4 7] [1 5 7] [2 4 6] [2 4 7] [2 5 7] [3 5 7]]

Calcule las sumas utilizando cada conjunto de índices, el mínimo que identifica los pares de números requeridos en DiffTable . Más arriba, le muestro que el segundo conjunto de índices le da el mínimo que está buscando.

Esta es una técnica simple de fuerza bruta y no se escala muy bien. Si tuviera una lista de 50 pares de números y quisiera elegir los 5 pares, AllSets contendría 1,221,759 conjuntos de pares de números para probar.