TA貢獻1877條經驗 獲得超1個贊
“笨”方法
(()=>{
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);
舉報