js数组拆分问题

Question

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

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

Answer 1

嗨，可以这么想：

两个集合和差值越小，说明两者越接近总和的一半。

问题即可转化为 0-1 背包问题，可求和小的子集合也可求和大的子集合，最后回溯打印路径。

如求和较小的，状态转移方程为：

f[i][v] = max( f[i-1][v], f[i-1][v-nums[i]] + nums[i] )

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

const nums = [0, ...arrs]
const halfSum = Math.round(nums.reduce((sum, x) => x + sum, 0) / 2)
const dp = nums.map(() => new Array(halfSum + 1).fill(0))

for (let i = 1; i < nums.length; i++) {
  for (let v = 1; v <= halfSum; v++) {
    dp[i][v] = v < nums[i]
      ? dp[i-1][v]
      : Math.max(dp[i-1][v], dp[i-1][v - nums[i]] + nums[i])
  }
}

// 回溯路径
const subsetA = []
const subsetB = []

for (let row = dp.length - 1, col = dp[0].length - 1; row > 0; row--) {
  if (dp[row][col] === dp[row-1][col]) {
    subsetA.unshift(nums[row])
  } else {
    subsetB.unshift(nums[row])
    col = dp[row][col] - nums[row]
  }
}

console.log(subsetA, subsetA.reduce((sum, x) => sum + x, 0))
console.log(subsetB, subsetB.reduce((sum, x) => sum + x, 0))

当然，如果这么用数组 dp 的话就限制了和最大值要在 2^32 以内，可以根据数字最小值压缩 dp 数组。

Answer 2

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

Answer 3

“笨”方法

(()=>{
    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);

Answer 4

    let arrs=[102,233,45,350,130,220,195,240];
    let temp = [...arrs];
    temp.sort((a,b)=>a-b);
    let avg = parseInt(temp.reduce(((a,b)=>a+b),0)/2);
    
    let sum = 0;
    let indx = 0;
    for(let i=0;i<temp.length;i++){
        sum+=temp[i];
        if(sum > avg){
            indx = i;
            break;
        }
    }
    //最后根据indx拆分 如果要保留原数组的数据顺序，则挨个找到然后踢出来 -- 有点low
    let left = temp.splice(0,indx);
    let right = temp;

Answer 5

此题无解，再寽寽你的需求吧。