How to find the balance of numbers in an array?

Question

JavaScript

Hello everyone. Who knows what algorithm to apply or who can write a solution for balancing 2 arrays filled with numerical values ​​so that the difference between the sums between the arrays is minimal. There is a condition that the number of elements in the arrays differ by a maximum of 1.

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

Answer 1

The algorithm is like this. All elements are placed in one heap (array). Sort in descending order. Then we begin to scatter over two new arrays. In parallel, we calculate the sum of each array. Thus, we lay out first large numbers, then smaller and smaller. Each time we put a new number in the array where the sum is less.
Obviously, the smallest numbers will go last, which will diligently minimize the difference in the amounts. I cannot prove that in the end the difference will be minimal (laziness), but intuition tells me that this will be so.
UPD:

Such an exhaustive search algorithm

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

Answer 2

Very similar to the knapsack problem. You can start by saying that there are 2 backpacks. One is initially empty. And in the other - all the items. And there is a certain value of the mass (the sum of the weights of all objects) divided in half.
That's what you should strive for.

Answer 3

I am posting my version:

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

Answer 4

As I understand it, it's just a matter of going through all the possible options. Well, you can discard some search branches that are obviously worse than what has already been found.