Número máximo de grupos similares de un tamaño dado que se puede hacer de una matriz dada

Question

Me da una matriz de números, no necesariamente únicos, y el tamaño de un grupo. Deje que la matriz sea denotada por $ b $ y el tamaño del grupo sea $ a $ .

Necesito encontrar el número máximo de grupos con exactamente los mismos contenidos y de tamaño $ a $ que se pueden hacer de los elementos de $ b $ . Una vez que se usa un elemento en un grupo. Está agotado. Un grupo puede tener más de un elemento con el mismo valor siempre y cuando el elemento aún esté disponible en $ b $ .

Ejemplo:

1. Si la matriz de entrada es $ \ {1, 2, 3, 1, 2, 3, 4 \} $ , y el tamaño del grupo es $ 3 $ El número máximo de grupos que se puede hacer es $ 2 $ , que son $ \ {1, 2, 3 \} $ y $ \ {1, 2, 3 \} $ .
2. Si la matriz de entrada es $ \ {1, 3, 3, 3, 6, 3, 10 \} $ , y el tamaño del grupo es $ 4 $ El número máximo de grupos que se puede hacer es $ 1 $ , que es $ \ {1, 3, 3, 3 \} $ .

Lo que he intentado hasta ahora es enmarcar algunas ecuaciones (dadas a continuación), pero después de eso, estoy luchando por llegar a un algoritmo para resolverlos.

Permitir $ f_1 $ ser la frecuencia del elemento $ b_1 $ , $ F_2 $ Sé la frecuencia del elemento $ b_2 $ y así sucesivamente hasta $ B_n $ , donde $ b_1 \ dots b_n $ son elementos distintos de la matriz $ b $ .

Ahora necesito elegir $ n_1, n_2, \ dots n_i $ de tal manera que

1. $ n_1 + n_2 + \ dots + n_i= a $
2. $ k \ cdot n_1 \ leq f_1 \ texto {,} k \ cdot n_2 \ leq f_2 \ texto {,} \ dots \ texto {,} K \ CDOT N_I \ leq f_i $
3. $ k $ es el número de grupos y tenemos que maximizarlo.

Duración de $ b $ puede ser tan grande como $ 10 ^ 5 $ y $ A $ también puede ser tan grande como $ 10 ^ 5 $ .

Por favor, ayúdame a encontrar un enfoque codicioso o dinámico al problema.

Answer 1

la función $$ F: \ mathbb {n} \ rudotrow \ {0, 1 \}: f (k)= \ comienzan {casos} 1; & \ texto {si hay una solución de tamaño $ k $,} \\ 0; & \ texto {lo contrario} \ End {casos} $$ es monoton, ya que si no hay solución de tamaño $ k $ entonces no hay solución de tamaño $ k + 1 $ . Eso significa que podemos buscar binary el valor de $ k $ en el intervalo $ [1, | b |] $ , y salga del mejor $ k $ para el cual hay una solución de tamaño $ k $ . Por lo tanto, convirtudimos el problema en un problema de decisión con un $ O (\ log | b |) $ factor en el tiempo de ejecución.

Para un valor fijo de $ k $ , se basa en una solución codiciosa. Si tenemos $ f_i $ copias de algún elemento $ b_i $ , entonces cada conjunto puede contener a lo sumo < Span Class="Math-contenedor"> $ \ izquierda \ lfloor \ frac {f_i} {k} \ derecha \ rfloor $ de este elemento. Así que tenemos una solución de tamaño $ k $ si y solo si $$ \ sum \ limits_ {i= 1} ^ {n} \ izquierda \ lfloor \ frac {f_i} {k} \ derecha \ rfloor \ geq a. $$

Como ejercicio, intente demostrar que la solución codiciosa es óptima. El tiempo de ejecución puede estar limitado en $ O (| b | \ log | b |). $