Entiendo que el problema es:
Dado un conjunto de enteros positivos [matemática] S [/ matemática] todos diferentes (es decir, no un conjunto múltiple) y dos límites [matemática] L_1, L_2 [/ matemática], encuentre cuatro números distintos [matemática] x_1, x_2, x_3 , x_4 \ en S [/ matemáticas] con la suma mayor, dadas las restricciones [matemáticas] x_1 + x_2 \ leq L_1 [/ matemáticas], [matemáticas] x_3 + x_4 \ leq L_2 [/ matemáticas]. Si no se requiere que los dos subconjuntos sean disjuntos, entonces el problema se vuelve más fácil.
Hay un algoritmo trivial [matemático] O (n ^ 4) [/ matemático] para lograr esto que podría ser lo suficientemente bueno para algunos entornos de programación competitivos. Sin embargo, podemos hacerlo mejor.
Suponga que [math] x_1 + x_2 [/ math] es la solución más conocida para el subconjunto delimitado por [math] L_1 [/ math]. ¿Cuánto peor tendríamos que hacer esta solución para encontrar el par limitado por [math] L_2 [/ math] que sea la mejor solución general? Ciertamente, no es peor que el segundo mejor par de números que no están en nuestro par original, [math] x_1 ‘, x_2’ [/ math].
- Cómo resolver [matemáticas] 3xe ^ {(7x + 2)} = 15 [/ matemáticas]
- ¿Existe alguna teoría especial para resolver este problema? Encuentre los dos últimos dígitos de [matemática] S [/ matemática] si [matemática] S = 1 ^ N + 2 ^ N + 3 ^ N + \ ldots + K ^ N [/ matemática ] y dado que [matemáticas] 2 \ le K \ le 10 ^ {16}, \; 2 \ le N \ le 10 ^ {16}? [/ Matemáticas]
- ¿Cuántos puntos se necesitan para definir de forma exclusiva una función cúbica?
- ¿A qué función matemática se puede aproximar este gráfico?
- ¿Por qué [math] \ left (\ sqrt {2} ^ \ sqrt {2} \ right) ^ \ sqrt {2} = 2 [/ math]?
Podemos encontrar los pares de suma más alta de modo que [matemática] x_1 + x_2 \ leq L_1 [/ matemática] en un tiempo no peor que [matemática] O (N \ log N) [/ matemática]. Primero ordenar [math] S [/ math] si aún no está ordenado. Luego proceda de la siguiente manera:
1. Inicialice T al miembro más grande de S, y B al miembro más pequeño de S.
2. Si [math] T + B> L_1 [/ math], entonces tenemos que hacer la suma más pequeña, así que disminuya T al siguiente número más pequeño en S.
3. De lo contrario, compare [matemáticas] (T, B) [/ matemáticas] con el mejor par hasta ahora, y recuerde si es más grande. (Salga si la suma es exactamente igual a [matemática] L_1 [/ matemática].) Incremente B al siguiente número más alto en S.
4. Pare cuando T = B.
Esta subrutina realiza a lo sumo [math] N [/ math] iteraciones ya que consumimos un elemento del subconjunto por ciclo. Ejecute la subrutina un total de ocho veces:
1. Primero extraiga la mejor [matemática] x_1 + x_2 [/ matemática] de todas las [matemática] S [/ matemática] y calcule la mejor suma limitada de los números restantes (sujeto a [matemática] L_2 [/ matemática])
2. Luego calcule el mejor par [math] x_1 ‘+ x_2 [/ math] para [math] L_1 [/ math] de [math] S – \ {x_1 \} [/ math] y el mejor par correspondiente para [math] ] L_2 [/ math] de [math] S – \ {x_1 ‘, x_2 \} [/ math]
3. Luego use [math] S – \ {x_2 \} [/ math] como conjunto inicial para [math] L_1 [/ math].
4. Finalmente calcule nuevamente con [math] S – \ {x_1, x_2 \} [/ math].
Todas las soluciones resultantes satisfacen los criterios de distinción, y una (o más) tendrá la mejor suma posible. (Nuevamente, puede salir antes si encuentra una solución igual a la mejor posible, [matemática] L_1 + L_2 [/ matemática].) El tiempo de ejecución es [matemática] O (N) [/ matemática] si la entrada ya está ordenada , y [math] O (N \ log N) [/ math] si se requiere una ordenación.
Si se permite que el conjunto 1 y el conjunto 2 se superpongan, simplemente ejecute la subrutina para encontrar el mejor par dos veces, una con cada límite.