js从数组中取出来数组的一半让他们的和最接近整个数组的和的一半

zhengwenlong
  • 12

var arr=[150,120,190,200,300,160,110,240]

上面数组的和是1470 ,length是8

怎么从arr中选出来4个数字,让他们的和最接近1470/2=735呢

———————————————————————更新—————————————————————————

也是自己工作闲暇之余瞎琢磨

问题可扩展为:

一个数组arr,里面全部是数字,有可能有相等的数据
假设要把这个数组分为n个数组,且每个数组之和都尽可能接近于 arr的总和/n
想了很久也没有一个很好的结果,各位道友可以分享一下想法

回复
阅读 4.6k
4 个回答

上面的答案是错误的。然后来说一下我的思路。
这道题只能遍历计算所有的可能性,但是有优化的地方。
首先要对数据排序,优化点在最后一个数据选择的地方。
记当前最优结果的值为S, 目标值为T
选好前N-1个数据后,
判断下前N-1的数据的和加上最后一个数据的和,记为S1
如果S1比T要小, 且T-S1 > abs(T-S), 就放弃该组合
判断下前N-1的数据的和加上N+1数据的和,记为S2
如果S2比T要大, 且S2-T > abs(T-S), 放弃该组合
剩下的如何选择第N个数据,就用2分法

稍后给出伪代码

这个分组问题转化成背包问题恐怕并不合适,因为

  1. 本题固定了每组的元素个数,而背包问题一般没有这个限制。

  2. 背包问题要求数组是非负的,而本题并没有这个限制。

把此题看成线性规划似乎更恰当。比如数组是$\{-1, 3, 0, 4\}$(和为6),分成两组,用线性规划的语言描述就是:

$$\array{\text{minimize:} & -x_1+3x_2+4x_3 \\ \text{subject to:} & -x_1+3x_2+4x_3 \geq 6/2 \\ & x_1 + x_2 + x_3 + x_4 = 4/2 \\ & x_i \in \{0, 1\}}$$

求解线性规划问题一般都有现成算法库可用。

推广到多个分组的情况,比如把n个数分成k组(n是k的倍数),可以重复使用线性规划,每次选出一个分组(组和>=sum/k,组长度=n/k)。当然这是一种简单的贪心推广,不见得给出最优解。

下面用Mathematica实现中,pickgroup是用线性规划算法(内置)给出从组lst中选出的长度为n/k的子组。subgroups递归调用自己,达到重复使用线性规划的目的。

clipboard.png

测试将40个-50到50间的随机数分为4组:

clipboard.png

DancingSean
  • -2
新手上路,请多包涵

相当于找4个数,然后让他们的和最接近 一个值;
1:把定值除以4;得均值;
2:所有数字与均值比较,进行排序;
3:找绝对值最小的,

应该是这个思路

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
宣传栏