Dado un conjunto de números naturales [matemáticos] n [/ matemáticos], encuentre los dos subconjuntos de números ‘k’, cuya suma es [matemática] S_k [/ matemática], que minimizan la diferencia entre estas sumas. ¿Cómo lo resuelves con programación dinámica?

Answer 1

Defina [matemática] D [i, j, k] = verdadero [/ matemática] si existe alguna [matemática] A, B \ subconjunto \ {a_1, …, a_i \} [/ matemática] tal que [matemática] A \ cap B = \ conjunto vacío [/ matemática], [matemática] | A | = | B | + j [/ math] con [math] j \ geq 0 [/ math] y [math] \ sum_ {x \ in A} {x} = k + \ sum_ {y \ in B} {y} [/ math ], Requerimos que al menos uno de A y B no esté vacío. Tenga en cuenta que [math] k [/ math] puede ser positivo o negativo.

Entonces, una recurrencia que se puede utilizar para la programación dinámica es
[matemáticas] D [i, j, k] = D [i-1, j, k] \ lor [/ matemáticas]
[matemáticas] D [i-1, j-1, k – a_ {i}] \ lor [/ matemáticas]
[matemáticas] D [i-1, j + 1, k + a_ {i}] \ lor [/ matemáticas]
[matemáticas] (j = 1 \ tierra D [i-1,0, – (k-a_ {i})]) \ lor [/ matemáticas]
[matemáticas] (j = 1 \ tierra k = a_ {i}) [/ matemáticas]

Los casos aquí corresponden a (1) no usar [matemática] a_i [/ ​​matemática], (2) agregar [matemática] a_i [/ ​​matemática] a A, (3) agregar [matemática] a_i [/ ​​matemática] a B, ( 4) agregar [math] a_i [/ ​​math] a B para que se convierta en el conjunto más grande, o (5) establecer [math] A = {a_i} [/ math] y [math] B = \ emptyset [/ math] .

Por ejemplo, si D [8, 0, 4] es verdadero y [matemáticas] a_i = 5 [/ matemáticas], entonces D [9, 1, 9] también debe ser verdadero, y también lo es D [9, 1, 1] (No he implementado el código, solo lo he prototipado en papel, por lo que es posible que tenga un error de señal en alguna parte …)

Después de calcular los valores de recurrencia comenzando en [matemática] i = 1 [/ matemática] y concluyendo con [matemática] i = n [/ matemática], examine los valores verdaderos [matemática] D [n, 0, k] [/ matemática] y seleccione [math] k [/ math] con el valor absoluto más bajo. Esta es la solución al problema de optimización. Anotar cada D con un puntero “padre” (puede haber múltiples pero solo necesitamos uno) nos permitirá reconstruir los conjuntos A y B.

El tiempo de ejecución de este algoritmo no es particularmente bueno. Podemos vincular el valor absoluto de [math] k [/ math] a la mitad de la suma del conjunto, por lo que el tiempo de ejecución no debe ser peor que [math] O (n ^ {2} N) [/ math], y probablemente mejor en la práctica al usar hashes para almacenar [math] k [/ math] ‘s en lugar de una matriz.

Answer 2

Esto está muy cerca de pedir un algoritmo de aproximación al problema de partición. La única diferencia es que el problema de la partición no requiere que los dos conjuntos sean del mismo tamaño. Tal vez podría obtener una idea al buscar soluciones al problema de partición.

Answer 3

El enfoque de Mark Gritter es de hecho la forma correcta de pensar sobre el problema.
Daré una solución más simple (pero menos eficiente) y luego la refinaré en una solución que es esencialmente la que dio Mark Gritter.

Definamos [matemáticas] G [i, j, S_A, S_B] = Verdadero [/ matemáticas] si existe una asignación para establecer [matemáticas] A [/ matemáticas] y [matemáticas] B [/ matemáticas] utilizando solo elementos de [matemáticas ] a_1, a_2,…, a_i [/ ​​matemática] tal que [matemática] A \ cap B = \ conjunto vacío [/ matemática] y [matemática] | A | – | B | = j [/ matemática] y [matemática] \ sum \ limits_ {x \ in A} {} x = S_A [/ math] y [math] \ sum \ limits_ {y \ in B} {} y = S_B [/ math].

