# js数组拆分问题

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

5 个回答
✓ 已被采纳

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

“笨”方法

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

###### 你尚未登录，登录后可以
• 和开发者交流问题的细节
• 关注并接收问题和回答的更新提醒
• 参与内容的编辑和改进，让解决方法与时俱进