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

JavaScript04

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

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

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

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

把此题看成线性规划似乎更恰当。比如数组是{−1,3,0,4}（和为6），分成两组，用线性规划的语言描述就是：

minimize:subject to:−x1+3x2+4x3−x1+3x2+4x3≥6/2x1+x2+x3+x4=4/2xi∈{0,1}

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

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

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

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

一、概述

join( ) ————————数组转字符串

split( ) ———————–字符串转数组

push( ) ———————-将数据添加到数组尾部

pop( ) ———————–数组末尾移除最后一项

shift( ) ———————–删除原数组第一项

unshift( ) ——————–将数据添加到数组头部

sort( ) ————————按升序排列数组项

reverse( ) ——————–反转数组项的顺序

concat( ) ——————–多个数组合并，原数组不变

slice( ) ———————–返回开始下标到结束下标之间的项组成的新数组，原数组不变

splice( ) ———————-从数组中添加/删除项目，然后返回被删除的项目，改变原数组

二、定义和用法

1、join()

2、concat()

3、pop()

4、shift()

5、push()

6、unshift()

7、reverse()

8、slice()

9、splice()

10、toString()

11、sort()

12、includes()

13、forEach()

14、map()