“笨”方法

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

嗨，可以這么想：

兩個集合和差值越小，說明兩者越接近總和的一半。

問題即可轉化為 0-1 背包問題，可求和小的子集合也可求和大的子集合，最后回溯打印路徑。

如求和較小的，狀態(tài)轉移方程為：

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

當然，如果這么用數(shù)組 dp 的話就限制了和最大值要在 2^32 以內(nèi)，可以根據(jù)數(shù)字最小值壓縮 dp 數(shù)組。

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

此題無解，再寽寽你的需求吧。

    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;
        }
    }
    //最后根據(jù)indx拆分 如果要保留原數(shù)組的數(shù)據(jù)順序，則挨個找到然后踢出來 -- 有點low
    let left = temp.splice(0,indx);
    let right = temp;