¿Cómo se pueden dividir n enteros en m subconjuntos no vacíos de modo que se minimice la diferencia entre las sumas de subconjuntos máximas y mínimas?

Answer 1

Obviamente, este es un problema NP-difícil porque el problema de Partición – Wikipedia se reduce al caso [matemática] m = 2 [/ matemática]. (El hecho de que estemos dispuestos a tomar una diferencia distinta de cero no ayuda, porque cero es la diferencia mínima). Una implementación ingenua para generar todas las particiones y encontrar la mejor. Obviamente, esto es exponencial en [matemáticas] n [/ matemáticas].

Para [math] m = 2 [/ math] hay una solución de programación dinámica bien conocida que es cuasipolinomial, tiempo [math] O (nS) [/ math] donde [math] S [/ math] es la suma de enteros Veamos si podemos adaptarlo al problema general.

Supongamos que tenemos [matemáticas] m = 3 [/ matemáticas]. ¿Podríamos arreglar una suma de subconjunto, encontrar un subconjunto que sume esa cantidad y luego usar el caso [math] m = 2 [/ math] de forma recursiva? Lamentablemente, este no parece ser el caso. Considere la entrada 1 3 4 5 5 7. La solución correcta es 1 7 | 3 5 | 4 5. Pero si buscamos comenzando con ‘8’, podríamos probar el subconjunto ‘4 3 1 que no conduce a la respuesta correcta. Y si intentamos comenzar con ‘9’, podríamos intentar con 5 3 1, que también está mal. Por lo tanto, no es suficiente tener un subconjunto con el valor correcto, lo que significa que tendríamos que probar todos los subconjuntos. (Más o menos, ver más abajo).

Sin embargo, aún podemos resolver el caso [math] m = 3 [/ math] usando la misma idea de programación dinámica. En lugar de recurrir al “elemento x dentro o fuera”, tenemos que introducir más dimensiones.

Deje que [math] p (a, b, j) [/ math] sea verdadero si hay dos subconjuntos distintos de [math] {x_1, \ ldots x_j} [/ math] que suman [math] a [/ math] y [matemáticas] b [/ matemáticas]. Entonces podemos calcular:

[matemáticas] p (a, b, j) = p (a, b, j-1) \ wedge p (a – x_ {j-1}, b, j-1) \ wedge p (a, b – x_ {j-1}, j-1) [/ matemáticas]

Desafortunadamente, el tamaño de nuestra tabla ahora es [matemática] O (n S ^ 2) [/ matemática] y esto solo empeora. “Particionamiento de números de múltiples vías” por Richard E Korf (http://ijcai.org/Proceedings/09/…) da la complejidad del espacio como [matemáticas] O (n (m-1) L ^ {m-1}) [/ math] con L del tamaño del elemento más grande. (Lo que me hace sentir que me falta algo en mi análisis y no lo entendí bien).

Ese documento prueba una reducción de la optimización: “si una partición óptima [math] k [/ math] -way incluye un subconjunto particular, entonces la división óptima de los números que no están en ese subconjunto [math] k-1 [/ math] producirá una partición óptima [matemática] k [/ matemática] ”. (Su [matemática] k [/ matemática] es su [matemática] m [/ matemática]). Él da dos algoritmos, que intentaré explicar brevemente aquí: lea el documento para obtener una explicación más completa.

Para resolver una [matemática] m [/ matemática] impar, primero ejecute un algoritmo aproximado para obtener un límite inferior [matemática] d [/ matemática] en la solución verdadera. Esto nos da un límite superior inicial [matemática] S / 2 [/ matemática] y un límite inferior inicial [matemática] (S-3d) / 4 [/ matemática]. Luego, recorra todos los subconjuntos, pero pode según los mejores límites superior e inferior encontrados hasta ahora. Decidir si incluir o excluir los números más grandes primero (del subconjunto dado) da los mejores resultados de poda. Para cada conjunto de candidatos, resuelva recursivamente los elementos restantes en subconjuntos [matemática] m-1 [/ matemática]. Continúe hasta que se hayan eliminado todos los primeros subconjuntos.

Para un problema de tamaño par, podemos aplicar una idea similar, pero en lugar de encontrar 1 de los subconjuntos [matemáticos] m [/ matemáticos], dividimos el problema en dos subconjuntos candidatos y resolvemos recursivamente cada uno de ellos. Podemos hacer esto de tal manera que obtengamos soluciones progresivamente peores. Si dividimos los números en dos subconjuntos, lo mejor que podemos esperar es que podamos resolver los subproblemas de manera óptima. Esto nos da un límite en el que podemos dejar de buscar, y podemos generar las particiones en orden creciente de diferencia entre los dos conjuntos.

La recurrencia entre los casos pares e impares da un algoritmo que se informa como 10,000 veces más rápido que los resultados conocidos previamente.

Answer 2

¡Buena pregunta! Déjame darte una idea.

Reformulemos el problema de la siguiente manera:

Tenemos m cubos yn números. ¿Cómo organizar los números entre cubos, de modo que ningún cubo permanezca vacío y la diferencia entre la suma más pequeña y la suma más grande en los cubos sea mínima posible?

Ahora el enfoque directo para resolver el problema anterior es retroceder. En cada iteración, debemos considerar como máximo m posiciones para cada uno de los números y al final calcular la diferencia entre las sumas mínimas y máximas contenidas en los cubos y volver al nivel superior de la disposición. La complejidad temporal de dicho algoritmo es de orden O (n ^ m).

partición vacía pública (int a [], int ptr, List [] buckets) {
if (ptr == a.length) {
int diff = getMaxDiff (cubos);
if (diff resultado = copyOf (cubos);
minDiff = diff;
}
regreso;
}
para (int i = 0; i if (getSum (cubos [i]) <= totalSum / m) {
cubos [i] .add (a [ptr]);
partición (a, ptr + 1, cubos);
cubos [i] .remove (cubos [i] .size () – 1);
}
}
}

El código de muestra anterior muestra la implementación del algoritmo. Tenga en cuenta que aquí utilicé heurística simple, que si los depósitos suman más que totalSum / m, entonces no es necesario agregar otro número a ese depósito. Idealmente, si la matriz se puede dividir en m subconjuntos con igual suma, cada segmento contendría números enteros que sumen un total de Suma / m.

PD: Creo que este algoritmo se puede optimizar, por supuesto. Pero solo quería dar una idea

Answer 3

Soluble mediante algoritmo codicioso. Ordene todas las entradas, luego asigne cada número entero hacia adelante y hacia atrás. Por ejemplo, según lo indicado por Mark Gritter, la entrada es 1 3 4 5 5 7, y desea asignarlos en 3 contenedores. Usted asigna 1-> 1st, 3-> 2nd, 4-> 3rd, 5-> 3rd, 5-> 2nd y 7-> 1st. Se puede encontrar un problema similar en el problema 410 “juez en línea de la uva”. Google para obtener una explicación más detallada sobre ese problema.