Разбиение последовательности на две, суммы которых равны или приближенные

157
16 июня 2022, 22:20

Есть последовательность, например:

{"set": [3, 3, 3, 7, 5]}

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

{"set_1": [3, 3, 5], "set_2": [3, 7]}

Сначала думал найти сумму всех элементов, разделить ее пополам и через цикл отнимать. Но это не то. Последовательность может быть любой длины.

Подскажите идеи, какой алгоритм решения?

Answer 1

Описание здесь уже делал, повторю до кучи:

Задача относится к классу 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]));

Answer 2

Функция getArrays() принимает в качетсве параметра - исходный массив, и возвращает массив, который состоит из двух массивов, которые и нужно было получить в результате этой задачи

Вот вопрос на stackoverflow, который я взял за основу, и переписал на js: Разделение массива по равенству двух частей В коде я описал комментариями логику работы.

//подсчет суммы массива
const getSumOfArray = array => array.reduce((a, c) => a + c)
//сортировка по убыванию(деструктуризация массива нужна для того чтобы не менялся исходный массив, который будет передан в эту функцию)
const descendingSort = array => [...array].sort((a, b) => b - a)
function getArrays(innerArray) {
    //сумма исходного массива
    const sumOfInnerArray = getSumOfArray(innerArray)
    //половина суммы исходного массива
    const halfOfSum = sumOfInnerArray / 2
    //сортировка по убыванию
    const sortedArray = descendingSort(innerArray)
    //результирующие массивы:
    const resultingArray1 = []
    const resultingArray2 = []
    //сумма результирующих массивов:
    let sumOfResultingArray1 = 0
    let sumOfResultingArray2 = 0
    //проходимся по отсротированному массиву и формируем два новых
    sortedArray.forEach(element => {
        if (
            sumOfResultingArray1 <= sumOfResultingArray2 ||
            sumOfResultingArray2 >= halfOfSum
        ) {
            resultingArray1.push(element)
            sumOfResultingArray1 += element
        } else {
            resultingArray2.push(element)
            sumOfResultingArray2 += element
        }
    })
    return [resultingArray1, resultingArray2]
}
const innerArray1 = [3, 3, 3, 7, 5]
//использование
const [arr1, arr2] = getArrays(innerArray1)
console.log(`Исходный массив: [ ${innerArray1} ]`)
console.log(`Массив 1: [ ${arr1} ], Сумма: ${getSumOfArray(arr1)}`)
console.log(`Массив 2: [ ${arr2} ], Сумма: ${getSumOfArray(arr2)}`)
console.log('----------------------------')
const innerArray2 = [3, 3, 3, 7, 5, 4, 5, 6, 61, 62]
//использование без деструктуризации
const result = getArrays(innerArray2)
const array1 = result[0]
const array2 = result[1]
console.log(`Исходный массив: [ ${innerArray2} ]`)
console.log(`Массив 1: [ ${array1} ], Сумма: ${getSumOfArray(array1)}`)
console.log(`Массив 1: [ ${array2} ], Сумма: ${getSumOfArray(array2)}`)

Answer 3

Если я не ошибаюсь, эта задача называется "Задача о рюкзаке" с некоторыми дополнениями. Разница с классической задачей в том, что надо будет собрать не один, а два "рюкзака", и следить не за тем, чтобы рюкзак был заполнен максимально ценными предметами, а за тем, чтобы вес рюкзаков был бы максимально близок друг к другу. Алгоритм решения задачи можно посмотреть здесь: https://vscode.ru/prog-lessons/zadacha-o-ryukzake.html

READ ALSO
Deno - Ошибка TS2339 [ERROR]: Property &#39;name&#39; does not exist on type &#39;UserSchema | null&#39;

Deno - Ошибка TS2339 [ERROR]: Property 'name' does not exist on type 'UserSchema | null'

Есть две функции javascript/typescript(Deno)Первая получает инфо по пользователю по id, а вторая удаляет пользователя по id

286
manifest.json возвращает noscript

manifest.json возвращает noscript

У меня есть сайт KinoFinderПри первом запуске (или ctrl + F5) В консоли такая ошибка:

177
Сделать цветную область внутри чернобелого background-image

Сделать цветную область внутри чернобелого background-image

Есть div с шириной 100% и высотой 100vh и заданной ему фоновой картинкой в качестве background; также заданы background-size: cover и filter: grayscale(100%)Нужно расположить...

136