>>1044642 (OP)
Гугли динамическое программирование

Это троллинговый тред про NP-полные задачи?

>>1044657
NIET

может анон сходу предложит хорошую эвристику?

>>1044662

я б перевел в целые.
а потом нагуглил жадный алгоритм
и йобнул на кристале
не благадари

Довольно интересная задача. Это из ЕГЭ по информатике?

>>1044671

из жизни

>>1044671

но если ты знаешь, как в этой задаче перейти к поиску максимума/минимума, то будет как из егэ по информатике

>>1044642 (OP)
это же почти рюкзак

>>1044670

ну или дерево тупо построил, с учетом симметрии
не знаю
зависит от количества точек
оп чёт неочень

>>1044642 (OP)
Что надо почитать, чтобы научиться решать такое? Везде говорят про графы, жадные алгоритмы, деревья - а я не знаю что это.

>>1044676

подумаю, как применить рюкзак с мультивыбором. Спасибо, анон!

>>1044679

всё лучше с кристаллом

Я придумал тупой метод. Но чет сомневаюсь в его алгоритмической правильности. Кто-нибудь доказывал, что эта задача решается только полным перебором?

>>1044672
>жизни
ОП, а тебе нужно математически идеально наименьшее? Или правдоподобное наименьшее подойдет?

Число перестановок в задаче ОПа равно 2^n, где n -- число пар чисел. Очевидно, что если ебашить перебором на любом мало-мальски длинном листе, то он никогда не решит эту задачу за отведенное время. ОП, какой длины типичный лист с парами чисел?

ОП, а в какой предметной области возникла такая задача?

Походу это все-таки троллинговый тред.

Я придумал гениальное решение этой задачи. Нужно использовать кастомную функцию проверки, которую пихают в алгоритм сортировки.

Умному человеку этой инфы будет достаточно. Если вы тупые, то позже вброшу подробное описание.

Посоны, давайте поменяем условие задачи ОПа на более веселое. Теперь нужно приближенно решить его задачу наиболее быстрым способом.

Тестировать будем на данных для которых я уже нашел решение брутфорсом.

Будем использовать такую метрику: вы постите решение (индексы или уже выбранный список) + время работы вашего алгоритма в мс. Далее умножаем отклонение в позициях от правильного на мс работы. Победит тот у кого это число наименьшее.

Тестовый лист:
{{0.3651525589431013,-0.27439756555180383},{0.3813596282820899,0.4129001439443434},{-0.40018595972934246,0.036322476938139614},{0.20103910110236267,-0.2264911463633661},{-0.1471193507514823,0.1516517904486454},{-0.19961312123638275,0.32420867690476274},{0.1314693103938107,0.08386231037821523},{-0.032350923965245526,-0.08835329409158366},{0.16155915573252155,-0.4197447029259542},{-0.3500723889425785,0.3242683106460933},{0.0038728621410171193,-0.17427372192135038},{-0.423077654432064,-0.1555870759775846},{-0.3500406380269585,-0.3323007306131922},{-0.15159191832180485,-0.4460865795125559},{-0.06187302589028665,-0.37137387344903305},{-0.25982881637857824,0.41202334197573753},{0.37973732322691345,0.21779452042026382},{-0.42958878111592,-0.18148614115362371},{-0.0642675349597035,-0.4440804036878956},{-0.1496008196436347,-0.445780771513441},{-0.37718478711604675,0.08218318185662543},{0.3674431561443947,-0.49488478131287494}}

КОГДА ТРЕНИРУЕШЬ НЕЙРОСЕТЬ
@
ЧТОБЫ РЕШИТЬ ЗАДАЧУ О РАНЦЕ

>>1044729

В следующей жизни расскажешь как натренировал.

>>1044642 (OP)
А если в инпуте все числа отрицательные?

>>1044835
Ты бы не прошел у меня интервью.

Могу предложить такой алгоритм: сначала выбираешь из пар такие числа чтобы модуль суммы был наименьшим - так ты не убежишь от нуля далеко. Потом можно пройтись по массиву еще несколько раз, меняя изначальный выбор в том случае если удается получить неотрицательную сумму меньшую чем в предыдущем случае. Это должно быть быстрее полного перебора.

