Приветствую, уважаемый аноним. Перейду сразу к делу. Дан массив пар числел, например ((0.08, -0.12), (0.07, -0.13), (0.03, -0.7), (0.14, -0.2)). Надо из каждой пары выбрать одно число так, чтобы сумма всех выбранных чисел была минимальной не отрицательной. HALP
>>1044642 (OP)Гугли динамическое программирование
Это троллинговый тред про NP-полные задачи?
>>1044644Кажется, меня только что обоссали на википедии
>>1044657NIETможет анон сходу предложит хорошую эвристику?
>>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)А если в инпуте все числа отрицательные?
>>1044721
>>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Тогда вопросов нет.
>>1044929забыл
>>1044642 (OP)>((0.08, -0.12), (0.07, -0.13), (0.03, -0.7), (0.14, -0.2))
>>10447211. Считаем все возможные суммы (2^22).2. Убираем отрицательные.3. Ищем наименьшую.4. ???5. Profit
>>1044942Где в результирующем выводе полученная сумма и список чисел?
>>1044947Сумма в самом внизу, списка нет :(.
>>1044942твой алгоритм неверенпопробуй входные данные [[1,2], [3,-4]]в нем минимальная верная сумма 4, а у тебя выходит 1
>>1044942fail
>>1044962>>1044967Сорян, пацаны, нужно конечно же сначала кэшировать в addToSums, а затем менять значение.Сейчас ответ сходится с >>1044835.
>>1044642 (OP)>>1044721
>>1045078Not bad.
Ну что вы, бэтманы? Остальные сдулись?
>>1045528И ненадувались.
>>1045563А жаль, интресная же задачка.
>>1044721> Далее умножаем отклонение в позициях от правильного на мс работы>на мс работыКак скажишь, насяльника!
>>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, но между собой нихуя не равны, поэтому пришлось сначала домножать на много, брать целую часть, а потом снова делить в конце.