js数组拆分问题

Question

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

Answer 1

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

Answer 2

“笨”方法

(()=>{

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

    

    // 笨方法，穷举，不过在穷举时淘汰了一些值。全穷举需要跑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, []);

    }

}

)();

补充一个背包的解法，支持一下

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