有一个最优化问题问下大家， N 个数字放入 Y 个盒子里，求 Y 个盒子的最小方差

[zhangqilin]

有谁可以指点一下吗？ 我的思路是 20 个数字放入 4 个盒子里 求最小方差 就把他们 20 个数字排序，尽量均匀的放在盒子里，这样数据离散程度就不会大了 但扩展到 N 个盒子里还是一点思路都没

[coderluan]

N 个数排序，然后每 Y 个算方差就可以了。也可以优化一下，一组方差可以由上一组结果算出来，不用完全重算，具体咋的忘了，楼主有兴趣自己导一下就出来了。

PS：这题我见过，所以楼主去搜索肯定也能搜到。
PS2：4 和 20，N 和 Y，不是一样的吗，一个会一个不会，这就不是思路问题，是编程能力问题了。

[snail1988]

貌似是 Bin packing problem 的变种，NP 问题，楼主想找最优方差貌似不容易，Google 学术查查论文吧

[takato]

NP 问题 +1
1L 的贪心似乎不能得到正解。

[minami]

遗传算法：
1、设定一个大小为 K 的盒子集合 S
2、随即从 20 个数字中选取 4 个数字，作为一个盒子，放入 S。重复 K 次
3、对 S 中的 K 个盒子，均计算对应的方差
4、对 S 中的 K 个盒子，执行突变操作，即随机替换盒子中的数字为剩余数字，可以得到一个新集合，记为 S ’
5、计算 S ‘中每个盒子的方差
6、合并 S ’，到 S，保证 S 中只留下方差最小的 K 个盒子
7、返回 1，直到搜索得到足够小的方差或搜查次数足够大