DM
Ну, это называется жадный алгоритм
Size: a a a
2021 February 06
DM
И он не всегда дает правильный ответ
🌬М
мне нужен универсальный ) помогите
C
попробуй, хз
function split(array) {
const sum = ar => ar.reduce((x,y) => x + y, 0);
const desc = (a, b) => b - a;
let a = [], b = [];
let sums = new Map();
sums.set(a, 0);
sums.set(b, 0);
let sorted = [...array].sort(desc);
while (sorted.length) {
let el = sorted.shift();
let rest = sum(sorted);
// всё в а - а+э+рест меньше или равно б
if (sums.get(a) + el + rest <= sums.get(b)) {
a.push(el, ...sorted);
sorted.length = 0;
break;
}
// всё в б - б+э+рест меньше или равно а
if (sums.get(b) + el + rest <= sums.get(a)) {
b.push(el, ...sorted);
sorted.length = 0;
break;
}
// э в а - а+э меньше или равно б
if (sums.get(a) <= sums.get(b)) {
a.push(el);
sums.set(a, sums.get(a) + el);
} else {
// э в б - б+э меньше или равно а
b.push(el);
sums.set(b, sums.get(b) + el);
}
}
return [a, b];
}DM
Я думаю это задача об укладке рюкзака
DM
Она NP-полная и решается перебором
AA
Я думаю это задача об укладке рюкзака
Я называю ее задачу о ранце-засранце
🌬М
Chris
попробуй, хз
function split(array) {
const sum = ar => ar.reduce((x,y) => x + y, 0);
const desc = (a, b) => b - a;
let a = [], b = [];
let sums = new Map();
sums.set(a, 0);
sums.set(b, 0);
let sorted = [...array].sort(desc);
while (sorted.length) {
let el = sorted.shift();
let rest = sum(sorted);
// всё в а - а+э+рест меньше или равно б
if (sums.get(a) + el + rest <= sums.get(b)) {
a.push(el, ...sorted);
sorted.length = 0;
break;
}
// всё в б - б+э+рест меньше или равно а
if (sums.get(b) + el + rest <= sums.get(a)) {
b.push(el, ...sorted);
sorted.length = 0;
break;
}
// э в а - а+э меньше или равно б
if (sums.get(a) <= sums.get(b)) {
a.push(el);
sums.set(a, sums.get(a) + el);
} else {
// э в б - б+э меньше или равно а
b.push(el);
sums.set(b, sums.get(b) + el);
}
}
return [a, b];
}спс чекну сейчас )
C
Chris
попробуй, хз
function split(array) {
const sum = ar => ar.reduce((x,y) => x + y, 0);
const desc = (a, b) => b - a;
let a = [], b = [];
let sums = new Map();
sums.set(a, 0);
sums.set(b, 0);
let sorted = [...array].sort(desc);
while (sorted.length) {
let el = sorted.shift();
let rest = sum(sorted);
// всё в а - а+э+рест меньше или равно б
if (sums.get(a) + el + rest <= sums.get(b)) {
a.push(el, ...sorted);
sorted.length = 0;
break;
}
// всё в б - б+э+рест меньше или равно а
if (sums.get(b) + el + rest <= sums.get(a)) {
b.push(el, ...sorted);
sorted.length = 0;
break;
}
// э в а - а+э меньше или равно б
if (sums.get(a) <= sums.get(b)) {
a.push(el);
sums.set(a, sums.get(a) + el);
} else {
// э в б - б+э меньше или равно а
b.push(el);
sums.set(b, sums.get(b) + el);
}
}
return [a, b];
}не, фигня, тоже могут быть наборы, в которых оно будет некорректный результат давать.
DM
Тут только перебором
🌬М
Chris
попробуй, хз
function split(array) {
const sum = ar => ar.reduce((x,y) => x + y, 0);
const desc = (a, b) => b - a;
let a = [], b = [];
let sums = new Map();
sums.set(a, 0);
sums.set(b, 0);
let sorted = [...array].sort(desc);
while (sorted.length) {
let el = sorted.shift();
let rest = sum(sorted);
// всё в а - а+э+рест меньше или равно б
if (sums.get(a) + el + rest <= sums.get(b)) {
a.push(el, ...sorted);
sorted.length = 0;
break;
}
// всё в б - б+э+рест меньше или равно а
if (sums.get(b) + el + rest <= sums.get(a)) {
b.push(el, ...sorted);
sorted.length = 0;
break;
}
// э в а - а+э меньше или равно б
if (sums.get(a) <= sums.get(b)) {
a.push(el);
sums.set(a, sums.get(a) + el);
} else {
// э в б - б+э меньше или равно а
b.push(el);
sums.set(b, sums.get(b) + el);
}
}
return [a, b];
}
оч большая разница ( но спс
AG
Привет, вопрос немного не по джаваскрипт, а в целом об общем - что стоит утчить следующим когда освоил и получил опыт с react, react native, redux, saga
Думаю или typescript, или учиться писать юнит тесты.
Сейчас работаю в аутсорс конторе, но целюсь в какой нибудьь продукт или стартапчик.
Думаю или typescript, или учиться писать юнит тесты.
Сейчас работаю в аутсорс конторе, но целюсь в какой нибудьь продукт или стартапчик.
AM
Переслано от Ahma Mahma
привет, подскажите как сделать эдакую задержку на ввод, типа подождать пока польз введет строку а потом выполнить fetchSearchResults(value); ?
setTimOut?
setTimOut?
C
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 sum(array) {
let result = 0, l = array.length;
while (--l >= 0) result += array[l];
return result
}
function split(array) {
let len = array.length;
let i = 2 ** len;
let results = [];
let min = Infinity, minidx = 0;
while (--i >= 0) {
let [a, b] = partition(array, i);
let diff = Math.abs(sum(a) - sum(b))
if (diff < min) {
if (diff === 0) return [a, b];
min = diff;
minidx = i;
}
results[i] = [a, b];
}
return results[minidx];
}перебором
D
Ahma Mahma
Переслано от Ahma Mahma
привет, подскажите как сделать эдакую задержку на ввод, типа подождать пока польз введет строку а потом выполнить fetchSearchResults(value); ?
setTimOut?
setTimOut?
Почитай про debounce
AM
хм оке
AG
Ahma Mahma
Переслано от Ahma Mahma
привет, подскажите как сделать эдакую задержку на ввод, типа подождать пока польз введет строку а потом выполнить fetchSearchResults(value); ?
setTimOut?
setTimOut?
Да, гугли debounce
AG
Или throtling
AM
во, вроде работает) спасибо
DM
мне нужен универсальный ) помогите
function solve(arr) {
const sum = arr.reduce((acc, cur) => acc+cur, 0)
function take(set1, set2, set1sum, set2sum) {
let result = { set1, set2, set1sum, set2sum }
for (let i=0; i<set1.length; i++) {
const x = set1[i]
const _set1 = [...set1.slice(0, i), ...set1.slice(i + 1)]
const _set2 = [...set2, x]
const r = take(_set1, _set2, set1sum - x, set2sum + x)
if (Math.abs(r.set1sum - r.set2sum) < Math.abs(set1sum - set2sum)) {
result = r
}
}
return result
}
return take(arr, [], sum, 0, sum)
}
const result = solve([8, 7, 6, 5, 4])
console.log(result)