Как из массива рандомных натуральных чисел вычислить две равные суммы?

Question

[wvw1]

Привет, попалась мне такая интересная задачка:

Вы собираетесь установить рекламный щит и хотите, чтобы он имел наибольшую высоту. Рекламный щит опирается на две стальные опоры, по одной с каждой стороны. Опоры должны быть одинаковой высоты.

У вас есть коллекция стержней, которые могут быть сварены вместе. Например, если у вас есть стержни длиной 1, 2 и 3, Вы можете сварить их вместе, чтобы сделать опору длиной 6.

Верните максимально возможную высоту установки рекламного щита. Если вы не можете установить рекламный щит, верните 0.

На входе: rods - массив с длинами имеющихся стержней

На выходе: максимальная высота установки рекламного щита, либо 0, если невозможно получить опоры одинаковой высоты

Пример:
1.

const rods = [1,2,3,6]
getHeight( rods ) // 6

из данного набора стержней можем получить две опоры по 6: сварив стержни длиной 1,2,3 и использовав имеющийся стержень длиной 6

2.

const rods = [1,2]
getHeight( rods ) // 0

из данного набора стержней невозможно получить две опоры одинаковой длины

Задачка была взята с аттестационных тестов отсюда https://geecko.ru/ (поиск работы в IT)

Answer 1

[Wataru]

Это задача - вариант Subset sum problem.

Она NP-полная - тут нет быстрых и простых решений. В общем случае, возможно только решение полным перебором за N*3^N. Что-то вроде того, что предложил Alexandroppolus, только там вообще не рассматривается случай, что текущее число просто пропускается. Еще можно делать это же без рекурсии на основе битовых масок.

Если есть какие-то дополнительные условия (например, все числа очень маленькие), то может более быстрым быть решение на основе динамического программирования, как в задаче о рюкзаке.

Comments

[Alexandroppolus]

только там вообще не рассматривается случай, что текущее число просто пропускается.

Да, этот кейс я профакапил. Поправил

Answer 2

[Alexandroppolus]

Навскидку видится что-то такое:

function getHeightRec(arr, height1, height2, max) {
    if (arr.length === 0) {
        return max;
    }
    let result;
    const lastItem = arr.pop();
    if (height1 === height2) {
        result = Math.max(
            getHeightRec(arr, height1, height2, height2),
            getHeightRec(arr, height1 + lastItem, height2, height2)
        );
    } else {
        result = Math.max(
            getHeightRec(arr, height1, height2, max),
            getHeightRec(arr, height1 + lastItem, height2, max),
            getHeightRec(arr, height1, height2 + lastItem, max)
        );
    }
    arr.push(lastItem);
    return result;
}

function getHeight(arr) {
    return getHeightRec(arr, 0, 0, 0);
}

не дебажил