Гугли динамическое программирование
Это троллинговый тред про NP-полные задачи?
NIET
может анон сходу предложит хорошую эвристику?
я б перевел в целые.
а потом нагуглил жадный алгоритм
и йобнул на кристале
не благадари
Довольно интересная задача. Это из ЕГЭ по информатике?
из жизни
но если ты знаешь, как в этой задаче перейти к поиску максимума/минимума, то будет как из егэ по информатике
это же почти рюкзак
ну или дерево тупо построил, с учетом симметрии
не знаю
зависит от количества точек
оп чёт неочень
Что надо почитать, чтобы научиться решать такое? Везде говорят про графы, жадные алгоритмы, деревья - а я не знаю что это.
подумаю, как применить рюкзак с мультивыбором. Спасибо, анон!
всё лучше с кристаллом
Я придумал тупой метод. Но чет сомневаюсь в его алгоритмической правильности. Кто-нибудь доказывал, что эта задача решается только полным перебором?
>жизни
ОП, а тебе нужно математически идеально наименьшее? Или правдоподобное наименьшее подойдет?
Число перестановок в задаче ОПа равно 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}}
Тестировать будем на данных для которых я уже нашел решение брутфорсом.
Будем использовать такую метрику: вы постите решение (индексы или уже выбранный список) + время работы вашего алгоритма в мс. Далее умножаем отклонение в позициях от правильного на мс работы. Победит тот у кого это число наименьшее.
Тестовый лист:
{{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}}
КОГДА ТРЕНИРУЕШЬ НЕЙРОСЕТЬ
@
ЧТОБЫ РЕШИТЬ ЗАДАЧУ О РАНЦЕ
@
ЧТОБЫ РЕШИТЬ ЗАДАЧУ О РАНЦЕ
В следующей жизни расскажешь как натренировал.
ОП, ты испортил мне жизнь сон. Никак не мог уснуть — всю ночь думал про твою ебанутую задачу.
Задача сводится к оптимизационной с сильно осциллирующей функцией. К программированию это говно имеет весьма отдаленное отношение.
Задача сводится к оптимизационной с сильно осциллирующей функцией. К программированию это говно имеет весьма отдаленное отношение.
А если в инпуте все числа отрицательные?
Ты бы не прошел у меня интервью.
Могу предложить такой алгоритм: сначала выбираешь из пар такие числа чтобы модуль суммы был наименьшим - так ты не убежишь от нуля далеко. Потом можно пройтись по массиву еще несколько раз, меняя изначальный выбор в том случае если удается получить неотрицательную сумму меньшую чем в предыдущем случае. Это должно быть быстрее полного перебора.
https://ideone.com/F3ANYn
https://ideone.com/F3ANYn
> JS
> $.each
Чувааааак.
У нас есть подебитель. Это джаваскрипт?
> Потом можно пройтись по массиву еще несколько раз, меняя изначальный выбор в том случае если удается получить неотрицательную сумму меньшую чем в предыдущем случае
Но тогда нужно помнить индексы выбора, чтобы менять числа пары.
В чем проблема их помнить? Память лимитирована?
Прогони на тестовых данных из поста:
Посмотрим на метрику.
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
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
>0.009682244792411643
Решение находится на 3939 месте. Умножаем 9.042236328125 на 3939 и получаем 35617.4
Сорри, но победитель прежний.
>время работы вашего алгоритма в мс
А ты не думал, что время работы на каждой машине будет разное?
Так он же на своей пускает
Тогда вопросов нет.
>((0.08, -0.12), (0.07, -0.13), (0.03, -0.7), (0.14, -0.2))
1. Считаем все возможные суммы (2^22).
2. Убираем отрицательные.
3. Ищем наименьшую.
4. ???
5. Profit
Где в результирующем выводе полученная сумма и список чисел?
Сумма в самом внизу, списка нет :(.
твой алгоритм неверен
попробуй входные данные [[1,2], [3,-4]]
в нем минимальная верная сумма 4, а у тебя выходит 1
Сорян, пацаны, нужно конечно же сначала кэшировать в addToSums, а затем менять значение.
Сейчас ответ сходится с .
Not bad.
Ну что вы, бэтманы? Остальные сдулись?
И ненадувались.
А жаль, интресная же задачка.
> Далее умножаем отклонение в позициях от правильного на мс работы
>на мс работы
Как скажишь, насяльника!
Ответ неверный (даже в приближении должен дать больше 2.65), чини алгоритм.
>Ответ неверный
А верного ответа никто и не просил, просили лучшее соотношение произведения точности на время.
>даже в приближении должен дать больше 2.65
Там и так сумма наибольших чисел из каждой пары, куда еще больше?
Очевидная шутка юмора была.
Задача о рюкзаке полным перебором, ой уморили. Сразу видно в вузе не учились.
Берешь сумму всех максимальных, и сохраняешь модуль разности всех пар. На этих разностях и сумме получаешь 0-1 рюкзак, решаешь его, и где получаешь 1 - меняешь элемент из пары на минимальный.
Тока осторожнее с парами где элементы равны - такие лучше отфильтровать заранее. Как и случай с отрицательной/нулевой суммой.
Оп здесь. Анализ тестовой выборки выявил некоторые особенности в данных, поэтому получилось решить жадно с приемлемой точностью. Всем спасибо за участие.
Аноны, что нужно изучать, что бы понимать эти элементарные вещи?
Пхп макак врывается в тред. Решил вашу задачу полным перебором.
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, но между собой нихуя не равны, поэтому пришлось сначала домножать на много, брать целую часть, а потом снова делить в конце.
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, но между собой нихуя не равны, поэтому пришлось сначала домножать на много, брать целую часть, а потом снова делить в конце.
HALP