Сохранен 63
https://2ch.hk/pr/res/1044642.html

Приветствую, уважаемый аноним. Перейду сразу

 Аноним 14/08/17 Пнд 22:41:54 #1 №1044642 
image.jpg
Приветствую, уважаемый аноним. Перейду сразу к делу. Дан массив пар числел, например ((0.08, -0.12), (0.07, -0.13), (0.03, -0.7), (0.14, -0.2)). Надо из каждой пары выбрать одно число так, чтобы сумма всех выбранных чисел была минимальной не отрицательной.

HALP
Аноним 14/08/17 Пнд 22:45:32 #2 №1044644 
>>1044642 (OP)
Гугли динамическое программирование
Аноним 14/08/17 Пнд 22:59:06 #3 №1044657 
Это троллинговый тред про NP-полные задачи?
Аноним 14/08/17 Пнд 23:01:04 #4 №1044660 
image.png
>>1044644

Кажется, меня только что обоссали на википедии
Аноним 14/08/17 Пнд 23:02:32 #5 №1044662 
>>1044657
NIET

может анон сходу предложит хорошую эвристику?
Аноним 14/08/17 Пнд 23:12:58 #6 №1044670 
>>1044662

я б перевел в целые.
а потом нагуглил жадный алгоритм
и йобнул на кристале
не благадари
Аноним 14/08/17 Пнд 23:14:19 #7 №1044671 
Довольно интересная задача. Это из ЕГЭ по информатике?
Аноним 14/08/17 Пнд 23:15:47 #8 №1044672 
>>1044671

из жизни
Аноним 14/08/17 Пнд 23:17:17 #9 №1044673 
>>1044671

но если ты знаешь, как в этой задаче перейти к поиску максимума/минимума, то будет как из егэ по информатике
sageАноним 14/08/17 Пнд 23:19:30 #10 №1044676 
>>1044642 (OP)
это же почти рюкзак
Аноним 14/08/17 Пнд 23:22:52 #11 №1044679 
>>1044670

ну или дерево тупо построил, с учетом симметрии
не знаю
зависит от количества точек
оп чёт неочень
Аноним 14/08/17 Пнд 23:24:31 #12 №1044680 
>>1044642 (OP)
Что надо почитать, чтобы научиться решать такое? Везде говорят про графы, жадные алгоритмы, деревья - а я не знаю что это.
Аноним 14/08/17 Пнд 23:26:13 #13 №1044681 
>>1044676

подумаю, как применить рюкзак с мультивыбором. Спасибо, анон!
Аноним 14/08/17 Пнд 23:29:16 #14 №1044682 
>>1044679

всё лучше с кристаллом
Аноним 14/08/17 Пнд 23:50:20 #15 №1044690 
Я придумал тупой метод. Но чет сомневаюсь в его алгоритмической правильности. Кто-нибудь доказывал, что эта задача решается только полным перебором?
Аноним 15/08/17 Втр 00:00:25 #16 №1044693 
>>1044672
>жизни
ОП, а тебе нужно математически идеально наименьшее? Или правдоподобное наименьшее подойдет?
Аноним 15/08/17 Втр 00:08:47 #17 №1044697 
Число перестановок в задаче ОПа равно 2^n, где n -- число пар чисел. Очевидно, что если ебашить перебором на любом мало-мальски длинном листе, то он никогда не решит эту задачу за отведенное время. ОП, какой длины типичный лист с парами чисел?
Аноним 15/08/17 Втр 00:28:23 #18 №1044703 
ОП, а в какой предметной области возникла такая задача?
Аноним 15/08/17 Втр 00:39:02 #19 №1044707 
Походу это все-таки троллинговый тред.
Аноним 15/08/17 Втр 00:43:23 #20 №1044712 
Я придумал гениальное решение этой задачи. Нужно использовать кастомную функцию проверки, которую пихают в алгоритм сортировки.

