首頁猿問 js數(shù)組拆分問題

js數(shù)組拆分問題

JavaScript

繁星coding 2019-03-14 10:14:03

let arrs=[102,233,45,350,130,220,195,240]我想讓arrs拆分出兩組,但是想讓拆分出的兩組數(shù)組之和的值盡可能相近,差值越小越好,我自己想法是重新sort,按照從小到大,然后判斷下標(biāo)分出兩組,奇數(shù)一組,偶數(shù)一組,或者前兩個(gè)最小值和后兩個(gè)最大值為一組,中間四個(gè)為一組.大家有沒有更好精確的方法,能取出最小差值.

查看完整描述

3 回答

隔江千里

TA貢獻(xiàn)1906條經(jīng)驗(yàn) 獲得超10個(gè)贊

把數(shù)組中所有元素求和，除以二
用這個(gè)值解一個(gè)背包問題子集和問題(Subset sum problem)

反對(duì) 回復(fù) 2019-04-09

冉冉說

TA貢獻(xiàn)1877條經(jīng)驗(yàn) 獲得超1個(gè)贊

“笨”方法

(()=>{

console.clear();

let arrs = [102, 233, 45, 350, 130, 220, 195, 240].sort((a,b)=>a - b);

console.log(arrs, arrs.reduce((a,b)=>a + b, 0));

// 笨方法，窮舉，不過在窮舉時(shí)淘汰了一些值。全窮舉需要跑256次，加上閥值了需要196次

var divideRes = divide(arrs);

console.log(divideRes, divideRes.reduce((a,b)=>a + b, 0));

function divide(array) {

var total = array.reduce((a,b)=>a + b, 0);

var half = total / 2;

var min = total;

var result = [];

var counter = 0;

for (let comb of fullCombination(array, half)) {

var sum = comb.reduce((a,b)=>a + b, 0);

if (sum > half && sum < min) {

min = sum;

result = comb.slice();

}

counter += 1;

}

// console.log(counter);

return result;

}

function *fullCombination(array, threshold) {

function *gen(array, prefix) {

if (array.length === 0) {

yield prefix;

} else {

if (prefix.reduce((a,b)=>a + b, 0) < threshold) {

yield*gen(array.slice(1), [...prefix, array[0]]);

yield*gen(array.slice(1), [...prefix]);

}

yield*gen(array, []);

}

)();

補(bǔ)充一個(gè)背包的解法，支持一下

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);

反對(duì) 回復(fù) 2019-04-09