Есть последовательность, например:
{"set": [3, 3, 3, 7, 5]}
Необходимо, чтобы эта последовательность разделилась на две, суммы элементов которых будут равны между собой либо максимально приближены друг к другу. Во втором случае ответ должен выглядеть так:
{"set_1": [3, 3, 5], "set_2": [3, 7]}
Сначала думал найти сумму всех элементов, разделить ее пополам и через цикл отнимать. Но это не то. Последовательность может быть любой длины.
Подскажите идеи, какой алгоритм решения?
Описание здесь уже делал, повторю до кучи:
Задача относится к классу 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]));
Функция 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)}`)
Если я не ошибаюсь, эта задача называется "Задача о рюкзаке" с некоторыми дополнениями. Разница с классической задачей в том, что надо будет собрать не один, а два "рюкзака", и следить не за тем, чтобы рюкзак был заполнен максимально ценными предметами, а за тем, чтобы вес рюкзаков был бы максимально близок друг к другу. Алгоритм решения задачи можно посмотреть здесь: https://vscode.ru/prog-lessons/zadacha-o-ryukzake.html
Айфон мало держит заряд, разбираемся с проблемой вместе с AppLab
Есть две функции javascript/typescript(Deno)Первая получает инфо по пользователю по id, а вторая удаляет пользователя по id
У меня есть сайт KinoFinderПри первом запуске (или ctrl + F5) В консоли такая ошибка:
Есть div с шириной 100% и высотой 100vh и заданной ему фоновой картинкой в качестве background; также заданы background-size: cover и filter: grayscale(100%)Нужно расположить...