Умному человеку этой инфы будет достаточно. Если вы тупые, то позже вброшу подробное описание.
Аноним 15/08/17 Втр 01:11:03 #21 №1044720 
ranec.jpg
Аноним 15/08/17 Втр 01:26:49 #22 №1044721 
Посоны, давайте поменяем условие задачи ОПа на более веселое. Теперь нужно приближенно решить его задачу наиболее быстрым способом.

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

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

Тестовый лист:
{{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}}



Аноним 15/08/17 Втр 02:56:19 #23 №1044729 
КОГДА ТРЕНИРУЕШЬ НЕЙРОСЕТЬ
@
ЧТОБЫ РЕШИТЬ ЗАДАЧУ О РАНЦЕ
Аноним 15/08/17 Втр 09:48:32 #24 №1044776 
>>1044729

В следующей жизни расскажешь как натренировал.
Аноним 15/08/17 Втр 10:53:22 #25 №1044800 
min.jpg
ОП, ты испортил мне жизнь сон. Никак не мог уснуть — всю ночь думал про твою ебанутую задачу.

Задача сводится к оптимизационной с сильно осциллирующей функцией. К программированию это говно имеет весьма отдаленное отношение.
Аноним 15/08/17 Втр 11:40:16 #26 №1044812 
>>1044642 (OP)
А если в инпуте все числа отрицательные?
Аноним 15/08/17 Втр 13:12:36 #27 №1044835 
image.png
>>1044721
Аноним 15/08/17 Втр 13:18:49 #28 №1044838 
>>1044835
Ты бы не прошел у меня интервью.
Аноним 15/08/17 Втр 13:26:05 #29 №1044842 
Могу предложить такой алгоритм: сначала выбираешь из пар такие числа чтобы модуль суммы был наименьшим - так ты не убежишь от нуля далеко. Потом можно пройтись по массиву еще несколько раз, меняя изначальный выбор в том случае если удается получить неотрицательную сумму меньшую чем в предыдущем случае. Это должно быть быстрее полного перебора.

https://ideone.com/F3ANYn
Аноним 15/08/17 Втр 13:27:56 #30 №1044844 
>>1044842
> JS
> $.each
Чувааааак.
Аноним 15/08/17 Втр 13:29:19 #31 №1044845 
>>1044835
У нас есть подебитель. Это джаваскрипт?
Аноним 15/08/17 Втр 13:30:10 #32 №1044846 
>>1044842
> Потом можно пройтись по массиву еще несколько раз, меняя изначальный выбор в том случае если удается получить неотрицательную сумму меньшую чем в предыдущем случае
Но тогда нужно помнить индексы выбора, чтобы менять числа пары.
Аноним 15/08/17 Втр 13:33:40 #33 №1044849 
>>1044846
В чем проблема их помнить? Память лимитирована?
Аноним 15/08/17 Втр 13:34:47 #34 №1044850 
>>1044849
Прогони на тестовых данных из поста:
>>1044721
Посмотрим на метрику.
Аноним 15/08/17 Втр 14:14:58 #35 №1044867 
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
Аноним 15/08/17 Втр 14:47:17 #36 №1044878 
>>1044867
>0.009682244792411643
Решение находится на 3939 месте. Умножаем 9.042236328125 на 3939 и получаем 35617.4

