const arr1 = [10, 300, 25, 75];
const arr2 = [50, 125, 500, 10];
balance(arr1, arr2);
// На выходе получаем
// [500, 25, 10, 10] => 545
// [300, 125, 75, 50] => 550
function balance(arr1, arr2) {
let all = arr1.concat(arr2);
//all.sort((a, b) => a - b); //Для исключения одинаковых.
let all_sum = all.reduce((a,b)=>a+b,0);
let len = all.length;
let cnt = Math.floor(len * 0.5);
let arr_result = new Array(cnt); //Массив выбранных индексов
let idx_begin = 0; //Начальная глубина перебора (индекс в arr_result)
let sum_begin = 0; //Начальная сумма частично перебранных элементов
if (cnt === len * 0.5) { //Оптимизация
arr_result[0] = 0;
idx_begin = 1;
sum_begin = all[0];
}
let min_diff = all_sum; //Присваиваем какое-то заведомо большое число.
let arr_answer; //Итоговый ответ
//Проверяем следующий уровень глубины
//idx - глубина, sum - сумма всех элементов до этого
function check(idx, sum) {
if (idx === cnt) { //Конец перебора. Проверяем, подходит ли.
let diff = Math.abs((all_sum - sum) - sum);
if (diff < min_diff) { //Подходит
min_diff = diff; //Запоминаем новый лучший результат.
arr_answer = arr_result.slice(); //Копируем
}
return;
}
//Иначе идем дальше вглубь на следующий уровень.
let start = idx === 0 ? 0 : arr_result[idx-1] + 1;
let max = len - cnt + idx;
for(let i = start; i <= max; i++){ //Ключевой цикл алгоритма
//if (i > start && all[i] === all[i-1]) continue;
arr_result[idx] = i;
check(idx+1, sum+all[i]); //Рекурсия
}
}
check(idx_begin,sum_begin); //Начать перебор. Поехали!
arr1 = [];
arr2 = [];
//Фасуем полученный ответ по массивам уже в виде значений.
let j = 0;
all.forEach((e,i)=>{
if (i === arr_answer[j]) {
arr1.push(e);
j++;
} else arr2.push(e);
});
return {
arr1: arr1,
arr2: arr2,
sum1: arr1.reduce((a,b)=>a+b,0),
sum2: arr2.reduce((a,b)=>a+b,0),
}
}
var arr1 = [10, 300, 25, 75];
var arr2 = [50, 125, 500, 10];
balance(arr1, arr2);
class Player{
constructor(elo){
this.elo = elo;
}
}
let reducer = (accumulator, value) => accumulator + value.elo;
let players = [
new Player(3000),
new Player(700),
new Player(750),
new Player(1250),
new Player(1000),
new Player(1200),
new Player(1350),
new Player(1400),
new Player(1500),
new Player(745)
];
let combinations = (function () {
function combinations(arr, k, start, idx, current, callback) {
if (idx === k)
return callback(current);
for(let i = start; i < arr.length; i++) {
current[idx] = arr[i];
combinations(arr, k, i + 1, idx + 1, current, callback);
}
}
return function (arr, k, callback) {
combinations(arr, k, 0, 0, [], callback);
};
}());
let minimal = [];
combinations(players, players.length / 2, (combo) => {
let t1 = [...combo],
t2 = players.filter(p => t1.indexOf(p) < 0),
w1 = t1.reduce(reducer, 0),
w2 = t2.reduce(reducer, 0),
diff = Math.abs(w1 - w2);
if( ! minimal.length)
minimal = [t1, t2, diff];
if(minimal[2] > diff)
minimal = [t1, t2, diff];
});
console.log(minimal);
Средний
