Cómo verificar si la suma de los números de la primera mitad y la segunda mitad de una matriz es la misma

Hay una solución simple de programación dinámica como se mencionó Kunal Kukreja. Tiene sentido, solo si los números son relativamente pequeños.

Supongamos que todos los números no son negativos. (Si hay números negativos, podemos restar el más pequeño de los otros para eliminar los números negativos).

Definamos [math] f_ {i, j} = 1 [/ math] si hay tales números [math] i [/ math] que tienen una suma igual a [math] j [/ math], falso de lo contrario.

La respuesta es NO, si la suma de todos los números [matemática] S = \ sum ^ {n-1} _ {i = 0} a_i [/ ​​matemática] es impar.

1) Inicializar f:
[matemáticas] f_ {0,0} = 1 [/ matemáticas],
[matemática] f_ {i, j} = 0 [/ matemática], [matemática] i = \ overline {1, n} [/ matemática], [matemática] j = \ overline {0, n} [/ matemática].

2) Luego repita todos los números [math] a_0, a_2, \ ldots, a_ {n-1} [/ math] y recalcule [math] f [/ math], para cada número [math] a_e [/ math]:
set [matemáticas] f_ {i + 1, j + a_e} = 1 [/ matemáticas], si [matemáticas] f_ {i, j} = 1 [/ matemáticas], [matemáticas] i = \ overline {0, \ min (e, \ frac {n} {2})} [/ matemática], [matemática] j = \ overline {0, \ frac {1} {2} S – a_e} [/ matemática], [matemática] e = \ overline {0, n-1} [/ math].

Si [math] f _ {\ frac {n} {2}, \ frac {S} {2}} = 1 [/ math], entonces la respuesta a su pregunta es SÍ, de lo contrario NO.

Complejidad:
[matemáticas] O (n S) [/ matemáticas] – tiempo
[matemáticas] O (n S) [/ matemáticas] – memoria.

Encuentra la suma de todos los elementos de la matriz. Si la suma es impar, entonces la respuesta seguramente será “NO”. Si no, entonces continúe.

1.) Fuerza bruta:

El método más fácil sería Brute Force sobre todas las formas posibles de recoger números ‘n / 2’ de la matriz. Esto se puede hacer de [math] \ binom {n} {\ frac {n} {2}} [/ math] formas. Si la suma de los números elegidos es igual a la mitad de la suma total de los elementos de la matriz, escriba “SÍ”.

Implementación: Ideone.com

Estoy bastante seguro de que existe una solución de programación dinámica para este problema. Tal como lo imagino, lo publicaré.

Puede ayudar al concepto de búsqueda binaria, que es un concepto de Estructura de datos.

Debido a que la estructura de datos se basa en una matriz y una lista de enlaces, sabrá mejor cómo funciona la búsqueda binaria.

Consulte un libro Estructura de datos usando C

PDF puede estar disponible en la red.