Maximale Anzahl ähnlicher Gruppen einer bestimmten Größe, die aus einem bestimmten Array hergestellt werden kann

Question

Ich habe ein Array von Zahlen, nicht unbedingt einzigartig, und die Größe einer Gruppe erhalten. Lassen Sie das Array von $ B $ bezeichnet, und die Größe der Gruppe ist $ A $ .

Ich muss die maximale Anzahl von Gruppen mit den gleichen Inhalten und der Größe $ A $ finden, die aus den Elementen der $ B $ . Sobald ein Element in einer Gruppe verwendet wird, ist es erschöpft. Eine Gruppe kann mehr als ein Element mit demselben Wert haben, solange das Element in $ B $ verfügbar ist.

Beispiel:

.
1. Wenn das Eingaberarray $ \ {1, 2, 3, 1, 2, 3, 4 \} $ ist, und die Gruppengröße ist $ 3 $ Die maximale Anzahl von Gruppen, die gemacht werden können, ist $ 2 $ , die $ \ {1, 2, 3 \} $ und $ \ {1, 2, 3 \} $ .
2. Wenn das Eingaberarray $ \ {1, 3, 3, 3, 6, 3, 10 \} $ ist, und die Gruppengröße ist $ 4 $ Die maximale Anzahl von Gruppen, die gemacht werden können, ist $ 1 $ , was $ \ {1, 3, 3, 3 \} $ .

was ich bisher versucht habe, ist, einige Gleichungen zu rahmen (unten), aber danach kämpfte ich, einen Algorithmus zu finden, um sie zu lösen.

$ F_1 $ Seien Sie die Frequenz des Elements $ B_1 $ , $ F_2 $ Seien Sie die Frequenz des Elements $ B_2 $ und so weiter bis $ B_N $ , wobei $ B_1 \ DOTS B_N $ verschiedene Elemente aus dem Array $ B $ .

Jetzt muss ich wählen $ n_1, n_2, \ dots n_i $ so, dass

.
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 $ ist die Anzahl der Gruppen und müssen es maximieren.

Länge von $ B $ kann so groß sein wie $ 10 ^ 5 $ und $ A $ kann ebenfalls so groß wie $ 10 ^ 5 $ sein.

Bitte helfen Sie mir, einen gierigen oder dynamischen Ansatz für das Problem zu finden.

Answer 1

die Funktion $$ F: \ mathbb {n} \ Rightarrow \ {0, 1 \}: f (k)= \ Beginnen Sie {Hüllen} 1; & \ Text {Wenn es eine Lösung von Größe $ k $ gibt, \\ \\ \\ 0; & \ text {sonst} \ ENDE {Hüllen} $$ ist Monoton, da, wenn es keine Lösung der Größe $ K $ gibt, dann gibt es keine Lösung der Größe $ k + 1 $ . Das heißt, wir können den Wert von $ K $ im Intervall $ [1, | B |] $ , und geben Sie den größten $ K $ , für den eine Lösung von Größe $ K $ besteht. Dabei haben wir das Problem in ein Entscheidungsproblem mit einem $ O (\ \ @ log | b |) $ Faktor in der Laufzeit.

für einen festen Wert von $ k $ , reicht eine gierige Lösung aus. Wenn wir $ F_I $ Kopien von einigen Elementen $ B_i $ , dann kann jedes Set höchstens < Span-Klasse="Math-Container"> $ \ link \ lfloor \ frac {f_i} {k} \ rechts \ rfloor $ dieses Elements. Wir haben also eine Lösung von Größe $ K $ Wenn und nur wenn $$ \ SUM \ Limits_ {I= 1 \ limits_ {n} \ link \ lfloor \ frac {f_i} {k} \ rechts \ rfloor \ geq a. $$

Versuchen Sie als Übung, zu beweisen, dass die gierige Lösung optimal ist. Die Laufzeit kann in $ O (| B | \ Log | B |) begrenzt werden. $