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

Question

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

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

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

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

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

问题可扩展为：

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

Answer 1

https://www.zhihu.com/questio...

Answer 2

上面的答案是错误的。然后来说一下我的思路。
这道题只能遍历计算所有的可能性，但是有优化的地方。
首先要对数据排序，优化点在最后一个数据选择的地方。
记当前最优结果的值为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分法

稍后给出伪代码

Answer 3

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

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递归调用自己，达到重复使用线性规划的目的。

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

Answer 4

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

应该是这个思路