Сорри, но победитель прежний.
Аноним 15/08/17 Втр 15:38:07 #37 №1044896 
>>1044721
>время работы вашего алгоритма в мс
А ты не думал, что время работы на каждой машине будет разное?
Аноним 15/08/17 Втр 15:39:26 #38 №1044897 
>>1044896
Так он же на своей пускает
Аноним 15/08/17 Втр 15:42:21 #39 №1044900 
>>1044897
Тогда вопросов нет.
Аноним 15/08/17 Втр 16:12:58 #40 №1044929 
image.png
Аноним 15/08/17 Втр 16:20:40 #41 №1044935 
image.png
>>1044929
забыл
Аноним 15/08/17 Втр 16:22:04 #42 №1044937 
image.png
>>1044642 (OP)
>((0.08, -0.12), (0.07, -0.13), (0.03, -0.7), (0.14, -0.2))
Аноним 15/08/17 Втр 16:25:22 #43 №1044942 
1.png
2.png
>>1044721
1. Считаем все возможные суммы (2^22).
2. Убираем отрицательные.
3. Ищем наименьшую.
4. ???
5. Profit
Аноним 15/08/17 Втр 16:29:53 #44 №1044947 
>>1044942
Где в результирующем выводе полученная сумма и список чисел?
Аноним 15/08/17 Втр 16:34:38 #45 №1044948 
>>1044947
Сумма в самом внизу, списка нет :(.
Аноним 15/08/17 Втр 16:58:44 #46 №1044962 
>>1044942
твой алгоритм неверен
попробуй входные данные [[1,2], [3,-4]]
в нем минимальная верная сумма 4, а у тебя выходит 1
Аноним 15/08/17 Втр 17:04:46 #47 №1044967 
image.png
>>1044942
fail
Аноним 15/08/17 Втр 17:06:53 #48 №1044969 
2.png
>>1044962
>>1044967
Сорян, пацаны, нужно конечно же сначала кэшировать в addToSums, а затем менять значение.
Сейчас ответ сходится с >>1044835.
Аноним 15/08/17 Втр 20:42:41 #49 №1045078 
image.png
>>1044642 (OP)
>>1044721
Аноним 15/08/17 Втр 21:24:12 #50 №1045090 
>>1045078
Not bad.
Аноним 16/08/17 Срд 20:15:46 #51 №1045528 
14781090005500.jpg
Ну что вы, бэтманы? Остальные сдулись?
Аноним 16/08/17 Срд 21:13:26 #52 №1045563 
>>1045528

И ненадувались.
Аноним 16/08/17 Срд 21:16:43 #53 №1045565 
>>1045563
А жаль, интресная же задачка.
Аноним 16/08/17 Срд 22:33:02 #54 №1045600 
notveryprecisebutfast.png
>>1044721
> Далее умножаем отклонение в позициях от правильного на мс работы
>на мс работы
Как скажишь, насяльника!
Аноним 16/08/17 Срд 22:57:24 #55 №1045613 
>>1045600
Ответ неверный (даже в приближении должен дать больше 2.65), чини алгоритм.
Аноним 16/08/17 Срд 23:02:34 #56 №1045618 
image.png
Рандом ищет дольше, чем полный перебор.
Аноним 16/08/17 Срд 23:08:31 #57 №1045621 
>>1045613
>Ответ неверный
А верного ответа никто и не просил, просили лучшее соотношение произведения точности на время.
>даже в приближении должен дать больше 2.65
Там и так сумма наибольших чисел из каждой пары, куда еще больше?
Очевидная шутка юмора была.
Аноним 17/08/17 Чтв 07:45:48 #58 №1045738 
Задача о рюкзаке полным перебором, ой уморили. Сразу видно в вузе не учились.
Аноним 17/08/17 Чтв 09:47:58 #59 №1045750 
>>1044642 (OP)
Берешь сумму всех максимальных, и сохраняешь модуль разности всех пар. На этих разностях и сумме получаешь 0-1 рюкзак, решаешь его, и где получаешь 1 - меняешь элемент из пары на минимальный.
Аноним 17/08/17 Чтв 09:55:30 #60 №1045752 
>>1045750
Тока осторожнее с парами где элементы равны - такие лучше отфильтровать заранее. Как и случай с отрицательной/нулевой суммой.
Аноним 19/08/17 Суб 16:24:30 #61 №1046936 
image.jpg
Оп здесь. Анализ тестовой выборки выявил некоторые особенности в данных, поэтому получилось решить жадно с приемлемой точностью. Всем спасибо за участие.
Аноним 19/08/17 Суб 20:06:39 #62 №1047048 
Аноны, что нужно изучать, что бы понимать эти элементарные вещи?
Аноним 22/08/17 Втр 10:56:03 #63 №1048550 
Пхп макак врывается в тред. Решил вашу задачу полным перебором.
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, но между собой нихуя не равны, поэтому пришлось сначала домножать на много, брать целую часть, а потом снова делить в конце.

comments powered by Disqus

Отзывы и предложения