js数组拆分问题

Question

let arrs=[102,233,45,350,130,220,195,240]

我想让arrs拆分出两组,但是想让拆分出的两组数组之和的值尽可能相近,差值越小越好,我自己想法是重新sort,按照从小到大,然后判断下标分出两组,奇数一组,偶数一组,或者前两个最小值和后两个最大值为一组,中间四个为一组.
大家有没有更好精确的方法,能取出最小差值.

Answer 1

把数组中所有元素求和，除以二用这个值解一个背包问题子集和问题(Subset sum problem)

Answer 2

“笨”方法(()=>{&nbsp; &nbsp; console.clear();&nbsp; &nbsp; let arrs = [102, 233, 45, 350, 130, 220, 195, 240].sort((a,b)=>a - b);&nbsp; &nbsp; console.log(arrs, arrs.reduce((a,b)=>a + b, 0));&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; // 笨方法，穷举，不过在穷举时淘汰了一些值。全穷举需要跑256次，加上阀值了需要196次&nbsp; &nbsp; var divideRes = divide(arrs);&nbsp; &nbsp; console.log(divideRes, divideRes.reduce((a,b)=>a + b, 0));&nbsp; &nbsp; function divide(array) {&nbsp; &nbsp; &nbsp; &nbsp; var total = array.reduce((a,b)=>a + b, 0);&nbsp; &nbsp; &nbsp; &nbsp; var half = total / 2;&nbsp; &nbsp; &nbsp; &nbsp; var min = total;&nbsp; &nbsp; &nbsp; &nbsp; var result = [];&nbsp; &nbsp; &nbsp; &nbsp; var counter = 0;&nbsp; &nbsp; &nbsp; &nbsp; for (let comb of fullCombination(array, half)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; var sum = comb.reduce((a,b)=>a + b, 0);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (sum > half && sum < min) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; min = sum;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result = comb.slice();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; counter += 1;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; // console.log(counter);&nbsp; &nbsp; &nbsp; &nbsp; return result;&nbsp; &nbsp; }&nbsp; &nbsp; function *fullCombination(array, threshold) {&nbsp; &nbsp; &nbsp; &nbsp; function *gen(array, prefix) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (array.length === 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield prefix;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (prefix.reduce((a,b)=>a + b, 0) < threshold) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield*gen(array.slice(1), [...prefix, array[0]]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; yield*gen(array.slice(1), [...prefix]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; yield*gen(array, []);&nbsp; &nbsp; }})();补充一个背包的解法，支持一下var res = knapsack([102, 233, 45, 350, 130, 220, 195, 240].map(i=>({w: i,b: i})), ([102, 233, 45, 350, 130, 220, 195, 240].reduce((a,b)=>a + b, 0) / 2) << 0);