Алгоритм для решения задачи о разбиении масива на 2 два одинаковых или максимально равных по суме

Question

function algoritm(arr) {
  try {
    if (arr.length == 0) {
      console.log('')
    }
    arr.sort((a, b) => b - a)
    let sum_arr1 = 0
    let sum_arr2 = 0;
    let arr_sum = arr.reduce((a, b) => a + b) / 2
    let arr1 = []
    let arr2 = []

    arr.forEach(element => {
      if (sum_arr1 <= sum_arr2 || sum_arr2 >= arr_sum || sum_arr1) {
        arr1.push(element)
        sum_arr1 += element
      } else {
        arr2.push(element)
        sum_arr2 += element
      }
    });

    let response = {
      s1: arr1,
      s2: arr2
    }
    return JSON.stringify(response)
  } catch {
    console.log('Invalid data')
  }

}

console.log(algoritm([4, 5, 6, 7, 8]));

Answer 1

Приведённый под пытается решить задачу жадным методом, однако в общем случае это не обеспечивает правильного решения.

Задача относится к классу subset sum (сумма подмножества) и может быть решена динамическим программированием. Переформулируя - требуется собрать подмножество с суммой Sum/2 или максимально близкой.

Создаётся таблица длиной Sum/2. Нулевой элемент заполнен ненулевым значением, означающим, что сумму 0 собрать можно, остальные пока нулями.

Затем проходим по всем элементам l входного множества. В обратном порядке, чтобы исключить многократное использование каждого элемента в наборе суммы.

Сумму i c использованием элемента l собрать можно, если существует возможная сумма i-l. Если сумма i встречается впервые, то записываем l в соответствующую ячейку на будущее. Тут же обновляем best - дистанцию, насколько набранная сумма близка к целевой.

По окончанию работы разматываем цепочку элементов, составляющих лучшую сумму. В ячейке a[sum/2 - best] ведь хранится слагаемое (l), с помощью которого получена эта сумма. В следующей ячейке, на которую указывает l (a[i-l] в основном алгоритме) - следующее слагаемое и т.д. Это получается одно подмножество, а не вошедшие в него элементы образуют второе.

Пример на Python:

def halfsum(lst):
    halfs = sum(lst) // 2
    a = [0] * (halfs + 1)
    a[0] = -1
    best = halfs + 1

    for l in lst:
        for i in range(halfs, l-1, -1):
            if (a[i - l] !=0) and a[i] == 0:
                a[i] = l
                best = min(halfs - i, best)

    id = halfs - best
    b = []
    while (id > 0):
        b.append(a[id])
        id = id - a[id]
    return b

print(halfsum([3,11,29,53,13,7]))

>>[53, 3]

БЛОГ НА HUSL

Алгоритм для решения задачи о разбиении масива на 2 два одинаковых или максимально равных по суме

Ответы (1 шт):