¿Cómo particionar un conjunto múltiple de enteros positivos en tres subconjuntos de modo que se minimice la diferencia entre las sumas de subconjuntos máximas y mínimas?

Answer 1

De acuerdo, entonces necesitarás mantener una buena atención y resolver los detalles más pequeños tú mismo porque es un enfoque un poco complicado, que debería funcionar de todos modos.

Primero debe comprender lo que el problema está pidiendo: dada una matriz de partición de tamaño [matemático] n [/ matemático] en tres formas, de modo que se minimice la diferencia entre la suma mínima y máxima de una partición.

Resolvamos algo más fácil primero: el mismo problema que el anterior pero solo dos particiones.

El enfoque de fuerza bruta es [matemática] O (2 ^ n) [/ matemática] (eso también si usas hashmap o algo así).

Mejor idea:

Cree dos conjuntos de tamaño casi igual y para cada conjunto genere todas las particiones posibles de tamaño dos, es decir, un total de particiones [math] O (2 ^ {n / 2}) [/ math] para cada conjunto. Digamos que representamos cada partición por [math] (a, b) [/ math] donde [math] a [/ math] y [math] b [/ math] son ​​la suma de dos partes en la partición.

Ahora, iteramos sobre las particiones [math] p_1 [/ math] de un conjunto e intentamos elegir una partición [math] p_2 [/ math] del otro conjunto de manera que:

• Mantendremos la condición de que la suma de la segunda parte será mayor o igual que la suma de la primera parte. Entonces, [matemáticas] a_1 [/ matemáticas] [matemáticas] + a_2 \ le b_1 + b_2 [/ matemáticas]. Esto implica una condición que para [matemática] p_2 [/ matemática], [matemática] (b_2 [/ matemática] [matemática] – a_2) \ ge (a_1 – b_1) [/ matemática].
• De acuerdo con la condición anterior, tenemos que minimizar [matemáticas] b_1 [/ matemáticas] [matemáticas] + b_2 – (a_1 + a_2) [/ matemáticas] es decir [matemáticas] (b_2 – a_2) – (a_1 – b_1) [/ matemáticas].

Estas condiciones y requisitos simples sugieren que clasifique todas las particiones del conjunto dos de acuerdo con [matemática] c [/ matemática], donde para una partición [matemática] (a, b) [/ matemática], [matemática] c = [/ matemática] [matemáticas] ba [/ matemáticas]. Luego, para una partición [math] (a_1, b_1) [/ math] del conjunto uno, encontrará una partición del conjunto dos de modo que [math] c [/ math] sea simplemente mayor que [math] c_1 [/ math ] Esto se puede hacer usando la búsqueda binaria fácilmente.

Entonces, logramos reducir la complejidad a [matemáticas] O (n * 2 ^ {n / 2}) [/ matemáticas].

Ahora, al problema original. Utilizamos la idea similar y creamos dos conjuntos de tamaño [matemática] n / 2 [/ matemática]. Para cada conjunto, generamos particiones [math] O (3 ^ {n / 2}) [/ math] (denotadas por sumas [math] (a, b, c) [/ math]). Nuevamente, iteramos sobre las particiones de un conjunto (digamos [math] (a_1, b_1, c_1) [/ math]) e intentamos elegir la partición [math] (a_2, b_2, c_2) [/ math] del otro conjunto como ese:

• Mantener condiciones que [matemáticas] a_1 + a_2 \ le b_1 + b_2 \ le c_1 + c_2 [/ matemáticas], que se pueden dividir en dos condiciones como [matemáticas] b_2-a_2 \ ge a_1-b_1 [/ matemáticas] y [ matemáticas] c_2-b_2 \ ge b_1-c_1 [/ matemáticas].
• De acuerdo con la condición anterior, tenemos que minimizar [matemática] c_1 + c_2 – (a_1 + a_2) [/ matemática] es decir [matemática] (c_2 – a_2) – (a_1 – c_1) [/ matemática], que es equivalente a minimizando [math] c_2-a_2 [/ math], ya que las condiciones anteriores ya garantizan que este valor será positivo.

Ahora, dos encuentran rápidamente una partición del otro conjunto que satisface esta condición y minimiza el valor requerido es un problema complejo de estructuras de datos.

Lo reformulo como: se le da una matriz [matemática] A [/ matemática] de tuplas [matemática] (x, y, z) [/ matemática] y una matriz [matemática] B [/ matemática] de consultas de forma [ matemáticas] (k, l) [/ matemáticas]. Aquí la equivalencia entre estas variables y las antiguas es que

• [matemática] x = ba [/ matemática], [matemática] y = cb [/ matemática] y [matemática] z = ca [/ matemática].
• [matemática] k = a_1-b_1 [/ matemática] y [matemática] l = b_1-c_1 [/ matemática]

Debe encontrar el valor mínimo de [math] z_i [/ ​​math], tal que [math] x_i \ ge k [/ math] y [math] y_i \ ge l [/ math]. La idea para resolver este problema es el manejo fuera de línea de consultas. Clasificamos array [math] A [/ math] según [math] x [/ math] y ordenamos array [math] B [/ math] según [math] k [/ math]. Luego mantenemos dos punteros [matemática] pt1 [/ matemática] y [matemática] pt2 [/ matemática], ambos inicialmente al final de las matrices [matemática] A [/ matemática] y [matemática] B [/ matemática]. Siempre alineamos estos punteros de manera tal que [matemática] pt1 [/ matemática] sea mínima y [matemática] x_ {pt1} \ ge k_ {pt2} [/ matemática] y luego movemos [matemática] pt2 [/ matemática] hacia atrás. Tenga en cuenta que en cada momento, mantenemos todas esas tuplas de la matriz [math] A [/ math] cuya primera condición se cumple, en una estructura de datos, digamos [math] S [/ math]. Tenga en cuenta que esta estructura de datos debe manejar las inserciones en tiempo sublineal, porque el puntero [math] pt1 [/ math] también se moverá hacia atrás. Nuestro objetivo es encontrar un elemento [math] j [/ math] de esta estructura, de modo que [math] z_j [/ math] sea mínimo y [math] y_j \ ge l [/ math]. Podemos hacer esto en [math] O (\ textrm {log} (\ textrm {tamaño de B})) [/ math]. ¿Cómo? Si los valores [math] y [/ math] son ​​menores, puede usar BIT para esto, de lo contrario: use compresión o árbol de segmentos implícito.

Por lo tanto, logramos resolver el problema en [matemáticas] O (n * 3 ^ {n / 2}) [/ matemáticas].