Número máximo de grupos semelhantes de um determinado tamanho que pode ser feito de um determinado matriz

Question

Eu recebo uma matriz de números, não necessariamente exclusivo e do tamanho de um grupo. Deixe a matriz ser denotada por $ B $ e o tamanho do grupo ser $ a $ . .

Eu preciso encontrar o número máximo de grupos com exatamente o mesmo conteúdo e de tamanho $ a $ que pode ser feito a partir dos elementos da $ B $ . Uma vez usado um elemento em um grupo, está esgotado. Um grupo pode ter mais de um elemento com o mesmo valor contanto que o elemento ainda esteja disponível na $ B $ .

Exemplo:

.
1. Se a matriz de entrada é $ \ {1, 2, 3, 1, 2, 3, 4 \} $ , e o tamanho do grupo é $ 3 $ O número máximo de grupos que podem ser feitos é $ 2 $ , que são $ \ {1, 2, 3 \} $ e $ \ {1, 2, 3 \} $ .
2. Se a matriz de entrada é $ \ {1, 3, 3, 3, 6, 3, 10 \} $ , e o tamanho do grupo é $ 4 $ O número máximo de grupos que podem ser feitos é $ 1 $ , que é $ \ {1, 3, 3, 3 \} $ .

O que eu tentei até agora, é enquadrar algumas equações (dadas abaixo), mas depois disso, estou lutando para chegar a um algoritmo para resolvê-los.

Deixe $ f_1 $ seja a frequência do elemento $ b_1 $ , $ F_2 $ Seja a frequência do elemento $ b_2 $ e assim por diante $ B_N $ , onde $ b_1 \ Dots b_n $ são elementos distintos da matriz $ B $ .

Agora eu preciso escolher $ n_1, n_2, \ Dots n_i $ tal que

.
1. $ n_1 + n_2 + \ Dots + n_i= A $
2. $ k \ cdot n_1 \ leq f_1 \ text {,} k \ cdot n_2 \ leq f_2 \ text {,} \ dots \ text {,} k \ cdot n_i \ leq f_i $
3. $ k $ é o número de grupos e precisamos maximizá-lo.

Comprimento da $ b $ pode ser tão grande quanto $ 10 ^ 5 $ e $ a $ também pode ser tão grande quanto $ 10 ^ 5 $ .

Por favor me ajude a encontrar uma abordagem gananciosa ou dinâmica ao problema.

Answer 1

a função $$ f: \ mathbb {n} \ rightarrow {0, 1}: f (k)= \ begin {casos} 1; & \ text {se houver uma solução de tamanho $ k $,} \\ 0; & \ text {de outro modo} \ fim {casos} $$ é monoton, já que se não houver solução de tamanho $ k $ então não há solução de tamanho $ k + 1 $ . Isso significa que podemos buscar binário o valor de $ k $ no intervalo $ [1, | B |] $ , e produza a maior $ k $ para o qual há uma solução de tamanho $ k $ . Assim, transformamos o problema em um problema de decisão com uma $ o (\ log | b |) $ fator no tempo de execução.

Para um valor fixo da $ k $ , uma solução gananciosa é suficiente. Se tivermos $ f_i $ cópias de algum elemento $ b_i $ , então cada conjunto pode conter no máximo < span class="contentor de matemática"> $ \ left \ lbloor \ frac {f_i} {k} \ direito \ rfloor $ deste elemento. Por isso temos uma solução de tamanho $ k $ se e somente se $$ \ Sum \ LIMITS_ {I= 1} ^ {n} \ lFloror \ frac {f_i} {k} \ rfloor \ geq a. $$

Como exercício, tente provar que a solução gananciosa é ideal. O tempo de execução pode ser limitado em $ o (| b | \ log | b |). $