¿Cómo se divide una matriz en 2 partes para que las dos partes tengan el mismo promedio? Cada partición puede contener elementos que no son contiguos en la matriz. El único algoritmo en el que puedo pensar es exponencial ¿podemos mejorarlo?¿Cómo se divide una matriz en 2 partes para que las dos partes tengan el mismo promedio?
Puede reducir este problema al sum-subset problem - también cached here. Aquí está la idea.
Deje A ser la matriz. Compute S = A[0] + ... + A[N-1], donde N es la longitud de A. Para k de 1 a N-1, dejar que T_k = S * k/N. Si T_k es un número entero, busque un subconjunto de A de tamaño k que se sume a T_k. Si puedes hacer esto, entonces has terminado. Si no puede hacer esto para cualquier k, entonces no existe tal partición.
Aquí está la matemática detrás de este enfoque. Supongamos que hay una partición de A de manera que las dos partes tienen el mismo promedio, dice X del tamaño x y Y del tamaño y son las particiones, donde x+y = N. A continuación, debe tener
sum(X)/x = sum(Y)/y = (sum(A)-sum(X))/(N-x)
por lo que un poco de álgebra da
sum(X) = sum(A) * x/N
Dado que la matriz contiene números enteros, el lado izquierdo es un entero, por lo que el lado derecho tiene que ser así. Esto motiva la restricción de que T_k = S * k/N debe ser un número entero. La única parte restante es realizar T_k como la suma de un subconjunto de tamaño k.
después de un poco de pensamiento que todavía no veo cómo su prueba reduce subconjunto de suma al problema de la OP. – soulcheck
quiero decir, esencialmente has probado que tener respuesta a la suma de subconjuntos uno puede responder al problema de OP, no al revés. – soulcheck
@soulcheck Todavía estoy pensando si son realmente equivalentes. Creo que la respuesta se reduce a [esta pregunta que acabo de hacer] (http://stackoverflow.com/questions/8916539/sum-subset-with-a-fixed-subset-size). – PengOne
ser honesto, es una pregunta con la tarea? –
¿Qué has probado? ¿Funcionó? ¿Tienes algunos casos de prueba con entrada y salida de ejemplo? –
esto suena más como una pregunta de entrevista, no es fácil en ese – BrokenGlass