有一个最优化问题问下大家， N 个数字放入 Y 个盒子里，求 Y 个盒子的最小方差
zhangqilin · 2018-11-14 13:29:44 +08:00 · 1186 次点击这是一个创建于 1982 天前的主题，其中的信息可能已经有所发展或是发生改变。
有谁可以指点一下吗？ 我的思路是 20 个数字放入 4 个盒子里 求最小方差 就把他们 20 个数字排序，尽量均匀的放在盒子里，这样数据离散程度就不会大了 但扩展到 N 个盒子里还是一点思路都没
 |
1
coderluan 2018-11-14 14:47:13 +08:00
N 个数排序，然后每 Y 个算方差就可以了。也可以优化一下，一组方差可以由上一组结果算出来，不用完全重算，具体咋的忘了，楼主有兴趣自己导一下就出来了。
PS：这题我见过，所以楼主去搜索肯定也能搜到。 PS2：4 和 20，N 和 Y，不是一样的吗，一个会一个不会，这就不是思路问题，是编程能力问题了。 |
 |
2
snail1988 2018-11-14 15:17:50 +08:00
貌似是 Bin packing problem 的变种，NP 问题，楼主想找最优方差貌似不容易，Google 学术查查论文吧
|
 |
3
takato 2018-11-14 15:44:16 +08:00
NP 问题 +1
1L 的贪心似乎不能得到正解。 |
 |
4
minami 2018-11-14 20:30:43 +08:00  1
遗传算法：
1、设定一个大小为 K 的盒子集合 S 2、随即从 20 个数字中选取 4 个数字，作为一个盒子，放入 S。重复 K 次 3、对 S 中的 K 个盒子，均计算对应的方差 4、对 S 中的 K 个盒子，执行突变操作，即随机替换盒子中的数字为剩余数字，可以得到一个新集合，记为 S ’ 5、计算 S ‘中每个盒子的方差 6、合并 S ’，到 S，保证 S 中只留下方差最小的 K 个盒子 7、返回 1，直到搜索得到足够小的方差或搜查次数足够大 |
Select Language