Numero massimo di gruppi simili di una determinata dimensione che può essere fatta da un determinato array

Question

Mi viene data una serie di numeri, non necessariamente unici e la dimensione di un gruppo. Lasciare che l'array sia denotato da $ B $ e la dimensione del gruppo è $ a $ . .

Ho bisogno di trovare il numero massimo di gruppi con gli stessi contenuti e della dimensione $ a $ che può essere fatto dagli elementi di $ B $ . Una volta che un elemento viene utilizzato in un gruppo è esaurito. Un gruppo può avere più di un elemento con lo stesso valore finché l'elemento è ancora disponibile in $ B $ .

Esempio:

.
1. Se l'array di ingresso è $ \ {1, 2, 3, 1, 2, 3, 4 \} $ e la dimensione del gruppo è $ 3 $ Il numero massimo di gruppi che può essere effettuato è $ 2 $ , che sono $ \ {1, 2, 3 \} $ e $ \ {1, 2, 3 \} $ .
2. Se l'array di ingresso è $ \ {1, 3, 3, 3, 6, 3, 10 \} $ e la dimensione del gruppo è $ 4 $ Il numero massimo di gruppi che può essere effettuato è $ 1 $ , che è $ \ {1, 3, 3, 3 \} $ .

Quello che ho provato finora, è quello di inquadrare alcune equazioni (dato di seguito) ma dopo, sto lottando per inventare un algoritmo per risolverli.

Let $ f_1 $ essere la frequenza dell'elemento $ B_1 $ , $ f_2 $ Essere la frequenza dell'elemento $ B_2 $ e così via fino a $ B_N $ , dove $ B_1 \ Dots B_N $ sono elementi distinti dall'array $ B $ .

Ora ho bisogno di scegliere $ n_1, n_2, \ dots n_i $ tale da

.
1. $ n_1 + n_2 + \ dots + n_i= a $
2. $ k \ cdot n_1 \ leq f_1 \ text {,} k \ clot n_2 \ leq f_2 \ text {,} \ dots \ text {,} k \ cdot n_i \ Leq F_i $
3. $ k $ è il numero di gruppi e dobbiamo massimizzarlo.

lunghezza della classe $ B $ può essere grande come $ 10 ^ 5 $ e $ A $ può anche essere grande come $ 10 ^ 5 $ .

Aiutami a trovare un approccio avido o dinamico al problema.

Answer 1

La funzione $$ f: \ MathBB {N} \ RightArrow \ {0, 1 \}: f (k)= \ Begin {casi} 1; & \ testo {se c'è una soluzione di dimensioni $ k $,} \\ 0; & \ testo {altrimenti} \ end {casi} $$ È Monoton, poiché se non ci sono soluzione di dimensioni $ k $ allora non c'è soluzione di dimensioni $ k + 1 $ . Ciò significa che possiamo cercare binary il valore di $ k $ nell'intervallo $ [1, | b |] $ , e in uscita la più grande $ k $ per il quale è presente una soluzione di dimensioni $ k $ . In tal modo, abbiamo trasformato il problema in un problema di decisione con una $ o (\ log | B |) $ fattore nel tempo di esecuzione.

Per un valore fisso di $ k $ , è sufficiente una soluzione avida. Se abbiamo $ f_i $ copie di alcuni elementi $ B_i $ , quindi ogni set può contenere al massimo < Span Class="Math-Container"> $ \ sinistra \ lfloor \ frac {f_i} {k} \ destra \ rfloor $ di questo elemento. Quindi abbiamo una soluzione di dimensioni $ k $ se e solo se $$ \ Sum \ Limits_ {i= 1} ^ {n} \ sinistra \ lfloor \ frac {f_i} {k} \ destra \ rfloor \ geq a. $$

Come esercizio, prova a dimostrare che la soluzione avida è ottimale. Il tempo di esecuzione può essere delimitato in $ o (| b | \ log | b |). $