2 抽象
将一个包含m个整数的数组分成n个数组,每个数组的和尽量接近
3 思路
这个问题是典型的动态规划的问题,理论上是无法找到最优解的,但是本次只是为了解决实际生产中的问题,而不是要AC,所以我们只需要找到一个相对合理的算法...我们举一个栗子:
数组为:500, 18, 28, 2, 27, 35, 22, 10, 6, 5, 3, 2, 1;分为4组
排序为:500, 35, 28, 27, 22, 18, 10, 6, 5..., 3, 2, 2, 1
计算平均值 avg = 164.75
遍历数组:
第一轮:500 > avg,取出500单独作为一组;剩余数组为 35, 28, 27, 22, 18, 10, 6, 5, 3...18,于是取出18加入到第二组,结束第二轮,剩余数组为 28, 27, 22, 10, 6, 5, 3, 2, 2, 1
第三轮:28 < avg, 取出28放入到第三组;
delta=53-28=25...= delta-3 = 0;于是将22和3加入到第三组,结束第三轮,属于数组为 27, 10, 6, 5, 2, 2, 1
第四轮:直接返回剩下数加入到一个组作为第四组
结果:
arr 0 is :