p
Не всегда выйдет то что ты хочешь
1 1 3 5
Разложиться в
[1, 3] [1, 5]
Разложиться в
[1, 3] [1, 5]
Size: a a a
2020 June 06
DS
НУ А КАК?
Ну вон, про те же акторы говорили тут сколько времени
SS
попробуй просто сортануть массив и найти в нём такую позицию, чтобы разница суммы чисел справа была минимальной с суммой слева
Я подумываю о том что Брут форса наверное не избежать. Скорее всего нужно просто какой-то по умному кешироваить то что уже забрутфорсил, и будет циклов в кучу раз меньше...
AZ
по идее это чутка усложненная задача ранца
DS
Тогда у тебя будет какой-нибудь ThreadStateActor, внутри которого будут запускаться актиксовые футуры, которые держат &mut ThreadStateActor
AZ
где первым шагом узнаешь размер ранца
p
Ясно я никому не нужен
VS
1 1 3 5
Разложиться в
[1, 3] [1, 5]
Разложиться в
[1, 3] [1, 5]
Лол б, ты читал вообще что я писал. По моему алгоритму разложится на [5] [3,1,1]
p
Хотя. Хм. Составлять граф от всех элементов это будет n! сложность. Не слушайте меня.
AZ
Составляй граф где сумма соседних узлов равна 0
у тебя на задачке 1 2 3 4 5 6 7 8 9 10 (sum 1..10) будет всё дерево таким размером
AZ
в этом и задача
AZ
Хотя. Хм. Составлять граф от всех элементов это будет n! сложность. Не слушайте меня.
ну вот ты понял
p
Может всему массиву присвоить плюсы, а потом добавлять минусы пока не окажется сумма 0? Такой умный брутфорс
G
Как добавлять?
AZ
AZ
обычно они строятся на базе и индукции
AZ
"предположим что мы прошли уже n элементов и они уже дают сумму ноль, теперь нам нужно добавить ещё элементов так, что бы сумма осталась ноль"
VS
Я подумываю о том что Брут форса наверное не избежать. Скорее всего нужно просто какой-то по умному кешироваить то что уже забрутфорсил, и будет циклов в кучу раз меньше...
Какой брут форс блять. Ты для варианта который я тебе сказал для каждой коллекции переменную sum сделай и увеличивай ее когда добавляешь в коллекцию цифру
AZ
ветвей и границ например классический алгоритм который ускоряет перебор