¿Cómo obtenemos [matemáticas] G [i, j, S_A, S_B] [/ matemáticas] recursivamente?

Bueno, podemos usar la siguiente recurrencia (ignorando los casos base)
[matemáticas] G [i, j, S_A, S_B] = G [i-1, j, S_A, S_B] [/ matemáticas] O [matemáticas] G [i-1, j-1, S_A-a_i, S_B] [/ math] OR [math] G [i-1, j + 1, S_A, S_B-a_i] [/ math] lo que esto significa en inglés simple es que tenemos tres formas posibles de usar el elemento [math] a_i [ /matemáticas]. Podemos:

1. No lo agregue a [matemática] A [/ matemática] o [matemática] B [/ matemática] es decir [matemática] G [i-1, j, S_A, S_B] [/ matemática]
2. Agréguelo a [math] A [/ math] solamente, es decir, [math] G [i-1, j-1, S_A-a_i, S_B] [/ math]
3. Agréguelo a [math] B [/ math] solo es decir [math] G [i-1, j + 1, S_A, S_B-a_i] [/ math]

De hecho, debemos obtener [matemáticas] G [i, j, S_A, S_B] [/ matemáticas] en una de las tres formas anteriores. Una vez que hemos calculado todos los [math] G [i, j, S_A, S_B] [/ math] ‘s, podemos encontrar los correspondientes [math] S_A [/ math] y [math] S_B [/ math] con una diferencia mínima revisando nuestra tabla y mirando las entradas en [matemáticas] G [n, 0, S_A, S_B] [/ matemáticas] que son [matemáticas] Verdaderas [/ matemáticas]

Entonces, ¿cómo podemos simplificar esto? Ahí es donde entran en juego las ideas de Mark Gritter. En lugar de hacer un seguimiento de [matemáticas] S_A [/ matemáticas] y [matemáticas] S_B [/ matemáticas] por separado, ¿por qué no simplemente combinarlas en su lugar? Como estamos interesados ​​en última instancia en [math] | S_A-S_B | [/ math], también podemos hacer un seguimiento de [math] S_A – S_B [/ math].

Entonces, redefinimos nuestra recurrencia.
Definamos [math] G [i, j, k] [/ math] para que sea el mismo que el anterior, excepto que esta vez, solo hacemos un seguimiento de la diferencia entre [math] S_A [/ math] y [math] S_B [ /matemáticas]. es decir, [matemáticas] k = S_A-S_B [/ matemáticas].

Nuestra nueva recurrencia se convierte en, [matemáticas] G [i, j, k] = G [i-1, j, k] \ text {OR} [/ matemáticas] [matemáticas] G [i-1, j-1, k -a_i] \ text {OR} G [i-1, j + 1, k + a_i] [/ math]

Bueno, no del todo. La razón de esto es que es perfectamente posible obtener nuestro conjunto deseado intercambiando [matemática] A [/ matemática] y [matemática] B [/ matemática] cuando los tamaños de los conjuntos son iguales. Por lo tanto, podemos obtener nuestra asignación deseada utilizando una asignación cuyo valor [math] k [/ math] podría ser de signo opuesto. Es por eso que se incluye el otro término [matemáticas] G [i-1,0, -k + a_i] [/ matemáticas]. Tenga en cuenta que esto no era un problema anteriormente, porque definimos claramente qué son [math] S_A [/ math] y [math] S_B [/ math]. Ahora, la recurrencia completa se convierte en:

[matemáticas] G [i, j, k] = G [i-1, j, k] [/ matemáticas] [matemáticas] \ text {OR} G [i-1, j-1, k-a_i] [/ matemática] [matemática] \ text {OR} G [i-1, j + 1, k + a_i] \ text {OR} [/ math] [matemática] (G [i-1,0, -k + a_i] \ text {AND} j = 1) [/ math]