https://ideone.com/F3ANYn

>>1044842
> JS
> $.each
Чувааааак.

>>1044835
У нас есть подебитель. Это джаваскрипт?

>>1044842
> Потом можно пройтись по массиву еще несколько раз, меняя изначальный выбор в том случае если удается получить неотрицательную сумму меньшую чем в предыдущем случае
Но тогда нужно помнить индексы выбора, чтобы менять числа пары.

>>1044846
В чем проблема их помнить? Память лимитирована?

>>1044849
Прогони на тестовых данных из поста:
>>1044721
Посмотрим на метрику.

https://ideone.com/0V4z2K - обновленная версия, в предыдущей были баги

test();
VM123:118 0.5675399590155936 (22) [0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0]
VM123:118 0.13103152234811155 (22) [0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0]
VM123:118 0.08342452233251607 (22) [0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0]
VM123:118 0.02742215220617794 (22) [0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0]
VM123:118 0.009682244792411643 (22) [0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0]
VM123:126 0.009682244792411643 (22) [0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0]
VM123:127 time: 9.042236328125ms

>>1044867
>0.009682244792411643
Решение находится на 3939 месте. Умножаем 9.042236328125 на 3939 и получаем 35617.4

Сорри, но победитель прежний.

>>1044721
>время работы вашего алгоритма в мс
А ты не думал, что время работы на каждой машине будет разное?

>>1044896
Так он же на своей пускает

>>1044897
Тогда вопросов нет.

>>1044721
1. Считаем все возможные суммы (2^22).
2. Убираем отрицательные.
3. Ищем наименьшую.
4. ???
5. Profit

>>1044942
Где в результирующем выводе полученная сумма и список чисел?

>>1044947
Сумма в самом внизу, списка нет :(.

>>1044942
твой алгоритм неверен
попробуй входные данные [[1,2], [3,-4]]
в нем минимальная верная сумма 4, а у тебя выходит 1

>>1045078
Not bad.

>>1045528

И ненадувались.

>>1045563
А жаль, интресная же задачка.

>>1045600
Ответ неверный (даже в приближении должен дать больше 2.65), чини алгоритм.

>>1045613
>Ответ неверный
А верного ответа никто и не просил, просили лучшее соотношение произведения точности на время.
>даже в приближении должен дать больше 2.65
Там и так сумма наибольших чисел из каждой пары, куда еще больше?
Очевидная шутка юмора была.

Задача о рюкзаке полным перебором, ой уморили. Сразу видно в вузе не учились.

>>1044642 (OP)
Берешь сумму всех максимальных, и сохраняешь модуль разности всех пар. На этих разностях и сумме получаешь 0-1 рюкзак, решаешь его, и где получаешь 1 - меняешь элемент из пары на минимальный.

>>1045750
Тока осторожнее с парами где элементы равны - такие лучше отфильтровать заранее. Как и случай с отрицательной/нулевой суммой.

Аноны, что нужно изучать, что бы понимать эти элементарные вещи?

Пхп макак врывается в тред. Решил вашу задачу полным перебором.
https://ideone.com/2j90ze
Поясняю как делал.

Так как массив состоит из пар, то каждую пару можно представить как бит. И выбирать из пары либо 1 либо 0
И вот всё что осталось это перебрать все двоичные числа в случае с 4 элементами от 0000 до 1111 беря вместо 0 и единицы соответственно нулевой и первый элемент каждой пары.

Далее все эти варианты сваливаются в кучу которая сортируется и из неё уже выбирается что нужно.

х1000, /1000 и 0.00001 в коде это потому что пхп не умеет сравнивать флоат числа :(

Для пхп суммы данных массивов:
["0.08 -0.13 0.03 0.14 "]=> float(0.12)
["-0.12 0.07 0.03 0.14 "]=> float(0.12)
пусть оба и равны по 0.12, но между собой нихуя не равны, поэтому пришлось сначала домножать на много, брать целую часть, а потом снова делить в конце.