Описание здесь уже делал, повторю до кучи:
Задача относится к классу subset sum (сумма подмножества) и может быть решена динамическим программированием. Переформулируя - требуется собрать подмножество с суммой Sum/2
или максимально близкой.
Создаётся таблица длиной Sum/2
. Нулевой элемент заполнен ненулевым значением, означающим, что сумму 0
собрать можно, остальные пока нулями.
Затем проходим по всем элементам e
входного множества.
Для каждого проверяем ячейки таблицы в обратном порядке, чтобы исключить многократное использование элемента в наборе суммы.
Сумму i
c использованием элемента e собрать можно, если существует возможная сумма i-e
. Если сумма i
встречается впервые, то записываем e
в соответствующую ячейку на будущее. Тут же обновляем best
- дистанцию, насколько набранная сумма близка к целевой.
По окончанию работы разматываем цепочку элементов, составляющих лучшую сумму. В ячейке a[sum/2 - best]
ведь хранится слагаемое (e
), с помощью которого получена эта сумма. В следующей ячейке, на которую указывает e
(a[i-e]
в основном алгоритме) - следующее слагаемое и т.д. Таким образом получается одно подмножество, а не вошедшие в него элементы образуют второе.
function halfsum(arr) {
let hsum = Math.floor(arr.reduce((a, b) => a + b) / 2)
let a = [-1]
for (var i=0;i<hsum;i++) {
a.push(0)}
let best = hsum + 1
arr.forEach(e => {
for (var i=hsum;i>=e; i--){
if ((a[i - e] !=0) & (a[i] == 0)) {
a[i] = e;
if (hsum - i < best) {
best = hsum - i;
}
}
}
})
let id = hsum - best
let b = []
while (id > 0) {
b.push(a[id]);
id = id - a[id];
}
return b;
}
console.log(halfsum([3,11,29,51,13,7]));