🌬М
Size: a a a
2021 February 10
DM
Вот это лучше, да
DM
Это очень производительное решение
ym
function solve(arr) {
function take(set1sum, set2sum = 0, mapper = 0, s = 0) {
let result = { mapper, set1sum, set2sum };
for (let i = s; i < arr.length; i++) {
const bit = 1 << i;
if (!(mapper & bit)) {
const x = arr[i];
if (set1sum - x - (set2sum + x) < set1sum - set2sum) {
const r = take(set1sum - x, set2sum + x, mapper | bit, i);
const d = Math.abs(r.set1sum - r.set2sum);
if (d < Math.abs(result.set1sum - result.set2sum)) {
if (d === 0) return r;
result = r;
}
}
}
}
return result;
}
const sum = arr.reduce((acc, cur) => acc + cur, 0);
const { set1sum, set2sum, mapper } = take(sum);
const set1 = [];
const set2 = [];
for (let i = 0; i < arr.length; i++) {
if (mapper & (1 << i)) {
set2.push(arr[i]);
} else {
set1.push(arr[i]);
}
}
return { set1, set2, set1sum, set2sum };
}
function take(set1sum, set2sum = 0, mapper = 0, s = 0) {
let result = { mapper, set1sum, set2sum };
for (let i = s; i < arr.length; i++) {
const bit = 1 << i;
if (!(mapper & bit)) {
const x = arr[i];
if (set1sum - x - (set2sum + x) < set1sum - set2sum) {
const r = take(set1sum - x, set2sum + x, mapper | bit, i);
const d = Math.abs(r.set1sum - r.set2sum);
if (d < Math.abs(result.set1sum - result.set2sum)) {
if (d === 0) return r;
result = r;
}
}
}
}
return result;
}
const sum = arr.reduce((acc, cur) => acc + cur, 0);
const { set1sum, set2sum, mapper } = take(sum);
const set1 = [];
const set2 = [];
for (let i = 0; i < arr.length; i++) {
if (mapper & (1 << i)) {
set2.push(arr[i]);
} else {
set1.push(arr[i]);
}
}
return { set1, set2, set1sum, set2sum };
}
Какой пиздец x2
🌬М
Вот это лучше, да
алгорим плиз ) шаг за шагом )
j
Какой пиздец x2
Добро пожаловать в @js_noobs_ru
C
У меня всё довольно прямолинейно. Есть входящий массив N чисел, каждое из чисел отправляется либо в первую кучу, либо во вторую. Обозначив битовой маской длиной N бит каждое разбиение (всего - 2^N, но половина из них повторяет друг друга), переберём все подряд и вычислим суммы чисел в разбиениях. Найдя минимальное удовлетворяющее - выходим.
ym
Вы на функции разбиывать не умеете чтоле? За такое в проде надо увольнять к хуям
DM
Профессионалы сейчас научат нас программировать
🌬М
Какой пиздец x2
есть отличная возможность создать не пизд и поделится )
DM
Давай, братюня, ждем твоего решения
DM
Покажи как надо 👍
j
Покажи как надо 👍
На этом обычно всё и заканчивается.
C
Ввиду специфики перебора, моё решение быстро работает на массивах, упорядоченных по убыванию, и деградирует, когда максимальный элемент располагается ближе к концу массива. Я позже добавил реверс для таких случаев.
ym
Бля из кровати чтоле вставать
C
Но решение Дениса в среднем в 2 раза быстрее, жму лапу.
C
Думал над хитрыми эвристиками для перестановки элементов в более удачном порядке, но к общему виду свести не смог.
C
Chris
Переслано от Chris
Набор
Решение с хитрой оптимизацией
[0,2,2,2,3,4,6,6,6,7,10,12,18,20,30,40,40,50,54,60,60,70,80,80,90,100,120,127]Решение с хитрой оптимизацией
function split(array) {
function partition(array, mask) {
let a = [], b = [], i = array.length;
while (--i >= 0) {
if ((mask >> i) & 1) a.push(array[i]);
else b.push(array[i]);
}
return [a, b];
}
function diffar(array, mask) {
let d = 0, i = array.length;
while (--i >= 0) {
if ((mask >> i) & 1) d += array[i];
else d -= array[i];
}
return d
}
//array = [...array].sort((a,b) => b - a);
let len = array.length;
let min = Infinity, result, idx;
let target = 0;
let sum = array.reduce((a, b) => a + b);
if (sum % 2) target = 1;
let i = 2 ** (len - 1)
while (--i >= 0) {
let diff = Math.abs(diffar(array, i))
if (diff < min) {
if (diff === target) return partition(array, i);
idx = i;
min = diff;
}
}
return partition(array, idx);
}Какой то си напомнило