Nombre maximum de groupes similaires d'une taille donnée pouvant être fabriquée à partir d'un tableau donné

Question

J'ai donné un tableau de chiffres, pas nécessairement unique et la taille d'un groupe. Laissez le tableau être noté par $ B $ et la taille du groupe être $ a $ .

J'ai besoin de trouver le nombre maximum de groupes avec exactement le même contenu et de taille $ A $ qui peut être fabriqué à partir des éléments de $ B $ . Une fois qu'un élément est utilisé dans un groupe, il est épuisé. Un groupe peut avoir plus d'un élément de la même valeur tant que l'élément est toujours disponible dans $ B $

.

.

Exemple:

1. Si la matrice d'entrée est $ \ {1, 2, 3, 1, 2, 3, 4 \} $ et la taille du groupe est $ 3 $ Le nombre maximum de groupes pouvant être effectué est 2 $ , qui sont $ \ {1, 2, 3 \} $ et $ \ {1, 2, 3 \} $ .
.
2. Si la matrice d'entrée est $ \ {1, 3, 3, 3, 6, 3, 10 \} $ et la taille du groupe est 4 $ Le nombre maximum de groupes pouvant être effectué est $ 1 $ , qui est $ \ {1, 3, 3, 3 \ \ \ \} $ .

Ce que j'ai essayé jusqu'à présent, est d'encadrer certaines équations (données ci-dessous), mais après cela, je me lance de trouver un algorithme pour les résoudre.

let $ f_1 $ est la fréquence de l'élément $ b_1 $ , $ f_2 $ Soyez la fréquence de l'élément $ b_2 $ et ainsi de suite till $ B_n $ , où $ b_1 \ dots b_n $ sont des éléments distincts de la matrice $ B $ .

Maintenant, je dois choisir $ n_1, n_2, \ dots n_i $ tel que

1. $ n_1 + n_2 + \ dots + n_i= A $
2. $ k \ cdot n_1 \ leq f_1 \ texte {,} k \ cdot n_2 \ leq f_2 \ text {,} \ dots \ text {,} k \ CDOT N_I \ LEQ F_I $
3. $ k $ est le nombre de groupes et nous devons le maximiser.

longueur de $ B $ peut être aussi grand que 10 $ ^ 5 $ et $ A $ peut également être aussi grand que 10 $ ^ 5 $ .

.

Aidez-moi à trouver une approche gourmande ou dynamique du problème.

Answer 1

la fonction $$ f: \ mathbb {n} \ researrow \ {0, 1 \}: f (k)= \ commencer {cas} 1; & \ Text {S'il y a une solution de taille $ K $,} \\ 0; & \ text {sinon} \ fin {cas} $$ est monoton, car s'il n'y a pas de solution de taille $ k $ il n'y a pas de solution de taille $ k + 1 $ . Cela signifie que nous pouvons rechercher binaires la valeur de $ k $ dans l'intervalle $ [1, | b |] $ , et Sortie le plus grand $ K $ pour lequel il existe une solution de taille $ K $ . Ainsi, nous avons transformé le problème dans un problème de décision avec un $ o (\ log | b |) $ facteur dans la période d'exécution.

pour une valeur fixe de $ K $ , une solution gourmande suffit. Si nous avons $ f_i $ copies de certains éléments $ b_i $ , alors chaque ensemble peut contenir au plus < Span Classe="Math-Conteneur"> $ \ Gauche \ lfloor \ frac {f_i} {k} \ droite \ rfloor $ de cet élément. Nous avons donc une solution de taille $ k $ si et seulement si $$ \ Somme \ limites_ {i= 1} ^ {n} \ lft \ lfloor \ frac {f_i} {k} \ droite \ rfloor \ geq a. $$

En tant qu'exercice, essayez de prouver que la solution gourmande est optimale. Le temps d'exécution peut être délimité dans $ o (| b | \ log | b |). $