将n个球放入等大盒子匹配全局颜色分布的最优K值推导问题

前提定义 #

• 设总球数为n，颜色集合为C，对任意颜色s ∈ C，全局中颜色为s的球数量为n_s，显然满足 ∑_{s∈C} n_s = n
• 全局颜色分布中颜色s的占比为 p_s = n_s / n
• 要求每个大小为K的盒子中，颜色s的数量为 p_s * K，该值必须为正整数（不存在被分割的球）
• 总球数必须能被K整除，即 n mod K = 0，保证所有球刚好装完

推导过程 #

1. 首先设 g = gcd(n_s | s ∈ C)，即所有颜色球数的最大公约数。可将每个n_s拆分为 n_s = g * k_s，此时 gcd(k_s | s ∈ C) = 1
2. 总球数可改写为 n = ∑ n_s = g * ∑ k_s = g * t，其中 t = ∑_{s∈C} k_s
3. 每个盒子中颜色s的数量要求为整数，即：

   p_s * K = (n_s / n) * K = (g k_s / g t) * K = (k_s * K) / t ∈ N+ （对所有s∈C）
   

4. 由于gcd(k_s | s∈C) = 1，要让所有k_s * K都能被t整除，必须满足 t | K（t是K的约数）
5. 结合总球数整除要求 K | n = g * t，设K = t * x（x为正整数），代入整除条件可得：

   t * x | g * t → x | g
   

最优K的取值 #

根据不同最优目标可得到对应取值：

• 若目标为最小化盒子数量（用最少的盒子完成划分）：取x的最大值g，此时 K = t * g = n，对应仅用1个盒子的平凡解
• 若目标为最大化盒子数量（尽可能拆分更多满足条件的盒子，也是该问题默认的非平凡最优目标）：取x的最小值1，此时 K = t = ∑_{s∈C} (n_s / g)，其中g为所有颜色球数的最大公约数

示例验证 #

举个简单例子验证：总共有12个球，其中红球6个，蓝球4个，绿球2个

• n_红=6，n_蓝=4，n_绿=2，g = gcd(6,4,2) = 2
• k_红=6/2=3，k_蓝=4/2=2，k_绿=2/2=1，t=3+2+1=6
• 可行K为t的倍数且整除12，即6和12
• 最大化盒子数量的最优K为6：每个盒子3红2蓝1绿，总共2个盒子，完全符合分布要求

内容的提问来源于stack exchange，提问作者sergio09